Proofs
Proofs have been an central element of our civilization for thousands of years. In Odyssey, Homer gives us proof of Ulysses identity when he describes how he is recognized by his aged, faithful dog. In Bible, the resurrected Christ allows Thomas to touch his wounds, leading to the first acclamation of Jesus as God (John 20:24–29). In the Lord of the Rings, Aragorn’s rightful claim to the thrones of Arnor and Gondor is established by the Ring of Barahir and his wielding of the Andúril sword. In fiction and scripture, proofs have been used to establish veracity of deeds and royal or divine status. Proofs satisfy our doubts and skepticism and give meaning to faith and theory alike.
In mathematics, proofs are arguments that establish the truthfulness of various statements. These arguments are based on the building blocks of mathematical systems: axioms, definitions, and theorems.
Direct proofs
This is the easiest kind of proofs, relatively speaking. In direct proofs we usually have a statement of the form:
The approach we take is to look at axioms, definitions, and theorems available to us based on \(p\) and find the right transformations to arrive to \(q\). For example, let’s consider
and
In this example, if \(n\) is odd then \(n=2x+1\) and by squaring both sides,
where \(z=2x^2+2x\). So we showed that \(n^2=2z+1\) which is an odd number.
Sum of two odd numbers is an even number
Another example of a direct proof is to show that if two numbers are odd, their sum is an even number, i.e.,
The proof is quite straight forward: if \(m\) is odd then \(m=2x+1\), i.e. it is, by definition, a multiple of 2 (\(2x\)) plus one. Similarly, \(n=2y+1\); where \(x\ \text{and}\ y\) are arbitrary integer numbers. Adding them together:
with \(k=x+y+1\). Thus we showed that the sum of two odd numbers is a multiple of 2, which by definition is an even number.
The product of odd and even numbers is an even number
Another direct proof is to show that the product of an odd and an even number is an even number. Assuming \(m=2x+1\) (the odd number) and \(n=2y\) (the even number), their product \(mn\) is:
In other words, \(mn\) is a multiple of 2, therefore an even number.
The square of an even number is an even number
Can show that if \(n\) is even, then \(n^2\) is also even? An even number is a multiple of 2, so we can write \(n=2x\). Squaring both sides gives us \(n^2=4x^2=2(2x^2)=2z\), where \(z=2x^2\). By showing that \(n^2=2z\) we have proved that \(n^2\) is even.
Proofs by contradiction
Some times, a direct proof may not be possible. For example, can we prove that if \(n^2\) is even then \(n\) is also even? Trying a direct proof we can write:
There is no way to tell if \(\sqrt{2x}\) is an odd or even number. Clearly, a direct proof approach does not work in this case. What if we took a different approach and assumed that if \(n^2\) is even then \(n\) is odd? If \(n\) is odd, then \(n=2x+1\). And by squaring both sizes of the equation,
with \(z=2x^2+2x\). Therefore \(n^2\) is an odd number though our initial assumption is that \(n^2\) is even. By assuming the opposite conclusion of the statement we tried to prove, we reach a contradiction and that allows us to conclude that the initial statement was actually true.
In general, a proof by contradiction works when a statement of the form
cannot be proved directly; here \(h\) and \(c\) are the hypothesis and conclusion parts of the statement and “\(\rightarrow\)” means “implies”. In this case, the proof by contradiction can be established as follows.
First, we assume that the opposite conclusion is true, i.e., that \(h\rightarrow\neg c\) is true. Remember, “\(\neg\)” is the negation operator and therefore \(\neg c\) is the opposite of \(c\).
Next, given that we accept \(h\rightarrow\neg c\) as true, we can now focus on its conclusion and test if we can derive \(h\) from \(\neg c\). In other words, given that \(h\rightarrow\neg c\) is true can we show that \(\neg c\rightarrow h\)? Attempting to do so will yield a result other than \(h\). Therefore the assumption \(h\rightarrow\neg c\) that allowed us to test if \(\neg c\rightarrow h\), is false. If \(h\rightarrow\neg c\) is false, then \(h\rightarrow c\) must be true. And that concludes our proof!
To illustrate this method, let’s look at the earlier example:
Example: if \(n^2\) is odd then \(n\) is odd
If we tried direct proof here, we’ll end with the expression \(n=\sqrt{2x+1}\) which is of inconclusive parity. Therefore, a proof by contradiction may be a better strategy. Our hypothesis is \(h:\ n^2\ \text{odd}\). Our conclusion is \(c:\ n\ \text{odd}\). And since we cannot prove directly \(h\rightarrow c\), we will assume that \(h\rightarrow\neg c\) is true. Given this assumption, \(n\) is odd and therefore \(n=2x\). Squaring both sides of the equation:
Therefore \(n^2\) is an even number contrary to the assumed truthfulness of \(h\rightarrow\neg c\). Our assumption \(h\rightarrow\neg c\) is false, leading to the conclusion that \(h\rightarrow c\) is true. In other words, if \(n^2\) is odd then \(n\) is also odd.
Example: if \(a,b \in \mathbb{Z}\) then \(a^2-4b\neq 2\)
The hypothesis here is \(h:\ a,b \in \mathbb{Z}\). And the conclusion is \(c:\ a^2-4b\neq 2\). There is no direct way to show \(h\rightarrow c\), and it would seem that a proof by contradiction is the preferred strategy. We begin by assuming that \(h\rightarrow\neg c\) is true, i.e., there are integer numbers \(a,b\) such that \(a^2-4b=2\). Given that, we can write:
From the above we can tell that \(a^2\) is even and therefore \(a\) is also even and thus can be written as a multiple of 2: \(a=2x\) and substituting this in the original expression:
We just concluded that \(1\) is an even number! That’s because the assumption that led us to this astonishing conclusion is false. The assumption was that there are integer numbers \(a,b\) such that \(a^2-4b=2\). This assumption is false which means that there are no integers \(a,b\) such that \(a^2-4b=2\). Therefore, the original statement \(a,b \in \mathbb{Z}\rightarrow a^2-4b\neq 2\), is true.
Example: there is no largest number
Let’s suppose that there is a largest number, \(L\), such that \(L\geq x,\ \forall x\). Given that \(1>0\), we can add \(L\) to both sides, resulting to \(L+1 > L\) which cannot be true, because we assumed that \(L\) is the greatest number, and we just showed that it’s less than \(L+1\).
Step-by-step template for proofs by contradiction
Given a theorem in the form \(h\rightarrow c\), where \(h\) is a hypothesis and \(c\) a conclusion, that cannot be proven directly, proof by contradiction may be our next best bet.
A road sign as a metaphor for proof by contradiction.
To illustrate proof by contradiction, consider this scenario. While driving to Seattle, you come to the road sign shown to the right. You decide to check if the sign is correct but in an indirect way: you turn right. After several hours, you arrive to New York City. The sign was correct: Seattle was to the left.
The theorem to prove is:
You made the assumption that you can still get to Seattle by making the opposite of a left turn (i.e., a right turn). You assumed, in other words, that the following theorem is correct:
Accepting this as true, you turn right and drive until you reach NYC. Evidently, the right-turn theorem is wrong. Therefore, the left-turn theorem is the correct one.
The most important first step
When trying to prove a theorem, the first thing to do is to identify the hypothesis and the conclusion propositions. Theorems are often stated as
So, finding the \(h\) and \(c\) propositions can be done with relative ease.
Formulate the contradicting condition
Using the hypothesis \(h\) and conclusion \(c\) from the previous step, write the contradicting condition:
Let’s resume using mathematical notation and write the contradicting condition as \(h\rightarrow\neg c\).
Accept the contradicting condition as true
State the assumption that \(h\rightarrow\neg c\) is true. You need to write this statement both for your benefit and also for the benefit of those reading your proof. This statement is a “contract” with yourself. You have to believe that the contradicting condition is true until you can prove that it is not.
Work the \(\neg c\)
Much like you started driving after turning right earlier and kept driving until you arrived to a place other than Seattle, you need to work on \(\neg c\) will take you. If the first step is the most important, this step is the most difficult. With practice and experience you develop intuition on the direction that you can take the \(\neg c\).
Examples
Show that if \(n^2\) is odd then \(n\) odd
We worked this example before but we repeat here to focus on two things: first, how to separate \(h\) from \(c\) and second how to work your way from \(\neg c\) to the contradiction. In this case, identifying \(h\) and \(c\) is straight forward: they are both present in the problem statement.
So it’s easy to formulate the contradictory condition \(h\rightarrow\neg c\):
The next challenge is where to take the \(\neg g\). One good place to start with is: definitions. What does it mean for a number to be even? It must be a multiple of two: \(n=2k, k\in\mathbb{Z}\). What to do with this? Well, we are interested in the properties of \(n^2\), so let’s square it: \(n^2=(2k)^2=4k^2=2(2k^2)\). This is a multiple of two; in other words \(n^2\) is even which contradicts our assumption that \(n^2\) is odd.
Show that there is no largest integer number
This is also an example that we worked on above, only it is not immediately obvious what is its \(h\) and what is its \(c\). When a problem is stated as a fact (“there is no largest integer number”), a good strategy is to turn the fact on its head, i.e., to accept (temporarily) that the opposite fact is true: there is a largest interest number.
Let’s call that number \(L\). What does it mean to be the largest integer number. It means that there is no integer number \(x\) such that \(x>L\). But can this be true? Can we not think of a number larger than \(L\)?
Here comes the intuition. Let’s take two numbers, one larger than the other, for example \(3 < 4\). If we add \(L\) to both sides, we get \(L+3 < L+4\). This is interesting because it suggests that a number larger than \(L\) (specifically, \(L+3\)) is greater than another number (\(L+4\)) also larger than \(L\). But this is not conclusive enough. The intuition is in the right direction, we need to experiment a bit, maybe by trying a different pair of numbers. Eventually, we come across the fact \(0 < 1\). Adding \(L\) to both sides yield \(L<L+1\). But if \(L\) is the largest number, how can it be smaller than \(L+1\)? There shouldn’t be any number greater that \(L\). This contradicts our assumption that there is a largest integer number and therefore the original statement must be true: there is no largest integer number.
What was the “magic” above? We started with \(3<4\) and said we should experiment with other ordered pairs of integers. For example, we could have tried \(11<13\) or \(-18 < 2\), etc. Adding \(L\) to both sides would have given the same pattern:
Eventually we come to the realization that we want just \(L\) on the left-hand side of the expression above. And the only “something” that we can add to \(L\) and still get \(L\) is zero. No we need an ordered pair with 0 to the left and something greater than zero to the right. We could try \(0<629\) but in mathematics we strive for the least necessary quantity to prove our point, so we end up with \(0<1\).
The square root of 2 is not a rational number
It is not immediately clear what is the hypothesis and what is the conclusion here. We discussed above that when a property is stated as a fact, to look at the opposite fact and work our way from there. The opposite fact in this case is: \(\sqrt{2}\) is a rational number.
We can write the original statement as:
\[\underbrace{\sqrt{2}=\frac{a}{b}}_{h} \rightarrow \underbrace{a, b\not\in\mathbb{Z}}_{c}\]
Here, \(h\) says that \(\sqrt{2}\) can be writen as a fraction of two numbers. And \(c\) says that these two numbers are not integers. And we can write a contradicting condition as:
\[\underbrace{\sqrt{2}=\frac{a}{b}}_{h} \rightarrow \underbrace{a, b\in\mathbb{Z}}_{\neg c}\]
The rest goes as follows: given that \(a,b\) are integers \(a\neq b\), multiplyin both sides with \(b\) and squaring them yields: \(2b^2=a^2\). Therefore \(a^2\) is a multiple of two, therefore even, and as we proved elsewhere \(a\) is also even and can be writen as \(a=2k\) (i.e., a multiple of two). Substituting \(2k\) for \(a\) we get that \(2b^2=4k^2\Rightarrow b^2=2k^2\), therefore \(b^2\) is even, and so must be \(b\), i.e., \(b=2l\). Now the fraction \(\dfrac{a^2}{b^2}\) can be re-written as \(\dfrac{(2k)^2}{(2l)^2}=\dfrac{k^2}{l^2}\), with \(k\neq l\).
Great! All we accomplished so far is to write a fraction of squared numbers (\(a^2/b^2\)) as a fraction of two other squared numbers (\(k^2/l^2\)). While there is no major award for our accomplishment, there is a notable difference between the two fractions. For the first fraction, we know that \(a^2\) and \(b^2\) are both even numbers. There is no such certainty about \(k^2\) and \(l^2\). We can use this uncertainty to our advantage as follows.
If both \(k^2\) and \(l^2\) are even, we can follow the same logic as above to reduce \(k^2/l^2\) to \(m^2/n^2\), and continue doing so until we reach a fraction where either the numerator or the denominator or both are odd numbers. And that takes us to the next case.
If either \(k^2\) or \(l^2\) (or both) is an odd number, then
The analysis above assumes that one part of the fraction is odd and the other is even, leading to the contradiction that an odd number can be equal to an even one. What if both parts of the fraction were odd numbers? In this case, we reach a similar impossibility:
There is a way to avoid all these different cases (now he tells us!). We can go back to the original contradicting condition and state that since \(\sqrt{2}=a/b\), we want \(a\neq b\) and also we want at least one of them to be odd (so that they do not have 2 as a common factor). Then we show that both \(a,b\) are even numbers, which cannot be true since we just specified that one of them must be odd.
How do we know to make this assumption about not sharing 2 as a common factor? By doing the looong analysis first, realizing that the secret is in fact to write \(\sqrt{2}\) as a fraction where at least one part is odd, and then simplify the presentation of our proof. In other words, we still need to do the long haul but our presentation can be more elegant.