Contrapositive and contradiction

Some true statements give a direct proof nothing to work with, because the hypothesis says nothing usable about the thing the conclusion is about.

The previous lesson proved conditionals by assuming the hypothesis and walking forward from definitions, and it ended on a claim that walk cannot finish: for every integer $n$ , if $n^{2}$ is even then $n$ is even. It also used, without proof, the fact that $\sqrt{2}$ is irrational. This lesson pays both debts with two indirect methods, proof by contrapositive and proof by contradiction, proves Euclid's theorem that there are infinitely many primes, and says how to choose a method. It assumes the definitions of even, odd and divisibility: $n$ is even when $n = 2 k$ for some integer $k$ , odd when $n = 2 k + 1$ , and $a ∣ b$ when $b = a k$ for some integer $k$ .

Turning the conditional round

The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$ , and a truth table shows the two are true in exactly the same rows. So a proof of the contrapositive is a proof of the original, not an approximation to one. A proof by contrapositive is a direct proof aimed at that equivalent statement: assume $\neg Q$ , and reach $\neg P$ .

What makes the swap worth doing is that negation can turn a useless hypothesis into a useful one. " $n^{2}$ is even" gives $n^{2} = 2 k$ , and there is no way back through the square to $n$ . Its partner in the contrapositive is " $n$ is not even", which, because every integer is even or odd and none is both, means " $n$ is odd", and that gives $n = 2 k + 1$ , a formula for $n$ itself. Squaring a formula is easy. Unsquaring a fact is not.

Example. Prove that for every integer $n$ , if $n^{2}$ is even then $n$ is even.

We prove the contrapositive: for every integer $n$ , if $n$ is not even then $n^{2}$ is not even. Let $n$ be an integer that is not even. Since every integer is even or odd, $n$ is odd, so $n = 2 k + 1$ for some integer $k$ . Then $n^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1$ . Since $2 k^{2} + 2 k$ is an integer, $n^{2}$ is odd, and since no integer is both odd and even, $n^{2}$ is not even. This proves the contrapositive, and therefore the original statement.

The first sentence is not decoration. Without it, the proof looks like a proof of the converse, and a careful reader will wonder whether the writer has confused the two.

Now you. Prove that for every integer $n$ , if $3 ∣ n^{2}$ then $3 ∣ n$ . (Use the fact that every integer is of the form $3 k$ , $3 k + 1$ or $3 k + 2$ for some integer $k$ .)

Answer

We prove the contrapositive: if $3$ does not divide $n$ then $3$ does not divide $n^{2}$ . Let $n$ be an integer not divisible by $3$ . Then $n = 3 k + 1$ or $n = 3 k + 2$ for some integer $k$ . In the first case $n^{2} = 9 k^{2} + 6 k + 1 = 3 (3 k^{2} + 2 k) + 1$ , and in the second $n^{2} = 9 k^{2} + 12 k + 4 = 3 (3 k^{2} + 4 k + 1) + 1$ . Either way $n^{2}$ leaves remainder $1$ on division by $3$ , so $3$ does not divide $n^{2}$ . This proves the contrapositive, and so the claim.

Assuming the opposite

A proof by contradiction proves a statement $Q$ by assuming $\neg Q$ and deriving something impossible: a statement together with its negation. The justification is one row of a truth table. The conditional $\neg Q \Rightarrow (R \land \neg R)$ has a conclusion that is false in every row, so if the conditional has been proved, its hypothesis must be false too. And $\neg Q$ false means $Q$ true.

For a conditional $P \Rightarrow Q$ , the thing to assume is its negation, which is $P \land \neg Q$ . So the proof starts with two assumptions rather than one: everything the direct proof had, plus the negated conclusion as a further fact to use.

The method is old. Aristotle, in the Prior Analytics of the fourth century BCE, gives as his standard example of reasoning "to the impossible" the proof that the diagonal of a square cannot be measured by its side, since otherwise odd numbers would equal even ones: the next proof in this lesson.

The contrapositive is a special case: if the argument uses $\neg Q$ to reach $\neg P$ , that contradicts the assumed $P$ . The difference is the destination. A contrapositive proof has a fixed target, $\neg P$ , while a proof by contradiction may end at any impossibility at all.

The square root of two

A real number is rational if it equals $\frac{a}{b}$ for some integers $a$ and $b$ with $b \neq 0$ , and irrational otherwise. "Irrational" is a negative: no pair of integers, out of infinitely many, has a certain property. Contradiction assumes one pair exists and extracts an impossibility from it, a single argument about a single, arbitrary pair.

Approximations show why checking cannot settle it. The fraction $\frac{99}{70}$ gives $99^{2} = 9801$ against $2 \times 70^{2} = 9800$ , and $\frac{577}{408}$ gives $577^{2} = 332 929$ against $2 \times 408^{2} = 332 928$ . The gap is one each time, and no amount of searching can show that it never closes.

Example. Prove that $\sqrt{2}$ is irrational.

Suppose, for contradiction, that $\sqrt{2}$ is rational, so $\sqrt{2} = \frac{a}{b}$ for some integers $a$ and $b$ with $b \neq 0$ . If $a$ and $b$ are both even, cancel a factor of $2$ from each; the denominator shrinks in size each time, so this must stop, and we may assume that $a$ and $b$ are not both even. Squaring $\sqrt{2} = \frac{a}{b}$ and multiplying by $b^{2}$ gives $a^{2} = 2 b^{2}$ , so $a^{2}$ is even. By the result proved above, $a$ is even, so $a = 2 c$ for some integer $c$ . Substituting, $4 c^{2} = 2 b^{2}$ , so $b^{2} = 2 c^{2}$ , and $b^{2}$ is even. By the same result, $b$ is even. So $a$ and $b$ are both even, which contradicts the choice of $a$ and $b$ . Hence $\sqrt{2}$ is not rational.

A proof that proves too much is wrong, so why does it not show $\sqrt{4}$ irrational? Run it with $4$ : from $a^{2} = 4 b^{2}$ the next step would need "if $4 ∣ a^{2}$ then $4 ∣ a$ ", and that is false, since $4 ∣ 36$ while $4$ does not divide $6$ . The proof for $2$ works because $2$ is prime, and it breaks exactly where it should.

Now you. Prove that $\sqrt{3}$ is irrational, using the result from the first Now you: if $3 ∣ n^{2}$ then $3 ∣ n$ .

Answer

Suppose, for contradiction, that $\sqrt{3} = \frac{a}{b}$ for integers $a$ and $b$ with $b \neq 0$ . Cancelling factors of $3$ from both as long as both are divisible by $3$ , which must stop because the denominator shrinks in size, we may assume $a$ and $b$ are not both divisible by $3$ . Squaring gives $a^{2} = 3 b^{2}$ , so $3 ∣ a^{2}$ , and therefore $3 ∣ a$ . Write $a = 3 c$ . Then $9 c^{2} = 3 b^{2}$ , so $b^{2} = 3 c^{2}$ and $3 ∣ b^{2}$ , hence $3 ∣ b$ . So $3$ divides both $a$ and $b$ , contradicting the choice of $a$ and $b$ . Hence $\sqrt{3}$ is irrational.

The primes never run out

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ . The primes thin out, from a quarter of the numbers up to $100$ to about one in thirteen of those up to a million, so whether they stop is a real question. Around 300 BCE Euclid answered it in Book IX of the Elements, Proposition 20. The proof needs one preliminary fact.

Every integer $N > 1$ has a prime divisor. Among the divisors of $N$ that are greater than $1$ there is at least one, $N$ itself, and there are only finitely many candidates between $2$ and $N$ , so there is a smallest; call it $d$ . Suppose, for contradiction, that $d$ is not prime. Then $d = r s$ for some integers with $1 < r < d$ . Now $r ∣ d$ and $d ∣ N$ , so $r ∣ N$ by the transitivity of divisibility from the previous lesson. That makes $r$ a divisor of $N$ greater than $1$ and smaller than $d$ , contradicting the choice of $d$ . So $d$ is prime.

Example. Prove that there are infinitely many primes.

Suppose, for contradiction, that there are only finitely many, and list all of them as $p_{1}, p_{2}, \dots, p_{k}$ . Let $N = p_{1} p_{2} \dots p_{k} + 1$ . Then $N > 1$ , so by the preliminary fact $N$ has a prime divisor $p$ . Since the list contains every prime, $p$ is one of $p_{1}, \dots, p_{k}$ , and so $p$ divides the product $p_{1} p_{2} \dots p_{k}$ . It also divides $N$ . A number dividing two integers divides their difference (from the previous lesson), so $p ∣ N - p_{1} p_{2} \dots p_{k}$ , that is, $p ∣ 1$ . But $p > 1$ , and no integer greater than $1$ divides $1$ . This contradiction shows the primes are not finite in number.

Now you. Prove directly that for every positive integer $n$ there is a prime greater than $n$ . (Consider a prime divisor of $n! + 1$ .)

Answer

Let $n$ be a positive integer. Since $n! + 1 > 1$ , it has a prime divisor $p$ . If $p \leq n$ , then $p$ is one of the factors $1, 2, \dots, n$ of $n!$ , so $p ∣ n!$ ; as also $p ∣ n! + 1$ , it would follow that $p ∣ 1$ , which is impossible. So $p > n$ . For $n = 6$ , $6! + 1 = 721 = 7 \times 103$ , and both prime factors exceed $6$ . The proof uses a small contradiction to locate $p$ , but it never assumes the primes are finite: it produces a larger prime from any $n$ .

What Euclid's proof does not say

A common retelling runs: multiply the primes together, add one, and the result is a new prime. The proof says something weaker, that $N$ has a prime divisor not on the list, and the retelling is false. The first cases make it look right: $2 + 1 = 3$ , $2 \times 3 + 1 = 7$ , then $31$ , $211$ and $2311$ , all prime. The sixth breaks it:

2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30 031 = 59 \times 509

Neither $59$ nor $509$ is among the primes from $2$ to $13$ , exactly as the proof promises. The new prime is a divisor of $N$ , not $N$ itself.

Nor did Euclid assume the primes were finite. His proposition reads "prime numbers are more than any assigned multitude of prime numbers": given any finite collection of primes, their product plus one either is prime or has a prime divisor, and the divisibility argument shows that divisor is not in the collection. That proves more than the textbook version, since it turns any finite list into a new prime.

Choosing a method

Try the direct route first. When it stalls, look at the shape of the statement. If it is a conditional whose hypothesis gives nothing to manipulate while the negation of its conclusion gives a formula, as " $n^{2}$ is even" against " $n$ is odd", use the contrapositive. If the statement is a negative with no hypothesis to start from, "is irrational", "there is no largest", "there are infinitely many", use contradiction, since assuming the positive version hands the proof an object to work on.

The claim that $\log_{2} 3$ is irrational shows the second shape. Suppose $\log_{2} 3 = \frac{p}{q}$ with $p$ and $q$ positive integers (positive because $\log_{2} 3 > 0$ ). Then $2^{\frac{p}{q}} = 3$ , so $2^{p} = 3^{q}$ . The left side is even and the right side is a product of odd numbers, hence odd, and no integer is both.

Prefer the contrapositive when both methods work. Its target, $\neg P$ , is fixed in advance, so a mistake usually shows as a failure to arrive. A proof by contradiction accepts any impossibility, including one produced by an algebra slip, so a wrong one can look exactly like a right one.

Contradictions in disguise

Many proofs by contradiction are something else wearing its opening sentence. The test is to delete "suppose, for contradiction" and ask whether the assumption was ever used. Consider: "Suppose, for contradiction, that the sum of odd integers $a$ and $b$ is odd. Write $a = 2 k + 1$ and $b = 2 m + 1$ . Then $a + b = 2 (k + m + 1)$ , which is even, a contradiction." The assumed oddness of $a + b$ did nothing until the last word. Strip the wrapper and what remains is a direct proof that $a + b$ is even.

The second disguise hides a contrapositive. "Suppose $n^{2}$ is even and $n$ is odd. Then $n = 2 k + 1$ , so $n^{2}$ is odd, contradicting $n^{2}$ even." The hypothesis appears only in the final clash; the work ran from $\neg Q$ to $\neg P$ . Writing it as a contrapositive says the same thing with fewer assumptions in the air.

The textbook proof of Euclid's theorem is the third: its argument works on any finite list, so the assumption that the list held every prime was never needed. Removing a disguise improves a proof. Every line becomes true, rather than true only in an impossible world about to collapse, and a stronger or constructive result often appears.

What none of these methods can do

Every proof in this lesson and the previous one handled infinitely many integers by one argument about an arbitrary integer. Some claims do not yield to that. Take "every integer $n \geq 2$ is a product of primes". For an arbitrary $n$ , either $n$ is prime, or $n = a b$ with $a$ and $b$ smaller than $n$ ; to finish, the proof needs $a$ and $b$ to be products of primes already, which is the claim for smaller numbers. The argument for each $n$ leans on the cases below it, and checking them one by one never ends. The next lesson supplies the method that follows such a chain all the way up: induction.