Category: Other

This isn’t a proof by contradiction

A short rant on bad proofs.

Recently I came across a proof concerning orthonormal basis of the following theorem (don’t worry if you know nothing about it):

Theorem. Let V be a vector space with inner (dot) product \langle\cdot,\cdot\rangle. Let B = \{b_1,\ldots,b_n\} be an orthonormal set of vectors, i.e. the vectors are pairwise orthogonal of norm 1. Then this set is linearly independent.

The proof I read goes as follows:

Proof Assume by contradiction, that B is not linearly independent. This means that there is a non-zero solution \alpha_1, \ldots, \alpha_n to the equation

    \[\sum_{i} \alpha_i b_i = 0\]

. However, this means that for every i=1,\ldots,n we have

    \begin{align*}0 &= \langle 0, b_i\rangle \\ &= \langle\sum_j \alpha_j b_j, b_j\rangle \\ &= \sum_j \alpha_j\langle b_j, b_i\rangle \\ &= \alpha_i\langle b_i, b_i\rangle \\ &= \alpha_i\end{align*}


However, we assumed that \alpha_i are non-zero, but we just showed that they must be zero. This is a contradiction with our assumption, hence the assumption is wrong, so \alpha_i must be zero. \qed

You can read the original proof here, it’s the same, but with more details on why the equalities here hold, which this is irrelevant for this post.

You might already see that something is odd here, especially given the title of this post. How is this exactly a proof by contradiction? Well, in the end we got a contradiction with the assumptions, so technically it is proof by contradiction. However, it is practically a very direct proof. Where did we use the assumption? It wasn’t useful by any means. We had some statement p that we wanted to prove, so we assumed \neg p, then showed that p holds, and then concluded that it cannot be that p\wedge \neg p, hence p. It’s quite a mental gymnastics here, don’t you agree?

This example may seem artificial, but you can clearly see that I didn’t come up with it on my own. I claim that this pattern can be seen often in the wild, especially when students are presenting proofs on the tutorials.

Example of a good proof by contradiction

A very well known and simple example is the proof that \sqrt{2} is irrational. In other words, the theorem states that there are no integers p, q\neq 0 such \sqrt{2} = \frac{p}{q}.

Proof. Assume by contradiction that there are integers p, q\neq 0 such that \sqrt{2} = \frac{p}{q}. We may assume without loss of generality, that p and q are coprime. Then we have a sequence of equivalent equalities:

    \begin{align*}\sqrt{2} &= \frac{p}{q} \\ 2q^2 &= p^2 \\ q^2 &= 2{p'}^2 \end{align*}


where p’ is \frac{p}{2}. This is an integer as well, by the Euclid’s lemma. So, by the same lemma we get that q must be divisible by 2, which is a contradiction with our assumption, that p and q are coprime. \qed

Notice that in this proof we’re actually leveraging the assumption, which wasn’t the case in the former theorem.

What is a proof by contradiction?

Disclaimer. This section is very technical and formal. This may be hideous to some readers. If you despise formal logic and hate Bourbakists, then skip this section for your own sake. I try to formalize what is a proof and why we actually can do a proof by contradiction.

Let’s first establish what is a proof. I don’t want to get in to much details, as this isn’t particularly engaging topic (check out my notes from Logic R if you are interested in a very formal and technical definition). In our case, we can think of a proof of a statement \phi with assumptions T as a sequence of sentences \phi_1,\ldots,\phi_n = \phi, where a sentence must be an assumption from T, a tautology, or be concluded directly from some previous statements in the proof. If there exists a proof of \phi assuming T, then we say that T proves \phi, which is often written as T\vdash\phi.

A proof by contradiction is an approach of proving rather than a technical term. I’ll try to formalize this with so called deduction theorem. It states that if we show that T proves \phi\rightarrow\psi, then T\cup\{\phi\} proves \psi and vice versa. This is again a technical theorem to formalize the fact that if we want to prove an implication A implies B we may simply assume A and then prove that B must hold.

Let’s say we want to prove some theorem \phi. To show that \phi is true, we could show that the following implication is true: \neg\phi\rightarrow\bot (where \bot is basically false, you could interpret it as a sentence x\neq x, which is always false). We could do that as (\neg\phi\rightarrow\bot) \leftrightarrow \phi. So, every proof by contradiction has the following scheme: First prove that T\cup\{\neg\phi\}\vdash\bot, by deduction theorem T\vdash\neg\phi\rightarrow\bot. Thanks to modus ponens we can then extend the proof of this implication and finally show that T\vdash\phi.

Conclusions

I like tidy and deliberate proofs. I also like when a presenter of a solution to some problem on the blackboard gives the viewers a nice and enjoyable experience. This post provides an example of one of the common shortcomings in presenting proofs. It’s not faulty reasoning, but it’s unnecessary and could be simplified and organized at a low cost. I try to pay attention to the preciseness and cleanliness of my solutions. If you ever see me presenting and saying something in a bad fashion, then please don’t mind telling me that!