In this section we discuss two strategies for proving statements of the form \(P \to Q\text{.}\) Both these strategies are a bit more convoluted than direct proof, but in some situations they are nonetheless easier to work with. A less than perfect analogy might be when the straightest road between two cities leads up and down a mountain and through difficult terrain, whereas a curved road might at first seem to be going in the wrong direction, but in fact it bypasses the mountain and is ultimately easier and quicker than the straight road.
In order to prove \(P \to Q\text{,}\) we could just as well prove \(¬Q \to ¬P\text{,}\) which we would do by the method of direct proof. We construct such a proof by assuming that \(Q\) is false, and then, in the final write-up, presenting a step-by-step argument going from \(¬Q \) to \(¬P\text{.}\) A proof of this sort is called proof by contrapositive.
Structure2.12.
Suppose that \(Q\) is false. ... (argumentation) ... Then \(P\) is false.
Theorem2.13.
Let \(n\) be an integer. If \(n^2\) is odd, then \(n\) is odd.
Suppose that \(n\) is even. Then there is some integer \(k\) such that \(n = 2k\text{.}\) Hence \(n^2 = (2k)^2 = 4k^2 = 2(2k^2)\text{.}\) Because \(2k^2\) is an integer, it follows that \(n^2\) is even. By contrapositive, we see that if \(n^2\) is odd then n is odd.
Convention2.14.
In the above proof we mentioned that we used proof by contrapositive. In general, it is often helpful to the reader to have the method of proof stated explicitly.
SubsectionContradiction
Another method of proof for theorems with statements of the form \(P \to Q\text{,}\) which looks similar to proof by contrapositive but is actually distinct from it, is proof by contradiction.
Definition2.15.
The method of proof by contradiction is to show that \(P \to Q\) is true by assuming that \(P \wedge ¬Q\) is true, and then deriving a logical contradiction, by which we mean a statement that cannot be true under any circumstances.
Logicians use the term “proof by contradiction” to mean the proof of a statement \(A\) by assuming \(¬A\text{,}\) then reaching a contradiction, and then deducing that \(A\) must be true. For our purposes, we are interested in proof by contradiction for the special case where the statement \(A\) has the form \(P \to Q\text{,}\) because that is how mathematical theorems are formulated.
Structure2.16.
We prove the result by contradiction. Suppose that \(P\) is true and that \(Q\) is false. ... (argumentation) ... We have therefore reached a contradiction. Therefore \(P\) implies \(Q\text{.}\)
Theorem2.17.
The only consecutive non-negative integers \(a\text{,}\)\(b\) and \(c\) that satisfy \(a^2 + b^2 = c^2\) are \(3\text{,}\)\(4\) and \(5\text{.}\)
We prove the result by contradiction. Suppose that \(a\text{,}\)\(b\) and \(c\) are non-negative consecutive integers other than \(3\text{,}\)\(4\) and \(5\text{,}\) and that \(a^2 + b^2 = c^2\text{.}\) Because a, b and c are not 3, 4 and 5, we know that a \neq 3, and because the three numbers are consecutive, we know that b = a + 1 and c = a + 2. From \(a^2 + b^2 = c^2\) we deduce that \(a^2 + (a + 1)^2 = (a + 2)^2\text{.}\) After expanding and rearranging we obtain \(a^2 - 2a - 3 = 0\text{.}\) This equation factors as \((a - 3)(a + 1) = 0\text{.}\) Hence \(a = 3 or a = -1\text{.}\) We have already remarked that \(a \neq 3\text{,}\) and we know a is non-negative. Therefore we have a contradiction, and the theorem is proved.
Our next two theorems are both famous results that have well-known proofs by contradiction. These clever proofs are much more difficult than what we have seen so far, and are more than would be expected of a student to figure out on her own at this point.
Definition2.18.
Let \(x\) be a real number. The number \(x\) is a rational number if there exist integers \(n\) and \(m\) such that \(m \neq 0\) and \(x = \frac{n}{m}\text{.}\) If \(x\) is not a rational number, it is an irrational number.
Remark2.19.
Observe that if \(x\) is a rational number, then there are many different fractions of the form \(n/m\) such that \(x = n/m\text{.}\) Given any fraction \(n/m\) such that \(n \ne 0\text{,}\) we can always reduce it to “lowest terms,” by which we mean that the numerator and denominator have no common factors other than \(1\) and \(-1\text{.}\)
Definition2.20.
Let \(p\) be a positive real number. The square root of \(p\text{,}\) denoted \(\sqrt{p}\text{,}\) is a positive real number \(x\) such that \(x^2 = p\text{.}\)
Theorem2.21.
There is no rational number \(x\) such that \(x^2 = 2\text{.}\)
Let \(x\) be a real number. Suppose that \(x^2 = 2\text{,}\) and that \(x\) is rational. We will derive a contradiction. Because \(x\) is rational, there are integers \(n\) and \(m\) such that \(x = \frac nm \text{.}\) Observe that \(n \neq 0\text{.}\) If \(\frac nm\) is not in lowest terms, then we could cancel any common factors, bringing it to lowest terms. There is no problem assuming that this has been done already, and so we may assume that \(n\) and \(m\) have no common factors other than \(1\) and \(-1\text{.}\)
Because \(x^2 = 2\text{,}\) then \((\frac nm)^2 = 2\text{.}\) It follows that \(\frac{n^2}{m^2} = 2\text{,}\) and hence \(n2 = 2m2\text{.}\) We now ask whether \(n\) is even or odd. If \(n\) were odd, then using Exercise 2.2.4 we would see that \(n^2\) would be odd. This last statement is not possible, because \(n^2 = 2m^2\text{,}\) and \(2m^2\) must be even, because it is divisible by \(2\text{.}\) It follows that \(n\) cannot be odd; hence \(n\) must be even. Therefore there is some integer \(k\) such that \(n = 2k\text{.}\) Then \((2k)^2 = 2m^2\text{,}\) so that \(4k^2 = 2m^2\text{,}\) and therefore \(2k^2 = m^2\) . By an argument similar to the one used above, we see that \(m\) is even. We therefore conclude that both \(n\) and \(m\) are even. We have therefore reached a contradiction, because any two even numbers have \(2\) as a common factor, and yet we assumed that \(n\) and \(m\) have no common factors other than \(1\) and \(-1\text{.}\) Hence \(x\) is not rational.
Definition2.22.
Let \(p\) be an integer greater than \(1\text{.}\) The number \(p\) is a prime number iff the only positive integers that divide \(p\) are \(1\) and \(p\text{.}\) The number \(p\) is a composite number iff it is not a prime number.
