Proof by contrapositive and contradiction

Some statements resist a direct attack. Try proving 'if \(n^2\) is even, then \(n\) is even' directly: you know \(n^2 = 2k\), and you want \(n = 2j\), but taking a square root of \(2k\) leads nowhere. The trouble is that the hypothesis gives information about \(n^2\), while the conclusion is about \(n\) itself. Two indirect methods get around this kind of obstacle. Proof by contrapositive proves an equivalent statement in which the information flows the easy way. Proof by contradiction assumes the statement is false and shows that this assumption leads to something impossible. Between them they handle some of the most famous theorems in mathematics, including the irrationality of \(\sqrt{2}\) and the infinitude of the primes.

Proof by contrapositive

Lesson 2 showed that \(P \implies Q\) is logically equivalent to its contrapositive \(\neg Q \implies \neg P\). So to prove \(P \implies Q\) it is enough to prove \(\neg Q \implies \neg P\) directly: assume \(Q\) is false and deduce that \(P\) is false. Announce the method at the start, so the reader knows why you are assuming the negation of the conclusion.

Theorem. Let \(n\) be an integer. If \(n^2\) is even, then \(n\) is even.

Proof. We prove the contrapositive: if \(n\) is odd, then \(n^2\) is odd. Suppose \(n\) is odd, so \(n = 2k + 1\) for some integer \(k\). Then \(n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\), which is odd. This proves the contrapositive, and hence the theorem. \(\blacksquare\)

The contrapositive turned an awkward square root into an easy square. That is the typical signal to use this method: when the negation of the conclusion gives you something concrete to compute with, and the negation of the hypothesis is easy to recognize. Statements whose conclusion is itself a negation, such as 'then \(n\) is not divisible by 5' or 'then \(x\) is irrational', are often good candidates, because the negated conclusion becomes a positive statement you can unpack.

Proof by contradiction

A proof by contradiction of a statement \(S\) assumes \(\neg S\) and deduces a contradiction, that is a statement of the form \(R \wedge \neg R\). Since a contradiction cannot be true, the assumption \(\neg S\) must be false, so \(S\) is true. The logic is the tautology \((\neg S \implies (R \wedge \neg R)) \implies S\), which you can check with a truth table.

The method is extremely flexible. It works for statements of any form, not just conditionals, and you do not need to know in advance which contradiction you are heading for. When \(S\) is a conditional \(P \implies Q\), the negation is \(P \wedge \neg Q\), so you assume both the hypothesis and the negation of the conclusion, which gives you twice as much to work with as a direct proof.

Write proofs by contradiction carefully. Begin with 'Suppose, for contradiction, that …' and state the negation precisely. End by pointing out the contradiction and concluding that the assumption was false. The mathematician G. H. Hardy called proof by contradiction 'one of a mathematician's finest weapons', remarking that it is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game.

The square root of 2 is irrational

The most famous proof by contradiction is attributed to the Pythagorean school of ancient Greece. Its discovery that the diagonal of a unit square cannot be measured as a ratio of whole numbers was a shock to a philosophy built on whole numbers.

Theorem. \(\sqrt{2}\) is irrational.

Proof. Suppose, for contradiction, that \(\sqrt{2}\) is rational. Then \(\sqrt{2} = a/b\) for some integers \(a\) and \(b\) with \(b \ne 0\). By canceling common factors we may assume the fraction is in lowest terms, so \(a\) and \(b\) have no common factor greater than 1. Squaring gives \(2 = a^2/b^2\), so \(a^2 = 2b^2\). Thus \(a^2\) is even, and by the theorem proved above \(a\) is even, say \(a = 2c\). Substituting, \(4c^2 = 2b^2\), so \(b^2 = 2c^2\). Thus \(b^2\) is even, so \(b\) is even. Now both \(a\) and \(b\) are even, so 2 is a common factor, contradicting the assumption that \(a/b\) is in lowest terms. Hence \(\sqrt{2}\) is irrational. \(\blacksquare\)

Look at the structure. The assumption was \(\neg S\): \(\sqrt{2}\) is rational. The contradiction was \(R \wedge \neg R\), where \(R\) is 'a and b have no common factor greater than 1'. We chose to put the fraction in lowest terms precisely so that this contradiction would be available. The proof also used an earlier theorem, that \(n^2\) even implies \(n\) even, which was itself proved by contrapositive. Chains like this are how mathematics is built.

The same argument shows that \(\sqrt{p}\) is irrational for every prime \(p\), once you know that \(p \mid n^2\) implies \(p \mid n\), which is Euclid's lemma. A different argument shows that \(\sqrt{n}\) is irrational whenever the positive integer \(n\) is not a perfect square. Those generalizations appear in the practice problems and in MATH-351.

There are infinitely many primes

Euclid's Elements, Book IX, Proposition 20, contains a proof that there are more primes than any given finite collection. It is usually presented by contradiction, as follows. We use one fact: every integer greater than 1 has a prime divisor. (This is proved by strong induction in lesson 8; the idea is that the smallest divisor greater than 1 of a number must be prime.)

Theorem. There are infinitely many prime numbers.

Proof. Suppose, for contradiction, that there are only finitely many primes, and list them all as \(p_1, p_2, \dots, p_k\). Consider \(N = p_1 p_2 \cdots p_k + 1\). Since \(N > 1\), it has a prime divisor \(p\). That prime must be one of the \(p_i\), because the list contains every prime. So \(p \mid p_1 p_2 \cdots p_k\) and \(p \mid N\). Then \(p\) divides the difference \(N - p_1 p_2 \cdots p_k = 1\). But no prime divides 1, since primes are greater than 1. This contradiction shows that there are infinitely many primes. \(\blacksquare\)

A common misreading is that \(N = p_1 p_2 \cdots p_k + 1\) is always prime. It need not be. With the first six primes, \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509\). The proof only needs \(N\) to have a prime factor missing from the list, and both 59 and 509 are missing from \(\{2, 3, 5, 7, 11, 13\}\). In fact Euclid's own argument is constructive: from any finite list of primes it produces a prime not on the list, so it is closer to a direct proof than the contradiction format suggests.

Choosing a method

For a conditional \(P \implies Q\) you now have three methods, and they assume different things.

Try direct proof first. If the hypothesis is hard to use but the negated conclusion is concrete, try contrapositive. If the statement says something does not exist, is not rational, cannot happen or is infinite, try contradiction: assume the thing does exist, is rational, does happen or is finite, and look for trouble. A proof by contradiction that ends by deducing \(\neg P\) from \(P \wedge \neg Q\) is really a contrapositive proof in disguise, and it is cleaner to present it as one.

Contradiction has a cost. Inside a proof by contradiction you are reasoning from a false assumption, so every intermediate statement may be false, and it is harder for the reader to check that each step is sound. Errors are also easier to hide: if you make an algebra mistake, you may 'reach a contradiction' that is really just your mistake. Use contradiction when it genuinely helps.

Irrational numbers and a surprise

Contradiction proofs often combine with closure properties. For example: if \(x\) is irrational and \(r\) is rational, then \(x + r\) is irrational. Proof: suppose, for contradiction, that \(x + r\) is rational. Then \(x = (x + r) - r\) is a difference of two rationals, which is rational by lesson 4, contradicting the irrationality of \(x\). So \(\sqrt{2} + 3\), \(\sqrt{2} - 1/7\) and every rational shift of an irrational number are irrational.

Here is a famous short argument with a twist. Claim: there exist irrational numbers \(a\) and \(b\) such that \(a^b\) is rational. Consider \(\sqrt{2}^{\sqrt{2}}\). Either it is rational or it is irrational. If it is rational, take \(a = b = \sqrt{2}\) and we are done. If it is irrational, take \(a = \sqrt{2}^{\sqrt{2}}\) and \(b = \sqrt{2}\); then \(a^b = \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}} = \sqrt{2}^2 = 2\), which is rational. Either way the claim holds. The proof shows that a pair exists without telling us which pair, a non-constructive existence proof. (A deep theorem of Gelfond and Schneider from 1934 shows that \(\sqrt{2}^{\sqrt{2}}\) is in fact irrational, so the second case is the true one.)

Experimenting with Euclid's argument

The code below builds Euclid's number \(N = p_1 \cdots p_k + 1\) from the first \(k\) primes and factors it. Every prime factor it finds is new, exactly as the proof predicts, even when \(N\) itself is composite. It also searches for fractions close to \(\sqrt{2}\), showing that \(a^2 - 2b^2\) is never zero, only close to it.

def is_prime(m):
    return m > 1 and all(m % d for d in range(2, int(m ** 0.5) + 1))

def factor(n):
    out, d = [], 2
    while d * d <= n:
        while n % d == 0:
            out.append(d)
            n //= d
        d += 1
    if n > 1:
        out.append(n)
    return out

primes = [p for p in range(2, 40) if is_prime(p)]
for k in range(1, 9):
    P = primes[:k]
    N = 1
    for p in P:
        N *= p
    N += 1
    f = factor(N)
    print(f"k={k}: N={N:>10}  factors={f}  any factor already listed? {any(q in P for q in f)}")

# a^2 - 2 b^2 is never 0, but can be +1 or -1 (good approximations to sqrt 2)
best = [(a, b, a*a - 2*b*b) for b in range(1, 200) for a in [round(b * 2 ** 0.5)] if abs(a*a - 2*b*b) == 1]
print("fractions a/b with a^2 - 2b^2 = +-1:", [f"{a}/{b}" for a, b, _ in best[:6]])

k=1: N=         3  factors=[3]  any factor already listed? False
k=2: N=         7  factors=[7]  any factor already listed? False
k=3: N=        31  factors=[31]  any factor already listed? False
k=4: N=       211  factors=[211]  any factor already listed? False
k=5: N=      2311  factors=[2311]  any factor already listed? False
k=6: N=     30031  factors=[59, 509]  any factor already listed? False
k=7: N=    510511  factors=[19, 97, 277]  any factor already listed? False
k=8: N=   9699691  factors=[347, 27953]  any factor already listed? False
fractions a/b with a^2 - 2b^2 = +-1: ['1/1', '3/2', '7/5', '17/12', '41/29', '99/70']

The fractions 3/2, 7/5, 17/12, 41/29 and so on are the best rational approximations to \(\sqrt{2}\), and they satisfy \(a^2 - 2b^2 = \pm 1\). They get as close as you like, but the proof above guarantees that \(a^2 - 2b^2\) can never be exactly 0.