Proof by Contradiction — Mathematics Knowledge System

Overview

Proof by contradiction (reductio ad absurdum) establishes a statement P by assuming its negation ¬P and deriving a logical contradiction — typically a statement of the form Q ∧ ¬Q — from that assumption together with known facts. Because a contradiction can never be true, and ¬P led to one, ¬P must be false, so P must be true. This method relies on the law of excluded middle (P ∨ ¬P) and, in its full strength, is generally rejected by constructive/intuitionistic logic, which accepts only the weaker principle that ¬¬P does not immediately give P without further construction. It is the classical proof strategy behind landmark results such as the irrationality of √2 and the infinitude of primes.

Intuition

Proof by contradiction works like an alibi: to prove someone was at the concert, you show that assuming they weren't leads to an impossible situation — say, two witnesses independently and reliably placing them in two different cities at once — so the assumption 'they weren't at the concert' must be false. In mathematics, once you assume the opposite of what you want to prove, you get an extra fact to work with (¬P), and often that fact combines with known theorems to force some statement Q to be simultaneously true and false, which is absurd — meaning the only flawed link in the chain was the initial assumption ¬P itself.

Formal Definition

Definition

Proof by contradiction has the following logical form:

\text{Assume } \neg P. \text{ Derive } Q \land \neg Q \text{ (a contradiction).} \implies P

Reductio ad absurdum

(\neg P \implies \text{False}) \implies P

Formal schema

P \lor \neg P \quad \text{(law of excluded middle, relied upon classically)}

Underlying classical axiom

Worked Examples

Assume the negation: √2 is rational, so √2 = a/b in lowest terms (gcd(a,b)=1).
$\sqrt{2} = a/b,\ \gcd(a,b)=1$
Squaring gives a² = 2b², so a² is even, hence a is even; write a = 2k.
$a^2 = 2b^2 \implies a = 2k$
Substituting gives 4k² = 2b², so b² = 2k², meaning b is also even — contradicting gcd(a,b)=1 since both are even.
$b^2 = 2k^2 \implies b \text{ even, contradicting } \gcd(a,b)=1$

Answer: The assumption that √2 is rational leads to a contradiction, so √2 is irrational.

Practice Problems

Difficulty 3/10

Prove by contradiction that there is no smallest positive real number.

Difficulty 3/10

Prove by contradiction that if n² is even, then n is even.

Difficulty 4/10

Prove by contradiction that log₂3 is irrational.

Quiz

Summary

Proof by contradiction assumes ¬P, derives an impossible statement Q ∧ ¬Q, and concludes P must be true.
It relies on the law of excluded middle and is the classical strategy behind results like the irrationality of √2.
Constructive/intuitionistic logic rejects the unrestricted use of this method, since deriving ¬¬P doesn't constructively exhibit P.

References

WebsiteWikipedia — Proof by contradiction