Proof by Contradiction

Detectives do this every day: assume the suspect is innocent, follow that assumption through, and if it leads somewhere that plainly cannot be true — the suspect would have had to be in two cities at once — then innocence is ruled out. Mathematicians turned that everyday trick into one of their most powerful tools.

Here is one of the sneakiest, most satisfying strategies in all of mathematics. To prove that something is true, you begin by boldly assuming it is false. You take that false assumption completely seriously and follow it, step by careful step, wherever the logic leads — until it marches you straight into something impossible: a square that is round, a number that is both even and odd, a fraction that is somehow smaller than itself.

When correct reasoning delivers an absurdity, only one thing can be to blame: the assumption you started with. So the assumption must be false — which means the original statement was true all along. You have proved it, not by building it up, but by watching its opposite self-destruct. It feels like a magic trick, and it powers some of the most beautiful results ever discovered.

Worked example 1 — the classic: \sqrt{2} is irrational

A number is irrational if it cannot be written as a fraction of whole numbers. We'll prove \sqrt{2} is irrational. Trying to build that directly is awkward — so instead, assume the opposite: suppose \sqrt{2} can be written as a fraction, and moreover in lowest terms (all common factors already cancelled):

\sqrt{2} = \frac{a}{b}, \qquad \text{with } \frac{a}{b} \text{ in lowest terms.}

Square both sides and rearrange:

2 = \frac{a^2}{b^2} \quad\Longrightarrow\quad 2b^2 = a^2.

So a^2 is even, which forces a to be even (an odd number squared stays odd), say a = 2c. Substitute back:

2b^2 = (2c)^2 = 4c^2 \quad\Longrightarrow\quad b^2 = 2c^2.

Now b^2 is even too, so b is even. But if a and b are both even, the fraction \tfrac{a}{b} was not in lowest terms — flatly contradicting how we chose it. The assumption has destroyed itself, so \sqrt{2} is irrational. \blacksquare

Worked example 2 — there is no largest even number

Claim: there is no biggest even number. Directly, that's hard to picture — how do you argue about "all even numbers at once"? Contradiction makes it easy.

Assume the opposite: suppose there is a largest even number; call it N. Now look at

N + 2.

Since N is even, N+2 is also even — and it is bigger than N. That contradicts N being the largest even number. The assumption fails, so no largest even number exists. \blacksquare

Notice the flavour: assuming a "biggest" thing exists, then constructing something bigger, is a pattern you'll see again and again — including in Euclid's proof about primes below.

Worked example 3 — a warm-up in one line

Claim: if n^2 is even, then n is even. Assume the opposite: suppose n is odd, so n = 2k+1. Then

n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1,

which is odd. But we were told n^2 is even — a contradiction. So n cannot be odd; it must be even. \blacksquare (This is exactly the little fact the \sqrt{2} proof leaned on.)

The pattern

Every proof by contradiction has the same shape: flip the claim to its exact opposite, follow the logic honestly, and wait for the impossible to appear.

To prove a statement P by contradiction:

Two things sink more contradiction proofs than anything else — get them right and the method is bulletproof:

Proof by contradiction has produced some of the most beautiful results in mathematics — and one of its most dramatic legends. Around 300 BC, Euclid proved there are infinitely many primes in a few devastating lines. Assume the opposite: that there are only finitely many, say p_1, p_2, \dots, p_n. Multiply them all together and add one:

N = p_1 p_2 \cdots p_n + 1.

This N leaves remainder 1 when divided by every prime on the list, so none of them divides it — yet every number has a prime factor. Contradiction! So the list can never be complete: the primes never run out.

Even older is the \sqrt{2} result. The Pythagoreans held a near-religious belief that every number was a ratio of whole numbers — that the universe was built from tidy fractions. The discovery that \sqrt{2} is irrational shattered that creed, and legend has it the cult was so scandalised that they drowned the man, Hippasus, who let the secret out. Small wonder the mathematician G. H. Hardy called proof by contradiction "a mathematician's finest weapon" — sharper, he said, than any gambit in chess. You can watch its opposite, the demolishing power of a single counterexample, elsewhere.

See it explained