Proof by contradiction
Tonight's idea
Some statements are hard to prove head-on but easy to prove backwards. To show a statement \(S\) is true, assume \(S\) is false, reason carefully, and arrive at something impossible. Correct reasoning cannot lead from a true assumption to an impossibility, so the assumption was false and \(S\) is true. That is proof by contradiction.
The classic: \(\sqrt{2}\) is irrational. A number is rational if it equals a fraction \(p/q\) of whole numbers, and irrational if not. Suppose \(\sqrt{2} = p/q\) in lowest terms (no common factor), so in particular \(p\) and \(q\) are not both even. Square: \(p^2 = 2q^2\), so \(p^2\) is even. An odd number squared is odd (\((2k+1)^2 = 4k^2 + 4k + 1\)), so \(p\) is even: \(p = 2k\). Substitute: \(4k^2 = 2q^2\), so \(q^2 = 2k^2\), so \(q\) is even too. Both even contradicts lowest terms. \(\sqrt{2}\) is irrational.
Notice that the whole weight rests on one unarguable fact: even is not odd.
Watch one: the primes never run out
Suppose there are only finitely many primes: a complete list \(p_1, p_2, \ldots, p_k\). Form \(N = p_1 p_2 \cdots p_k + 1\). Divide \(N\) by any prime on the list and the remainder is 1, so no listed prime divides \(N\). But every whole number bigger than 1 has a prime factor. That factor of \(N\) is not on the list, so the list was not complete. Contradiction.
Careful: the proof does not say \(N\) is prime. With the list 2, 3, 5, 7, 11, 13, \(N = 30031 = 59 \times 509\). It only says the list missed a prime, and here it missed two.
Your turn
- Prove that there is no smallest positive rational number.
- Prove that if \(r\) is rational and \(x\) is irrational, then \(r + x\) is irrational. Then explain why \(\sqrt{2} + 1\) and \(\sqrt{2} - 7/3\) are irrational without any further work.
- Run the \(\sqrt{2}\) proof on \(\sqrt{4}\) and find exactly where it breaks. (It had better break somewhere, because \(\sqrt{4} = 2\).)
- Prove that \(\sqrt{3}\) is irrational. Follow the \(\sqrt{2}\) proof, but at the step "\(p^2\) is a multiple of 3, so \(p\) is", you need a reason. (Hint: if \(p\) is not a multiple of 3 then \(p = 3m + 1\) or \(3m + 2\). Square each and look at the remainder.)
Stretch: a logarithm that is not a fraction
\(\log_2 3\) is the number \(x\) with \(2^x = 3\), about 1.585. Prove it is irrational: suppose \(2^{p/q} = 3\) with \(p, q\) positive whole numbers, raise both sides to the power \(q\), and look at even versus odd.
Answers
- Suppose \(r\) is the smallest positive rational. Then \(r/2\) is rational, positive, and smaller than \(r\). Contradiction.
- Suppose \(r + x = s\) is rational. Then \(x = s - r\), the difference of two rationals, which is rational (common denominators). That contradicts \(x\) irrational. Since 1 and \(-7/3\) are rational and \(\sqrt{2}\) is irrational, both sums are irrational.
- \(p^2 = 4q^2\) gives \(p\) even, \(p = 2k\), then \(4k^2 = 4q^2\), so \(k^2 = q^2\). That tells us nothing about \(q\) being even. The chain stops, no contradiction, and indeed \(p/q = 2/1\) works. With \(\sqrt{2}\), cancelling left a factor 2 on the \(q\) side, forcing \(q\) even. With \(\sqrt{4} = \sqrt{2^2}\), both 2s cancel and nothing is left to force anything.
- Suppose \(\sqrt{3} = p/q\) in lowest terms. Then \(p^2 = 3q^2\), so \(p^2\) is a multiple of 3. If \(p = 3m+1\), \(p^2 = 9m^2 + 6m + 1\), remainder 1. If \(p = 3m+2\), \(p^2 = 9m^2 + 12m + 4\), remainder 1. So \(p\) must be a multiple of 3: \(p = 3k\). Then \(9k^2 = 3q^2\), so \(q^2 = 3k^2\), so by the same argument \(q\) is a multiple of 3. Both divisible by 3 contradicts lowest terms.
Stretch. From \(2^{p/q} = 3\), raising to the power \(q\) gives \(2^p = 3^q\). The left side is a power of 2, so even (since \(p \ge 1\)); the right side is a product of 3s, so odd. Even cannot equal odd. Contradiction, so \(\log_2 3\) is irrational.