Proof techniques II: contradiction, cases and existence

Direct proof and the contrapositive handle many theorems, but some statements resist them. This lesson adds three more tools. Proof by contradiction shows that assuming a statement is false leads to an impossibility. Proof by cases splits a problem into parts that are each easier. Existence and uniqueness proofs show that an object exists, sometimes by building it and sometimes without ever finding it, and that there is only one. Two famous theorems, the irrationality of \(\sqrt{2}\) and the infinitude of the primes, show contradiction at its best.

Proof by contradiction

To prove a statement \(S\) by contradiction, assume \(\neg S\) and derive a contradiction: a statement of the form \(R \wedge \neg R\), which can never be true. Since a true assumption cannot lead to a false conclusion by valid steps, the assumption \(\neg S\) must be false, so \(S\) is true. In symbols, \((\neg S \to F) \equiv S\), which you can check with a two-row truth table.

Contradiction is especially useful for statements that say something does not exist or that a quantity is not of some form: there is no largest prime, \(\sqrt{2}\) is not rational, no algorithm solves every instance of some problem. Negating such a statement gives you something concrete to work with: a largest prime, a fraction equal to \(\sqrt{2}\), an algorithm.

This proof, known to the ancient Greeks, is one of the oldest in mathematics. Look closely at its structure. The assumption gave us concrete integers \(a\) and \(b\). The extra condition, lowest terms, was free to impose because every fraction can be reduced, and it became the statement that was contradicted. Many contradiction proofs work this way: assume a smallest, largest or simplest counterexample, then produce a smaller, larger or simpler one.

A common misreading of Euclid's proof is that \(N\) itself must be prime. It need not be: \(2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509\). What the proof shows is that \(N\) has a prime factor not in the list. Python can check both the claim and the misreading.

def smallest_factor(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d
        d += 1
    return n

primes = [2, 3, 5, 7, 11, 13]
prod = 1
for i, p in enumerate(primes):
    prod *= p
    N = prod + 1
    f = smallest_factor(N)
    status = "prime" if f == N else f"composite, factor {f}"
    print(f"product of first {i+1} primes + 1 = {N:6d}: {status}; new prime factor {f} not in list: {f not in primes[:i+1]}")

product of first 1 primes + 1 =      3: prime; new prime factor 3 not in list: True
product of first 2 primes + 1 =      7: prime; new prime factor 7 not in list: True
product of first 3 primes + 1 =     31: prime; new prime factor 31 not in list: True
product of first 4 primes + 1 =    211: prime; new prime factor 211 not in list: True
product of first 5 primes + 1 =   2311: prime; new prime factor 2311 not in list: True
product of first 6 primes + 1 =  30031: composite, factor 59; new prime factor 59 not in list: True

Contradiction versus contrapositive

Proof by contrapositive and proof by contradiction look similar, since both begin by assuming something is false. The difference is in what you aim for. In a contrapositive proof of \(P \to Q\), you assume \(\neg Q\) and aim specifically for \(\neg P\). In a contradiction proof of \(P \to Q\), you assume both \(P\) and \(\neg Q\) and aim for any contradiction at all. Contradiction is more flexible, because any impossibility will do; contrapositive is more focused and often clearer. If a contradiction proof ends by contradicting the hypothesis \(P\), it can usually be rewritten as a cleaner contrapositive proof.

Proof by cases

Sometimes a hypothesis naturally splits into several situations, and each is easier to handle on its own. If \(P \equiv P_1 \vee P_2 \vee \cdots \vee P_k\) and you prove \(P_i \to Q\) for every \(i\), then \(P \to Q\) follows. The cases must be exhaustive, meaning they cover every possibility; they do not have to be exclusive, though usually they are.

With a finite number of cases, a computer can check every case directly. This is called proof by exhaustion, and it is completely rigorous when the cases really are finite. A famous example is the Four Color Theorem: every map can be colored with four colors so that neighboring regions differ. Kenneth Appel and Wolfgang Haken proved it in 1976 by reducing it to 1,936 configurations checked by computer. A smaller example is checking a claim about remainders.

# Proof by exhaustion over remainders: n**2 mod 8 depends only on n mod 8,
# so checking the 8 residues proves the claim for every integer n.
squares = sorted({(r * r) % 8 for r in range(8)})
print("possible values of n^2 mod 8:", squares)
odd_squares = sorted({(r * r) % 8 for r in range(1, 8, 2)})
print("possible values of n^2 mod 8 for odd n:", odd_squares)

possible values of n^2 mod 8: [0, 1, 4]
possible values of n^2 mod 8 for odd n: [1]

This program is a proof, not just evidence, because of the argument in its comment: the remainder of \(n^2\) modulo 8 depends only on the remainder of \(n\) modulo 8, and there are only eight remainders. Lesson 11 explains why this holds. The general lesson is that a computer check proves a universal claim only when you can show the infinite domain reduces to finitely many cases.

Existence proofs

To prove \(\exists x\, P(x)\), the most satisfying method is a constructive proof: exhibit a specific \(x\), or give an algorithm that finds one, and verify \(P(x)\). A non-constructive proof shows that some \(x\) must exist without identifying which one, often by contradiction or by cases.

Computer scientists generally prefer constructive proofs because a construction is an algorithm. A proof that a schedule exists is useful; a proof that also builds the schedule is far more useful. Some mathematicians, the constructivists, accept only constructive existence proofs, and proof assistants based on constructive logic can extract working programs from proofs.

Uniqueness proofs

A uniqueness claim \(\exists! x\, P(x)\) has two parts. Existence: some \(x\) has property \(P\). Uniqueness: if \(x\) and \(y\) both have property \(P\), then \(x = y\). The uniqueness part is usually proved by assuming two objects with the property and showing they are equal.

Common fallacies in proofs

Learning to spot errors is as important as learning to write proofs. The fake proofs below each contain a single flaw. Finding the flaw sharpens your sense of what a valid step requires.