Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 68 · Proof Techniques

Contradiction and Contrapositive

Learn proof by contrapositive and proof by contradiction with classic examples: the irrationality of the square root of 2 and infinitely many primes.

Some statements are awkward to prove head-on. "If n² is even then n is even" gives you very little to start with: the hypothesis mentions a square, and you want a fact about the number itself. Other statements, like "there are infinitely many primes", have no obvious hypothesis at all. For these, mathematicians turn the problem around.

This lesson covers two indirect techniques. A proof by contrapositive proves an equivalent statement that is easier to attack. A proof by contradiction assumes the opposite of what you want and shows that this leads to something impossible. Both rely on the logic you met in Implication and Biconditional and Logical Equivalences and Laws.

Proof by contrapositive

The contrapositive of "if P then Q" is "if not Q then not P". The two statements are logically equivalent: they are true in exactly the same situations. You can confirm that with a truth table, and a quick check in code shows it.

Python An implication equals its contrapositive

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The converse Q → P is a different statement, as the last column shows. So to prove "if P then Q" by contrapositive, assume not Q and derive not P.

Theorem. If n² is even, then n is even.

Proof (by contrapositive). We prove: if n is odd, then n² is odd. Let n = 2k + 1. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. This is the contrapositive of the theorem, so the theorem holds. ∎

Notice how much easier this was. Starting from "n is not even" gives a concrete formula 2k + 1 to compute with, whereas starting from "n² is even" gives only n² = 2m, and you cannot get from there to a statement about n without extra tools.

Two ways to go indirect

Contrapositive To show P implies Q, assume not Q and reach not P.
Contradiction Assume the claim is false and reach an impossibility.

Contrapositive proves the same implication. Contradiction proves any statement.

1 / 2

Proof by contradiction

To prove a statement S by contradiction, assume S is false and keep reasoning until you reach something that cannot be true: a statement and its negation together, or a plain falsehood like 1 = 0. Since correct reasoning from true assumptions never gives a falsehood, the assumption "S is false" must itself be wrong, so S is true.

The logic is: if ¬S → False is true, then S must be true. You can see it by checking that the only way an implication with a false conclusion can hold is when its hypothesis is false.

Contradiction is the standard tool for statements about things that do not exist or are not of a certain form, because the opposite ("it does exist") hands you an object to work with.

The square root of 2 is irrational

A number is rational if it equals a/b for integers a and b ≠ 0, and we can always write the fraction in lowest terms (no common factor).

Theorem. √2 is irrational.

Proof (by contradiction). Suppose √2 is rational. Then √2 = a/b with integers a, b, b ≠ 0, and the fraction is in lowest terms, so a and b have no common factor greater than 1. Squaring gives 2 = a²/b², so a² = 2b². Hence a² is even, and by the previous theorem a is even: a = 2c for some integer c. Substituting, 4c² = 2b², so b² = 2c², which makes b² even, and so b is even. Now both a and b are even, so they share the factor 2. This contradicts "lowest terms". Therefore √2 is not rational. ∎

The proof used the contrapositive theorem from above as a lemma, which is typical: proofs build on each other. Code cannot prove irrationality, but it can show how the best fractional approximations behave, and that no small fraction squares to exactly 2.

Python No small fraction squares to 2

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The fractions that get closest, like 7/5 and 17/12, come arbitrarily near √2 but never reach it. The proof explains why the search can never succeed, however far you go.

There are infinitely many primes

A prime is an integer greater than 1 whose only positive divisors are 1 and itself. Euclid's proof is one of the most celebrated arguments in mathematics.

Theorem. There are infinitely many primes.

Proof (by contradiction). Suppose there are only finitely many primes, p₁, p₂, …, pₙ. Consider N = p₁ × p₂ × … × pₙ + 1. Every integer greater than 1 has a prime divisor (see Divisibility and Primes for the full story), so N has a prime divisor q. Our list contains every prime, so q = pᵢ for some i. Then q divides the product p₁ × … × pₙ and also divides N, so it divides their difference, which is 1. But no prime divides 1. This contradiction shows that the list of primes cannot be finite. ∎

A common misunderstanding: the proof does not claim that N is itself prime. It only says that N has a prime factor missing from the list. Code makes the point vividly.

Python Euclid's number is not always prime

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the primes up to 13, N = 30031 = 59 × 509 is composite, yet both of its prime factors are new. The list of primes was incomplete either way, which is exactly what the contradiction needs.

Common errors

Indirect proofs have their own traps.

  • Mixing up the contrapositive and the converse. To prove "if P then Q", proving "if Q then P" proves nothing about the original. The contrapositive is "if not Q then not P".
  • Negating wrongly. The negation of "all x satisfy P" is "some x fails P", not "no x satisfies P". Practice with Predicates and Quantifiers.
  • Reaching no contradiction. Deriving an odd-looking but true statement is not a contradiction. You need a genuine impossibility, or something that conflicts with an assumption (as "lowest terms" did above).
  • Contradicting the wrong thing. Make clear which assumption failed: it must be the one you introduced at the start ("suppose S is false").
  • Using contradiction when a direct proof is short. If the final line is a contradiction of your own first assumption, you may have a direct proof or a contrapositive proof in disguise. Prefer the simpler form.

When a direct proof stalls, try the contrapositive first: it is mechanical, since it only flips and negates. Use contradiction when the statement says something does not exist, is not rational, or is infinite.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the contrapositive of 'if it rains, the match is cancelled'?

    The contrapositive of P -> Q is not Q -> not P. The first option is the converse and the second is the inverse; neither is equivalent to the original.
  2. 2. To prove a statement S by contradiction, what do you assume first?

    You assume the negation of S and derive an impossibility, which shows the assumption was wrong, so S holds.
  3. 3. In Euclid's proof, which claim about N = p1 x ... x pn + 1 is correct?

    N leaves remainder 1 when divided by each listed prime, so none of them divides it, yet N has some prime factor. That factor must be a prime outside the list. N itself might be composite, as 30031 = 59 x 509 shows.
  4. 4. Where does the proof that the square root of 2 is irrational reach its contradiction?

    The argument shows both a and b are even, so they share the factor 2, which contradicts the assumption that a/b was in lowest terms.

Summary

  • The contrapositive of "if P then Q" is "if not Q then not P", and it is logically equivalent to the original; the converse is not.
  • Proof by contrapositive assumes not Q and derives not P, which is often much easier.
  • Proof by contradiction assumes the claim is false and derives an impossibility, which shows the claim is true.
  • The square root of 2 is irrational: a fraction in lowest terms would force both numerator and denominator to be even.
  • There are infinitely many primes: a finite list would give an N with a prime factor missing from the list.
  • Avoid confusing converse and contrapositive, negating quantifiers incorrectly, or calling any odd result a contradiction.

Next: Mathematical Induction.