Proof by contradiction: assume it is false, derive the impossible
Proof by contradiction assumes the claim is false and derives something impossible, so the assumption falls. The irrationality of √2 and Euclid's primes both yield to it. Engineers use it daily: assume the loop never terminates, assume two users got the same id — impossible.
A bug report lands: two customers received the same invoice number. The on-call engineer replies in one sentence: “Impossible — invoice numbers come from a column with a unique index, so if two rows had the same number, the database would have rejected the second insert.” She assumed the report was true, followed the system’s guarantees to an impossibility, and concluded the report must be wrong. That is a proof by contradiction — the second-oldest move in mathematics, the one that felled √2 and crowned the primes infinite. The end of this story is worth keeping: the report was right. A migration three weeks earlier had silently dropped the index. The proof was valid — but one of its “known facts” was no longer a fact.
After this lesson you can state the three beats of a contradiction proof and explain why it is legitimate, apply the technique to the irrationality of √2 and the infinity of primes, identify when contradiction is the right tool versus the contrapositive, and name the failure mode that produces a false proof.
Three beats: assume ¬C, derive impossible, conclude C. Assume, for the sake of argument, the claim is false. Using only valid steps, arrive at something that cannot be true — a collision with a known fact or with the assumption itself. Conclude: since the assumption led to the impossible, it cannot stand; the claim holds. The engine underneath: valid steps never lead from truth to falsehood. So a chain ending at the impossible had a false input — and if every input except the assumption is bedrock, the assumption is the only suspect.
Classic one: √2 is irrational. A number is rational if it equals p/q (integers, q ≠ 0) in lowest terms (p and q share no common factor). The claim says no such fraction exists — assume one does, and interrogate it.
Assume √2 = p/q in lowest terms. Squaring: p² = 2q², so p² is even. If p were odd then p² would be odd (last lesson, by contraposition), so p is even — write p = 2k. Substituting: q² = 2k², so q is even too. Now p and q are both even — both divisible by 2 — yet the fraction was taken in lowest terms. That is the impossibility. Every step was plain algebra or an already-proven fact, so the assumption is to blame. √2 is irrational. ∎
Notice the cameo: the contrapositive from lesson 1 did the heavy lifting inside this contradiction proof. Techniques compose.
Classic two: there is no largest prime. Assume finitely many primes, list them p₁, p₂, …, pₙ. Build N = p₁·p₂·…·pₙ + 1. Dividing N by any listed prime leaves remainder 1, so no listed prime divides N. But N > 1 has some prime factor — which is not on the list. The list claimed completeness; here is a prime it missed. Impossible. ∎
Critical: the proof does not claim N is prime. It claims N has a prime factor outside the list. Concretely: 2·3·5·7·11·13 + 1 = 30031 = 59·509 — not prime, but 59 and 509 are new primes. The contradiction needs only “a prime not on the list”, and the remainder argument delivers exactly that.
The wall must come from the assumption — not from a slip. The technique works because “the assumption is the only suspect”. One arithmetic error mid-chain and you arrive at an “impossibility” with two candidate sources for the falsehood — and you triumphantly blame the wrong one. A contradiction at the end does not certify the chain; it indicts some input. Only a clean chain entitles you to point at the assumption. When contradiction proves an implication and the derivation only ever uses ¬Q (not P), it is a contrapositive in disguise — restate it as ¬Q→¬P, one assumption instead of two.
Termination as a contradiction argument.
function drainQueue(queue) {
// Claim: this loop always terminates.
while (queue.length > 0) {
queue.pop(); // every pass removes exactly one element
}
}
// Assume it loops forever. Each pass strictly decreases queue.length by 1,
// so the length would decrease forever. But a length is a non-negative
// integer — it cannot decrease forever. Impossible → the loop terminates.And the invoice story: assume two rows share an invoice number → the second INSERT would violate the unique index → the database rejects violating inserts → yet both rows exist — impossible, given the index exists. Each “known fact” is a load-bearing link. When the impossible happened in production, the correct conclusion was not “the report is wrong” but “one of my axioms quietly stopped being an axiom.”
▸Why this works
Why does the assumption take the blame, and not some other link? Audit: every other link is either a definition (which cannot be false — it just fixes meaning), a previously proven fact, or a valid inference. Falsehood cannot originate in those. The only statement admitted without credentials was the assumption — so the falsehood at the end traces to it. In production nothing is truly bedrock: the index can be dropped, the clock can jump, the “single writer” can become two. When the impossible happens in a live system, the correct response is not “the report is wrong” but “go find which axiom quietly died.”
Name the three beats of a contradiction proof (comma-separated).
In the √2 proof, what is the 'impossibility' that closes the argument?
In Euclid's primes proof, does the constructed number N = p₁·p₂·…·pₙ + 1 have to be prime itself? Answer yes or no.
If a contradiction proof of an implication only uses ¬Q (never uses P), what is it really? Answer in two words.
The engineer proves 'two duplicate invoice rows are impossible' from a unique index. The bug report says duplicates exist. What is the most likely explanation? Write one short phrase.
In the √2 proof, why does reaching 'p and q are both even' finish the argument?
Proof by contradiction runs in three beats: assume the claim is false, derive something impossible by valid steps, conclude the claim is true. The engine is validity — valid steps never carry truth into falsehood, so a chain ending at the impossible had a false input, and if every link except the assumption is bedrock, the assumption is the only suspect. The two classics show the craft: assume √2 = p/q in lowest terms, square, watch evenness infect p then q until “no common factor” collapses; assume a complete finite list of primes, multiply and add 1, and the remainder manufactures a prime the list missed — N itself need not be prime, only its factors new. The technique shines where direct attack drowns: impossibility and uniqueness, where assuming falsehood hands you a concrete object — a fraction, a list, two duplicate rows, a non-terminating loop. The discipline: the wall must trace to the assumption — one slip gives blame a second home; in production, when the impossible visibly happened, go find which axiom quietly died. And when your contradiction proof of an implication only used ¬Q, it is a contrapositive in disguise — restate it.
Practice
Start at the top. Tasks go easiest → hardest: recall a fact, apply it to a case, then a senior-level stretch. Open one, attempt it, then reveal.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.