Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 37 · Proof Techniques

Proof by Contrapositive and Proof by Contradiction

Learn when to prove the contrapositive and when to argue by contradiction, with classic proofs (irrationality of √2, infinitely many primes) and numeric Python checks.

Sometimes assuming the hypothesis and marching forward gets you nowhere. Two indirect techniques often rescue you. Proof by contrapositive swaps the statement for an equivalent one that is easier to attack, and proof by contradiction assumes the claim is false and derives an absurdity.

Proof by contrapositive

Recall that P → Q is logically equivalent to its contrapositive ¬Q → ¬P. To prove P → Q, you may instead assume ¬Q and derive ¬P. This is especially handy when Q is a negative statement (so ¬Q is a nice positive one) or when the hypothesis P gives little to work with.

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

A direct proof starts from n² = 2k and has to extract a square root, which is awkward. The contrapositive is: if n is odd, then n² is odd.

Proof (contrapositive). Suppose n is odd, n = 2k + 1. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. Hence if n² is even, n must be even. ∎

Python Implication, contrapositive, converse and inverse

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 this particular statement the converse is also true, so all four print True for the numeric range. The last line is the general fact: implication and contrapositive always agree. Do not mistake "the converse happens to be true here" for a general equivalence (compare "if it is a square then it is a rectangle").

Proof by contradiction

To prove a statement S, assume ¬S and derive a contradiction (something false such as R ∧ ¬R, or 0 = 1). Since valid reasoning from the assumption led to absurdity, the assumption must be false, so S is true. In the logic of the earlier lesson this is the rule: if assuming ¬S leads to ⊥, conclude S.

Classic example: √2 is irrational

Theorem. √2 is irrational.

Proof. Suppose √2 were rational. Then √2 = a/b with integers a, b, b ≠ 0, written in lowest terms (no common factor). Squaring: 2b² = a², so a² is even, hence a is even (previous theorem). Write a = 2c. Then 2b² = 4c², so b² = 2c², making b² even and so b even. Now a and b are both even, contradicting lowest terms. Hence √2 is irrational. ∎

Classic example: infinitely many primes

Theorem (Euclid). There are infinitely many primes.

Proof. Suppose there were finitely many: p₁, …, pₙ. Let N = p₁p₂⋯pₙ + 1. N > 1, so it has a prime divisor p. That prime must be some pᵢ, so pᵢ divides both N and the product p₁⋯pₙ, hence divides their difference, 1. Impossible. So no finite list contains all primes. ∎

The numbers p₁⋯pₙ + 1 are not always prime (2·3·5·7·11·13 + 1 = 30031 = 59 × 509), but they always have a prime factor outside the list, which is all the proof needs.

Python Euclid's construction in action

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.

Each round produces a prime missing from the list: the heart of Euclid's argument, running.

Indirect proofs

Contrapositive Assume ¬Q, show ¬P
Contradiction Assume ¬S, reach absurdity
When to use Direct route is blocked

Both are valid: classical logic accepts them

1 / 2

Choosing a technique

Situation Try
Hypothesis easy to unpack Direct proof
Conclusion is negative ("not", "irrational", "no") Contradiction or contrapositive
Statement P → Q where ¬Q is concrete Contrapositive
Claim of the form "there is no …" Contradiction
Uniqueness Assume two, show equal (or contradiction)

Contrapositive vs contradiction. A contrapositive proof assumes ¬Q and proves ¬P, with no hidden "contradiction". A contradiction proof of P → Q assumes P ∧ ¬Q and derives anything absurd. Every contrapositive proof can be seen as a contradiction proof (the absurdity is P ∧ ¬P), but the contrapositive version is cleaner when it applies. Prefer it, and avoid "contradiction" proofs that are really direct proofs with a needless detour.

Common mistakes

  • Proving the converse instead of the contrapositive.
  • Assuming the wrong negation. The negation of "for all" is "there exists a counterexample"; the negation of "x is irrational" is "x is rational".
  • Deriving something odd that is not actually a contradiction.
  • Forgetting to state at the end which assumption was refuted.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. The contrapositive of 'if it rains then the ground is wet' is...

    Swap and negate: ¬Q → ¬P.
  2. 2. In a proof by contradiction of S, you begin by assuming...

    Assume the negation, derive an absurdity, and conclude S.
  3. 3. In the proof that √2 is irrational, which contradiction arises?

    Assuming a/b in lowest terms leads to a common factor of 2.
  4. 4. Why does Euclid's number p₁⋯pₙ + 1 give a new prime factor?

    Every pᵢ leaves remainder 1, so any prime factor of N lies outside the list.

Summary

  • P → Q is equivalent to ¬Q → ¬P, so you may prove the contrapositive when it is easier.
  • Proof by contradiction assumes the negation of the claim and derives an impossibility.
  • Famous results: irrationality of √2 and the infinitude of primes.
  • Take care with negations, and do not confuse contrapositive with converse.
  • Prefer the simplest valid technique.

Next: Mathematical Induction