6.3 Proof by Contradiction and Counterexamples
AHL 1.15
- the idea of proof by contradiction
- the link between a statement and its contrapositive
- how to prove that numbers such as \(\sqrt{3}\) and \(\log_2 3\) are irrational
- how to prove that there are infinitely many primes
- how to show a statement is false with a counterexample
The idea
In a proof by contradiction we:
- assume the opposite of what we want to prove,
- use correct logical steps from that assumption,
- reach something impossible (a contradiction, such as \(1 = 0\) or “an even number is odd”),
- conclude that the assumption was wrong, so the original statement is true.
Contrapositive Not in the formula booklet
The statement “if \(A\), then \(B\)” (\(A \Rightarrow B\)) is equivalent to its contrapositive “if not \(B\), then not \(A\)” (\(\bar{B} \Rightarrow \bar{A}\)).
For example, “if it is raining, the ground is wet” is equivalent to “if the ground is not wet, it is not raining”.
Proof by contradiction can be used for any kind of statement, not only “if … then” statements. Always say clearly at the start what you are assuming, and at the end, what the contradiction is.
Example 1 Prove by contradiction that if \(n^2\) is a multiple of 3, then \(n\) is a multiple of 3 (\(n \in \mathbb{Z}\)).
Assume, for a contradiction, that \(n^2\) is a multiple of 3 but \(n\) is not a multiple of 3. Then \(n = 3k + 1\) or \(n = 3k + 2\) for some \(k \in \mathbb{Z}\).
\[ \begin{aligned} (3k + 1)^2 &= 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1, \\ (3k + 2)^2 &= 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1 . \end{aligned} \]
In both cases \(n^2\) leaves remainder 1 when divided by 3, so it is not a multiple of 3. This contradicts the assumption. Hence \(n\) is a multiple of 3.
Irrational numbers
A number is rational if it can be written as \(\dfrac{p}{q}\) with \(p, q \in \mathbb{Z}\), \(q \neq 0\). We may always assume the fraction is in lowest terms (no common factor other than 1).
Example 2 Prove that \(\sqrt{3}\) is irrational.
Assume, for a contradiction, that \(\sqrt{3}\) is rational. Then \(\sqrt{3} = \dfrac{p}{q}\), where \(p, q \in \mathbb{Z}\), \(q \neq 0\), and \(p\) and \(q\) have no common factor.
Squaring: \(3 = \dfrac{p^2}{q^2}\), so \(p^2 = 3q^2\).
So \(p^2\) is a multiple of 3, and by Example 1, \(p\) is a multiple of 3. Write \(p = 3m\). Then
\[ 9m^2 = 3q^2 \;\Longrightarrow\; q^2 = 3m^2, \]
so \(q^2\), and therefore \(q\), is also a multiple of 3.
Now \(p\) and \(q\) have the common factor 3. This contradicts “no common factor”. Hence \(\sqrt{3}\) is irrational.
Example 3 Prove that \(\log_2 3\) is irrational.
Assume, for a contradiction, that \(\log_2 3 = \dfrac{p}{q}\) with \(p, q \in \mathbb{Z}^+\) (it is positive, because \(3 > 1\)).
By the definition of a logarithm, \(2^{\frac{p}{q}} = 3\). Raise both sides to the power \(q\):
\[ 2^{p} = 3^{q} . \]
The left side is even (a power of 2 with \(p \ge 1\)). The right side is odd (a product of odd numbers). An even number cannot equal an odd number — a contradiction. Hence \(\log_2 3\) is irrational.
Infinitely many primes
Example 4 Prove that there are infinitely many prime numbers.
Assume, for a contradiction, that there are only finitely many primes: \(p_1, p_2, \ldots, p_k\).
Consider the number \(N = p_1 p_2 \cdots p_k + 1\).
\(N > 1\), so \(N\) has at least one prime factor, and it must be one of \(p_1, \ldots, p_k\), say \(p_i\). But \(p_i\) divides the product \(p_1 p_2 \cdots p_k\), so it would also have to divide \(N - p_1 p_2 \cdots p_k = 1\). No prime divides 1 — a contradiction.
Hence there are infinitely many primes.
Disproof by counterexample
A statement that claims something is true for all cases is disproved by one case where it fails. That case is a counterexample.
For example, “every prime number is odd” is false: \(2\) is prime and even.
Example 5 Show that each statement is false.
(a) \(n^2 + n + 41\) is prime for every positive integer \(n\).
(b) If \(a^2\) is a multiple of 8, then \(a\) is a multiple of 8.
(c) If \(ab\) is rational, then \(a\) and \(b\) are both rational.
(a) It works for \(n = 1, 2, \ldots, 39\), but for \(n = 40\): \(\;1600 + 40 + 41 = 1681 = 41^2\), which is not prime.
(b) \(a = 4\): \(a^2 = 16\) is a multiple of 8, but \(4\) is not.
(c) \(a = b = \sqrt{2}\): \(ab = 2\) is rational, but \(\sqrt{2}\) is not.
Example 5 (a) is a warning: a pattern that works for many cases is still only a conjecture.
Some statements can be settled by checking every possible case (proof by exhaustion).
Example 6 Show that there are no positive integers \(x\) and \(y\) with \(x^2 + y^2 = 7\).
If \(x \ge 3\) then \(x^2 \ge 9 > 7\), so \(x\) and \(y\) can only be \(1\) or \(2\). The possible values of \(x^2 + y^2\) are \(1 + 1 = 2\), \(1 + 4 = 5\) and \(4 + 4 = 8\). None of them is \(7\).
Common errors
| ✗ Wrong | ✓ Right | Why |
|---|---|---|
| Not stating the assumption | “Assume, for a contradiction, that …” | The reader must know what is being contradicted. |
| Forgetting “lowest terms” in an irrationality proof | Say \(p, q\) have no common factor | The contradiction depends on it. |
| Using “if \(p^2\) is a multiple of 3 then so is \(p\)” without proof | Prove it first (Example 1) | Every step must be justified. |
| Stopping at the contradiction | Finish: “hence the statement is true” | State the conclusion. |
| “It works for \(n = 1, 2, 3\), so it is true” | Use a general proof | Examples are not a proof; see Example 5. |
| A counterexample that does not satisfy the “if” part | Check both parts | It must make \(P\) true and \(Q\) false. |
Exercises
1 Write down the contrapositive of “If \(n\) is a multiple of 6, then \(n\) is even.”
“If \(n\) is not even (odd), then \(n\) is not a multiple of 6.”
2 Prove by contradiction that if \(n^2\) is even, then \(n\) is even.
Assume \(n^2\) is even but \(n\) is odd, \(n = 2k + 1\). Then \(n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\) is odd — a contradiction. So \(n\) is even.
3 Prove that \(\sqrt{2}\) is irrational.
Assume \(\sqrt{2} = \dfrac{p}{q}\) in lowest terms. Then \(p^2 = 2q^2\), so \(p^2\) is even and (by Question 2) \(p\) is even: \(p = 2m\). Then \(4m^2 = 2q^2\), \(q^2 = 2m^2\), so \(q\) is even too. Both are even — a contradiction with lowest terms.
4 Prove that \(\log_3 5\) is irrational.
Assume \(\log_3 5 = \dfrac{p}{q}\), \(p, q \in \mathbb{Z}^+\). Then \(3^{p} = 5^{q}\). The left side is a power of 3 and the right side a power of 5; by unique prime factorisation they cannot be equal (for \(p, q \ge 1\), \(3\) divides the left side but not the right). Contradiction.
5 Prove that if \(a\) is rational and \(b\) is irrational, then \(a + b\) is irrational.
Assume \(a + b = c\) is rational. Then \(b = c - a\), the difference of two rationals, which is rational. This contradicts \(b\) irrational. So \(a + b\) is irrational.
6 Hence show that \(3 + \sqrt{2}\) is irrational.
\(3\) is rational and \(\sqrt{2}\) is irrational (Question 3), so by Question 5, \(3 + \sqrt{2}\) is irrational.
7 Prove that there are no integers \(a\) and \(b\) such that \(6a + 9b = 1\).
Assume such integers exist. Then \(1 = 3(2a + 3b)\) is a multiple of 3, which is false. Contradiction.
8 Prove that there is no largest even number.
Assume \(N\) is the largest even number. Then \(N + 2\) is also even and \(N + 2 > N\) — a contradiction.
9 Prove that for \(x > 0\), \(x + \dfrac{1}{x} \ge 2\).
Assume \(x + \dfrac{1}{x} < 2\) for some \(x > 0\). Multiply by \(x > 0\): \(x^2 + 1 < 2x\), so \((x - 1)^2 < 0\). A square cannot be negative — a contradiction.
10 Prove that there are no positive integers \(m\) and \(n\) with \(m^2 - n^2 = 10\).
Assume they exist: \((m - n)(m + n) = 10\). The two factors \(m - n\) and \(m + n\) differ by \(2n\), an even number, so they are both even or both odd. If both odd, the product is odd, not 10. If both even, the product is a multiple of 4, but 10 is not. Contradiction.
11 Find a counterexample to: “If \(x^2 > 4\), then \(x > 2\).”
\(x = -3\): \(x^2 = 9 > 4\), but \(-3 < 2\).
12 Find a counterexample to: “\(2^n + 1\) is prime for every positive integer \(n\).”
\(n = 3\): \(2^3 + 1 = 9 = 3 \times 3\), not prime.
13 Show that the statement “\(\sqrt{a + b} = \sqrt{a} + \sqrt{b}\) for all positive real numbers \(a\) and \(b\)” is false.
\(a = 9\), \(b = 16\): \(\sqrt{25} = 5\), but \(\sqrt{9} + \sqrt{16} = 7\).