Proof by Contradiction

Overview

Reaching an Impossibility

In proof by contradiction, you assume the NEGATION of what you want to prove and show that this assumption leads to a logical impossibility (contradiction). Since the assumption leads to nonsense, the original statement must be true.

Definition

Proof by Contradiction Template

To prove: Statement S.

Proof: 1. Assume ¬S (the negation of S). 2. [Derive logical consequences...] 3. Reach a contradiction (e.g., something both true and false). 4. Therefore ¬S is false, so S is true. QED.

Example

Classic Proof: √2 is Irrational

Theorem: √2 is irrational.

Proof: Assume, for contradiction, that √2 is rational. Then √2 = a/b where a, b are integers with b ≠ 0 and the fraction is in lowest terms (gcd(a, b) = 1).

Squaring: 2 = a²/b², so a² = 2b². This means a² is even, so a must be even. Write a = 2k. Then (2k)² = 2b², so 4k² = 2b², so b² = 2k². This means b² is even, so b is even.

But now both a and b are even, contradicting our assumption that gcd(a, b) = 1. Contradiction!

Therefore √2 is irrational. QED.

Example

Proof: Infinitely Many Primes

Theorem: There are infinitely many prime numbers.

Proof: Assume, for contradiction, that there are only finitely many primes: p₁, p₂, ..., pₙ.

Consider N = p₁ × p₂ × ... × pₙ + 1. N is greater than 1, so N must have a prime factor p. But N leaves remainder 1 when divided by any pᵢ, so p ≠ pᵢ for all i. This means p is a prime not in our list, contradicting the assumption that p₁, ..., pₙ are all the primes.

Therefore there are infinitely many primes. QED.

Note

Contradiction vs. Contrapositive

Proof by contrapositive proves P → Q by proving ¬Q → ¬P directly. This is different from contradiction, where you assume the entire statement is false.

For "If P, then Q": - Contrapositive: Assume ¬Q, derive ¬P. - Contradiction: Assume P ∧ ¬Q, derive a contradiction.

Contrapositive is often cleaner for conditional statements. Contradiction is more general and can prove any kind of statement.

Example

Proof by Contrapositive

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

Proof (Contrapositive): We prove: if n is odd, then n² is odd. Assume n is odd. Then n = 2k + 1 for some integer k. n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1. Since 2k² + 2k is an integer, n² is odd. QED.