Proof by contraposition
How do you prove “if n^2 - 6n + 5 is even, then n is odd”, when knowing that n^2 - 6n + 5 is even says almost nothing you can use about n itself?
Where you are 14 in Proof techniques
When you reach for it
To prove “if P, then Q” directly, you assume P and work toward Q (direct proof). That works when P hands you something to calculate with. Often it does not. “If n^2 - 6n + 5 is even, then n is odd” gives n^2 - 6n + 5 = 2k, an equation with n buried inside a quadratic, and nothing in it says how to write n as 2m + 1. Run the other way and the work is easy: start from n, a single letter with a definition, and compute.
A conditional and its contrapositive \neg Q \to \neg P are logically equivalent (a conditional and its contrapositive), so a direct proof of the contrapositive is a proof of the original. That is proof by contraposition. Reach for it when
- the conclusion is about a simple object, such as one variable, and the hypothesis is about a combination of it, so the reasoning wants to run from the simple object to the combination;
- the hypothesis is negative (“is not divisible by”, “is irrational”, \ne), which gives nothing to compute with, while its negation is positive and does;
- the conclusion is an “or”, which is hard to aim at, while its negation is an “and”, which hands over two facts at once.
It is the proof-writing form of modus tollens: whenever Q fails, so does P.
The procedure
The write-up
A proof by contraposition has four parts, and the reader must be able to see each one.
Say what you are doing. Open with “We prove the contrapositive”, with the contrapositive written out in full. The reader then knows that the first assumption is \neg Q, not P, and can check that the statement proved really is the contrapositive.
Negate both parts exactly. This is logic, done before any mathematics, and the method stands or falls on it. The table lists the negations these proofs use most. For an integer, “not odd” is “even” because every integer is exactly one of the two (even and odd integers).
| Statement | Its negation |
|---|---|
| n is odd | n is even (for an integer n) |
| x < c | x \ge c (for real x) |
| x \ne c | x = c |
| d \nmid m | d \mid m |
| x is irrational | x is rational (for real x) |
| A and B | not A, or not B |
| A or B | not A, and not B |
| for every t, A(t) | for some t, not A(t) |
The last three rows are De Morgan’s laws and the rule for negating a quantified statement. “Or” is inclusive throughout, so the negation of “a is even or b is even” is “a is odd and b is odd”.
Prove \neg Q \to \neg P directly. Assume \neg Q, unfold it with definitions, compute, and arrive at \neg P. Nothing about P is assumed anywhere in this part.
Close by naming the original. State \neg P, say that the contrapositive is therefore proved and with it the original claim, and mark the end with \square (how a proof ends).
Inside a “for every”
Most claims carry a quantifier: “for every integer n, if P(n), then Q(n)”. The quantifier is not part of the conditional and is not negated. Contraposition acts on the conditional inside:
For each single n the two conditionals have the same truth value, so one holds for every n exactly when the other does. The proof still begins “Let n be any integer” and then assumes \neg Q(n). A quantifier inside P or Q is different: it is part of the statement being negated, and it flips (Example 7).
Worked examples
The lesson is taught in two parts. Examples 1 to 3 belong to the first: claims about integers, written up in full, with negations that need De Morgan’s laws. Examples 4 to 7 belong to the second: divisibility and real numbers, choosing a method, and a quantifier inside the hypothesis.
An expression and a variable
Prove: for every integer n, if n^2 - 6n + 5 is even, then n is odd.
SolutionA direct proof would start from n^2 - 6n + 5 = 2k and have to extract the parity of n from it. The contrapositive runs the easy way. The negation of “n is odd” is “n is even”, since every integer is one or the other and not both, and the negation of “n^2 - 6n + 5 is even” is “n^2 - 6n + 5 is odd”. So the contrapositive is: for every integer n, if n is even, then n^2 - 6n + 5 is odd.
Proof. We prove the contrapositive. Let n be an integer, and suppose n is even, so n = 2k for some integer k. Then
Since 2k^2 - 6k + 2 is an integer (sums and products of integers are integers), n^2 - 6n + 5 is odd. This proves the contrapositive, and so for every integer n, if n^2 - 6n + 5 is even, then n is odd. \square
Check. n = 3 gives 9 - 18 + 5 = -4, even, and 3 is odd. n = 4 gives -3, odd, a case the claim says nothing about.
An “or” in the conclusion
Prove: for all integers a and b, if a^2 + ab + b^2 is even, then a is even or b is even.
SolutionAiming at an “or” is awkward: which of the two should a direct proof try to reach? By De Morgan’s laws its negation is “a is odd and b is odd”, two facts to use at once. The contrapositive: for all integers a and b, if a is odd and b is odd, then a^2 + ab + b^2 is odd.
Proof. We prove the contrapositive. Let a and b be odd integers, so a = 2k + 1 and b = 2m + 1 for some integers k and m. Two letters are needed, because a and b need not be equal. Then
where s = 2k^2 + 2km + 2m^2 + 3k + 3m + 1 is an integer, so a^2 + ab + b^2 is odd. The contrapositive holds, and therefore if a^2 + ab + b^2 is even, then a is even or b is even. \square
The converse fails: a = 2 and b = 1 give a^2 + ab + b^2 = 7, odd, although a is even. And the claim is weaker than the truth; Exercise 9 shows that both must be even.
An “and” in the conclusion
Prove: for all integers x and y, if x^2 + xy is odd, then x is odd and y is even.
SolutionThe negation of “x is odd and y is even” is “x is not odd or y is not even”, that is, “x is even or y is odd”. The contrapositive: for all integers x and y, if x is even or y is odd, then x^2 + xy is even. An “or” as the assumption can hold in more than one way, and the proof must cover every way. Factoring helps: x^2 + xy = x(x + y), and a product with an even factor 2t is 2 times an integer, so it is even.
Proof. We prove the contrapositive. Let x and y be integers with x even or y odd. If x is even, the factor x of x^2 + xy = x(x + y) is even, so x^2 + xy is even. If x is not even, then x is odd, and the assumption says y is odd. Writing x = 2k + 1 and y = 2m + 1, x + y = 2(k + m + 1), so the factor x + y is even and again x^2 + xy is even. Either way x^2 + xy is even, which proves the contrapositive and with it the claim. \square
Splitting on “is x even?” covers every integer exactly once; such splits are the subject of proof by cases.
Divisibility, and De Morgan again
Prove: for all integers a and b, if 3 \nmid a^2 - b^2, then 3 \nmid a - b and 3 \nmid a + b.
SolutionBoth parts are negative, and “3 \nmid a^2 - b^2” gives nothing to write down: there is no formula for “not a multiple”. Negated, both turn positive. The negation of “3 \nmid a - b and 3 \nmid a + b” is “3 \mid a - b or 3 \mid a + b”, and the contrapositive is: for all integers a and b, if 3 \mid a - b or 3 \mid a + b, then 3 \mid a^2 - b^2. Recall that d \mid m means m = dk for some integer k (divisibility), and that a^2 - b^2 = (a - b)(a + b).
Proof. We prove the contrapositive. Let a and b be integers with 3 \mid a - b or 3 \mid a + b. If 3 \mid a - b, then a - b = 3k for some integer k, so a^2 - b^2 = 3k(a + b) with k(a + b) an integer, and 3 \mid a^2 - b^2. If 3 \mid a + b, then a + b = 3m for some integer m, so a^2 - b^2 = 3m(a - b), and again 3 \mid a^2 - b^2. The contrapositive holds, so if 3 \nmid a^2 - b^2, then 3 \nmid a - b and 3 \nmid a + b. \square
Each case is the multiple rule (proving statements about divisibility) applied to one factor. The converse, “if 3 \nmid a - b and 3 \nmid a + b, then 3 \nmid a^2 - b^2”, is also true, because 3 is prime; that fact is stated here without proof. With 4 in place of 3 the converse is false: a = 2 and b = 0 give a - b = a + b = 2, and 4 \nmid 2, yet 4 \mid a^2 - b^2 = 4.
Integers or real numbers
Prove that for all integers a and b, if a + b \ge 15, then a \ge 8 or b \ge 8. Then decide whether the same statement holds for all real numbers a and b.
SolutionThe negation of “a \ge 8 or b \ge 8” is “a < 8 and b < 8”, and the negation of a + b \ge 15 is a + b < 15.
Proof. We prove the contrapositive: for all integers a and b, if a < 8 and b < 8, then a + b < 15. Let a and b be integers with a < 8 and b < 8. No integer lies strictly between 7 and 8, so a \le 7 and b \le 7. Adding the two inequalities, a + b \le 14 < 15. The contrapositive holds, and so does the claim. \square
For real numbers the step “less than 8, so at most 7” is not available, and adding a < 8 and b < 8 gives only a + b < 16. The gap between 15 and 16 is where a counterexample lives: a = b = 7.5 gives a + b = 15, and neither number is at least 8. So for real numbers the statement is false. The figure shows both facts.
The contrapositive argument does prove the version with 16 for real numbers: if a + b \ge 16, then a \ge 8 or b \ge 8.
Choosing the method
For each claim, decide whether to prove it directly, by contraposition or by contradiction, and prove it.
(a) For every integer n, if 4 \mid n - 1, then 8 \mid n^2 - 1.
(b) For every integer n, if 8 \nmid n^2 - 1, then 4 \nmid n - 1.
(c) For every positive integer n, \displaystyle \sqrt{n^2 + 1} is not an integer.
SolutionAsk which statement hands the proof something to compute with.
(a) The hypothesis is positive and says what n is, n - 1 = 4k, and the conclusion is about an expression in n. Go directly.
Proof. Let n be an integer with 4 \mid n - 1, so n = 4k + 1 for some integer k. Then n^2 - 1 = 16k^2 + 8k, which is 8(2k^2 + k), and 2k^2 + k is an integer, so 8 \mid n^2 - 1. \square
(b) Both parts are negative, so a direct start, “n^2 - 1 is not a multiple of 8”, has nothing to compute. Its contrapositive is “if 4 \mid n - 1, then 8 \mid n^2 - 1”, which is (a). So (b) is already proved: (a) and (b) are contrapositives of each other, and the proof of (a) is a proof of (b) by contraposition.
(c) There is no conditional worth turning around: “positive integer” only says which n the claim is about, and it stays outside. The claim says something does not happen, and its negation names an object, an integer equal to \displaystyle \sqrt{n^2 + 1}. That is the setting for a proof by contradiction.
Proof. Suppose, for a contradiction, that n is a positive integer and \displaystyle \sqrt{n^2 + 1} = m for some integer m. Then m > 0 and m^2 = n^2 + 1. Since n \ge 1,
so n^2 < m^2 < (n + 1)^2, and since n, m and n + 1 are positive, n < m < n + 1. No integer lies strictly between two consecutive integers, a contradiction. So \displaystyle \sqrt{n^2 + 1} is not an integer. \square
A proof by contradiction of P \to Q whose contradiction is with P itself was a proof by contraposition all along, and reads better written as one (contradiction or contraposition).
A quantifier inside the hypothesis
Prove: for all real numbers a and b, if a \le b + \varepsilon for every \varepsilon > 0, then a \le b.
SolutionThe outer “for all a and b” stays outside. The hypothesis carries its own “for every \varepsilon”, which is part of P, so it flips when P is negated: the negation of “a \le b + \varepsilon for every \varepsilon > 0” is “a > b + \varepsilon for some \varepsilon > 0”. The contrapositive: for all real numbers a and b, if a > b, then there is an \varepsilon > 0 with a > b + \varepsilon. A direct proof would have to use infinitely many inequalities at once; the contrapositive asks for one number.
Proof. We prove the contrapositive. Let a and b be real numbers with a > b, and let \displaystyle \varepsilon = \frac{a - b}{2}, which is positive because a - b > 0. Then, using b < a,
So \varepsilon is a positive number with a > b + \varepsilon, which proves the contrapositive. Therefore, if a \le b + \varepsilon for every \varepsilon > 0, then a \le b. \square
A “there is” is proved by producing one (existence proof); here it was half the gap between a and b.
Boundaries
Only the contrapositive is equivalent. Assuming \neg P and proving \neg Q proves the inverse, which is equivalent to the converse, not to the claim (converse, inverse and contrapositive). A proof by contraposition always begins from the negation of the conclusion.
The negations must be exact, and they depend on the domain. “Not odd” is “even” only for integers. For real numbers, “not less than 8” is “at least 8”, never “more than 8”. Example 5 shows how much can hang on the domain: the same sentence is true for integers and false for real numbers.
There must be a conditional. Contraposition works on “if P, then Q”. A statement such as Example 6(c), whose only hypothesis is the domain, has nothing useful to turn around.
Where this goes next
Proving “P if and only if Q” takes two conditionals, and one of them is often easiest by contraposition: proving an if and only if. A function is one-to-one when f(x) = f(y) forces x = y, and that is checked as often through its contrapositive, “if x \ne y, then f(x) \ne f(y)” (one-to-one and onto). The quantifier flip of Example 7 returns in the definition of a limit.
Exercises
Part 1: writing the contrapositive
Write the contrapositive of each statement, with every negation carried out. Do not prove it.
- For every integer n, if 9n + 4 is odd, then n is odd.
- For all integers a and b, if ab is even, then a is even or b is even.
- For all real numbers x and y, if x + y < 2, then x < 1 or y < 1.
- For all integers m and n, if m + n is even and m is odd, then n is odd.
Part 1: proofs by contraposition
- Prove: for every integer n, if n^2 - 4n + 7 is even, then n is odd.
- Prove: for every integer n, if n^3 - 1 is even, then n is odd.
- Prove: for all integers a and b, if a^2 + b is odd, then a is odd or b is odd.
- Prove: for all integers a and b, if (a - 1)(b + 2) is odd, then a is even and b is odd.
- Prove by contraposition that for all integers a and b, if a^2 + ab + b^2 is even, then a and b are both even. (Example 2 settles one case.)
Part 1: reasoning
- A write-up of “for every integer n, if 3n + 1 is even, then n is odd” begins “Suppose n is odd” and goes on to show that 3n + 1 is even. What has it proved, and what should it have assumed?
- In Example 3 the assumption is “x is even or y is odd”. Explain why the proof may not assume that x is even and y is odd together.
Part 2: divisibility and real numbers
- Prove: for all integers a and b, if 5 \nmid a + 4b, then 5 \nmid a - b.
- Prove: for every integer n, if 4 \nmid n^2, then n is odd.
- Prove: for all integers a and b, if 4 \nmid a^2 + 2b, then a is odd or b is odd.
- Prove: for every real number x, if x is irrational, then 5 - 3x is irrational.
- Prove: for all real numbers x, y and z, if x + y + z > 30, then x > 10 or y > 10 or z > 10.
- Prove that for all positive integers a and b, if ab \ge 50, then a \ge 8 or b \ge 8. Is the statement true for all positive real numbers?
- Prove: for every real number a, if |a| < \varepsilon for every \varepsilon > 0, then a = 0.
Part 2: choosing a method
Say which method you would use and why, then prove the claim.
- For every integer n, if 3 \mid n - 2, then 3 \mid n^2 - 4.
- For every real number x, if x^3 + x > 10, then x > 2.
- For all real numbers x and y, if x is irrational, then x + y is irrational or x - y is irrational.
- For every positive integer n, n^2 + n is not a perfect square.
Part 2: reasoning
- Explain why \forall n\,(P(n) \to Q(n)) is equivalent to \forall n\,(\neg Q(n) \to \neg P(n)). Then, with P(n) “n = 1” and Q(n) “n = 2” over the integers, show that “if \neg Q(n) for some n, then \neg P(n) for some n” is not equivalent to it.
- Show how any proof by contraposition of P \to Q can be rewritten as a proof by contradiction, and say why the contraposition version is usually the cleaner one.
Answers
- For every integer n, if n is even, then 9n + 4 is even.
- For all integers a and b, if a is odd and b is odd, then ab is odd.
- For all real numbers x and y, if x \ge 1 and y \ge 1, then x + y \ge 2.
- For all integers m and n, if n is even, then m + n is odd or m is even. The hypothesis is an “and”, so its negation is an “or”.
- Contrapositive: if n is even, then n^2 - 4n + 7 is odd. With n = 2k, n^2 - 4n + 7 = 4k^2 - 8k + 7, and this is 2(2k^2 - 4k + 3) + 1, which is odd. So the claim holds.
- Contrapositive: if n is even, then n^3 - 1 is odd. With n = 2k, n^3 - 1 = 8k^3 - 1 = 2(4k^3 - 1) + 1, which is odd.
- Contrapositive: if a and b are both even, then a^2 + b is even. With a = 2k and b = 2m, a^2 + b = 4k^2 + 2m = 2(2k^2 + m).
- Contrapositive: if a is odd or b is even, then (a - 1)(b + 2) is even. If a = 2k + 1, the factor a - 1 = 2k is even. If b = 2m, the factor b + 2 = 2(m + 1) is even. Either way the product is even.
- Contrapositive: if a is odd or b is odd, then a^2 + ab + b^2 is odd. If both are odd, this is Example 2. If a = 2k + 1 and b = 2m, then a^2 + ab + b^2 is 4k^2 + 4k + 1 + 4km + 2m + 4m^2, which is 2(2k^2 + 2k + 2km + m + 2m^2) + 1, odd. If a is even and b odd, the same computation with the letters swapped works, since swapping a and b does not change a^2 + ab + b^2.
- It proved the converse, “if n is odd, then 3n + 1 is even”, a different statement. It should assume n even, n = 2k, and show 3n + 1 = 2(3k) + 1 is odd.
- “x even or y odd” is true when only one part holds, for instance x = 2, y = 4, or x = 3, y = 5. The contrapositive must be proved for those pairs too; assuming both parts would prove it only for pairs like x = 2, y = 5.
- Contrapositive: if 5 \mid a - b, then 5 \mid a + 4b. From a - b = 5k, a + 4b = (a - b) + 5b = 5(k + b), with k + b an integer.
- Contrapositive: if n is even, then 4 \mid n^2. From n = 2k, n^2 = 4k^2.
- Contrapositive: if a and b are both even, then 4 \mid a^2 + 2b. From a = 2k and b = 2m, a^2 + 2b = 4k^2 + 4m = 4(k^2 + m).
- Contrapositive: if 5 - 3x is rational, then x is rational. If \displaystyle 5 - 3x = \frac{p}{q} with integers p and q \ne 0, then \displaystyle x = \frac{5q - p}{3q}, a quotient of integers with 3q \ne 0.
- Contrapositive: if x \le 10, y \le 10 and z \le 10, then x + y + z \le 30. Add the three inequalities.
- Contrapositive: for positive integers, if a < 8 and b < 8, then ab < 50. Integers below 8 are at most 7, and since both are positive, ab \le 7b \le 49 < 50. Not true for positive reals: a = b = 7.1 gives ab = 50.41 with neither at least 8.
- Contrapositive: if a \ne 0, then |a| \ge \varepsilon for some \varepsilon > 0. Take \varepsilon = |a|, which is positive since a \ne 0, and |a| \ge \varepsilon holds with equality.
- Directly, since the hypothesis is positive: n - 2 = 3k, so n^2 - 4 = (n - 2)(n + 2), which is 3k(n + 2), a multiple of 3.
- By contraposition, since the conclusion is about x alone. Contrapositive: if x \le 2, then x^3 + x \le 10. Cubing keeps order on all real numbers, so x^3 \le 8; adding x \le 2 gives x^3 + x \le 10.
- By contraposition, since the hypothesis is negative and the conclusion an “or”. Contrapositive: if x + y and x - y are rational, then x is rational. Indeed \displaystyle x = \frac{(x + y) + (x - y)}{2}, half a sum of two rational numbers.
- By contradiction, since there is no conditional to turn around. Suppose n^2 + n = m^2 with n \ge 1 and m an integer, m \ge 0. Then n^2 < n^2 + n < n^2 + 2n + 1, so n^2 < m^2 < (n + 1)^2 and n < m < n + 1, impossible for an integer m.
- For each single n, P(n) \to Q(n) and \neg Q(n) \to \neg P(n) have the same truth value, so one is true for every n exactly when the other is. With the given P and Q, \forall n\,(n = 1 \to n = 2) is false at n = 1, but “if some n \ne 2, then some n \ne 1” is true, since n = 0 satisfies both.
- Suppose, for a contradiction, P and \neg Q. The direct proof of \neg Q \to \neg P gives \neg P, contradicting P. The contradiction version carries the assumption P through lines that never use it; the contraposition version assumes only what it uses and states exactly what it proves.