← mapLogic & Proof

Proof by Contradiction

requiresContrapositive & Iff Proofs ⚠Irrationals & the Real Line ⚠

⚗ Dr. Möbius, from the lab

Now the most thrilling weapon in the arsenal — the one that feels like cheating but is absolutely bulletproof. You want to prove $P$ ? Assume it's false. Then watch the entire universe catch fire. If denying $P$ forces an impossibility, then $P$ had no choice but to be true all along. Today we finally make the √2 argument rigorous — I've been dangling that proof since the first damn lesson and now we deliver — and we prove there are infinitely many primes, both with the same gorgeous, ruthless move. The reactor is fully charged. Let's go.

THE BIG IDEA

To prove P, assume ¬P and derive an impossibility; since a true assumption can't yield a contradiction, ¬P must be false, so P is true.

The shape, and why it's valid

Proof by contradiction runs like this:

Suppose, for contradiction, that the thing you want to prove is false — assume $\neg P$ .
Reason validly until you derive something impossible — a statement and its own negation, like " $x$ is even and $x$ is odd," or " $1 = 0$ ." Call that impossibility a contradiction, written as a guaranteed-false statement.
Conclude that the assumption $\neg P$ must have been wrong. Therefore $P$ is true. $\blacksquare$

Why is this airtight? Because true assumptions never produce contradictions. A valid chain of reasoning starting from a true statement only ever reaches true statements. So if your reasoning was valid and it reached a falsehood, the starting assumption was the rotten apple. You assumed $\neg P$ and broke the universe, so $\neg P$ is false, so $P$ is true. Symbolically: if $\neg P \to \text{(false)}$ , then $\neg P$ is false, hence $P$ . That's the whole damn engine.

You grab the hypothesis you don't want, feed it into the reactor, and if the reactor explodes, you've proven the hypothesis was unstable — i.e. false. Controlled demolition of an idea. I have been waiting to show you this since the beginning.

THE classic, now in full rigor: √2 is irrational

Way back in Irrationals & the Real Line I showed you this argument as a trailer — informal, hand-wavy, "trust me on this one." I promised the rigorous version would return in Logic & Proof. Here it is. Here is the full, airtight, beautiful bastard, and you now have every single tool it needs, including the lemma we sharpened last lesson: if $n^2$ is even, then $n$ is even.

Theorem. $\sqrt{2}$ is irrational — there are no integers $a, b$ with $\sqrt{2} = a/b$ .

Proof (by contradiction). Suppose, for contradiction, that $\sqrt{2}$ is rational. Then we can write $\sqrt{2} = \frac{a}{b}$ for integers $a, b$ with $b \ne 0$ , and — crucially — in lowest terms: $a$ and $b$ share no common factor other than $1$ . (Any fraction can be reduced to lowest terms, so this costs us nothing.)

Square both sides: $2 = a^2 / b^2$ , hence $a^2 = 2b^2.$ So $a^2$ is even (it's $2$ times an integer). By our lemma from the last lesson — $n^2$ even $\Rightarrow n$ even — $a$ is even. Write $a = 2c$ for some integer $c$ . Substitute: $(2c)^2 = 2b^2 \ \Rightarrow\ 4c^2 = 2b^2 \ \Rightarrow\ b^2 = 2c^2.$ So $b^2$ is even, and by the same lemma, $b$ is even.

But now $a$ is even and $b$ is even — they share the factor $2$ . That contradicts our setup that $a/b$ was in lowest terms (no common factor). Contradiction. Therefore our assumption was false: $\sqrt{2}$ is not rational. $\blacksquare$

That's it. The trailer is now the feature film, every step justified, the "even/even" collision delivering the kill. The lowest-terms setup was the trap we laid in the very first line: we forced $a$ and $b$ to be coprime, then proved they share a factor. They can't both be true. The reactor explodes. Euclid and his heirs have been enjoying this exact moment for over 2,000 years — welcome to the club.

Euclid: infinitely many primes

A prime is an integer $\ge 2$ whose only positive divisors are $1$ and itself. Euclid proved, ~2300 years ago, that the primes never run out — and his proof is contradiction at its most elegant.

Theorem. There are infinitely many primes.

Proof (by contradiction). Suppose, for contradiction, that there are only finitely many primes. Then we can list all of them: $p_1, p_2, \dots, p_k$ . Now build the number $N = p_1 p_2 \cdots p_k + 1$ — the product of every prime, plus one. Since $N \ge 2$ , it has at least one prime divisor (every integer $\ge 2$ does — we'll prove that fact next lesson). Call that prime divisor $p$ . Since our list contains all primes, $p$ must be one of $p_1, \dots, p_k$ , so $p$ divides the product $p_1 \cdots p_k$ .

But $p$ also divides $N = p_1 \cdots p_k + 1$ . If $p$ divides both $p_1 \cdots p_k$ and $p_1 \cdots p_k + 1$ , then $p$ divides their difference, which is $1$ . No prime divides $1$ (primes are $\ge 2$ ). Contradiction. Therefore there cannot be finitely many primes — there are infinitely many. $\blacksquare$

The subtle point everyone botches: $N$ itself is not claimed to be prime. The argument only needs that $N$ has some prime factor, and that this factor escapes the list. People mis-remember Euclid as " $N$ is a new prime" — this is false, it's been false for two thousand years, and I beg you not to perpetuate it. Check: $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59 \times 509$ — composite! The factor is new, not $N$ . State it carefully or you state it wrong.

Contradiction vs contrapositive: cousins, not twins

These two feel similar — both involve negating something — so let's separate them cleanly.

Contrapositive (last lesson) proves a specific implication $P \to Q$ by assuming $\neg Q$ and deriving $\neg P$ . You end at a clean conclusion, $\neg P$ . No "impossibility" appears.
Contradiction proves any statement $P$ (implication or not) by assuming $\neg P$ and deriving an actual falsehood — a contradiction, a thing that cannot be.

Every contrapositive proof can be rewritten as a contradiction (assume $P$ and $\neg Q$ , derive a clash), but not vice versa — contradiction is the more general, more powerful tool. The √2 and infinitude-of-primes theorems aren't even implications; contrapositive doesn't apply, but contradiction shines.

Warning: contradiction is a chainsaw

It's powerful, it's seductive, and it is overused. A huge number of "proofs by contradiction" are direct proofs wearing a costume — they assume $\neg P$ , never actually use the assumption, derive $P$ straight, and then announce "contradiction with $\neg P$ !" That's a two-step screwdriver job done with a chainsaw, and it drives me absolutely insane. If you can prove $P$ directly, do it — it's clearer, shorter, and you won't accidentally hide a gap inside the theatrics.

Reach for contradiction when the negation gives you a concrete object to break — "assume $\sqrt 2 = a/b$ in lowest terms" hands you actual integers to torture in the reactor; "assume finitely many primes" hands you a finite list to overflow and destroy. When the assumption is a lever, use the chainsaw. When it's dead weight, put it down. Now go break some universes.

🔬 SPECIMENS (worked examples)

Worked example 1 — nuking the largest-integer fantasy▸

Prove by contradiction: there is no largest integer.

Proof (by contradiction). Suppose, for contradiction, that there is a largest integer; call it $M$ . By "largest," $M \ge n$ for every integer $n$ .

But $M + 1$ is also an integer, and $M + 1 > M$ . So $M + 1$ is an integer strictly greater than the supposed largest integer $M$ — contradicting that $M$ is $\ge$ every integer.

This is a contradiction. Therefore our assumption was false: there is no largest integer. $\blacksquare$

The assumption "there is a largest integer, $M$ " was the lever — it handed us a concrete object $M$ to break, and $M + 1$ broke it. That's the right time to use the chainsaw: the negation gave us something to grab.

Worked example 2 — sum of rational and irrational is irrational▸

Prove by contradiction: if $r$ is rational and $x$ is irrational, then $r + x$ is irrational.

Proof (by contradiction). Let $r$ be rational and $x$ irrational. Suppose, for contradiction, that $r + x$ is rational.

Then both $r$ and $r + x$ are rational, so write $r = a/b$ and $r + x = c/d$ for integers $a,b,c,d$ with $b, d \ne 0$ . Subtract: $x = (r + x) - r = \frac{c}{d} - \frac{a}{b} = \frac{cb - ad}{db}.$ The numerator $cb - ad$ and denominator $db$ are integers with $db \ne 0$ , so $x$ is a ratio of integers — i.e. $x$ is rational.

But we assumed $x$ is irrational. Contradiction. Therefore $r + x$ is irrational. $\blacksquare$

The key move: the differences and products of rationals are rational (closure), so assuming $r+x$ rational forces $x$ rational, colliding head-on with the hypothesis. The assumption was the lever; closure of $\mathbb{Q}$ did the breaking.

Worked example 3 — the trap: a contradiction proof with no actual contradiction▸

Critique this "proof": "Claim: if $n$ is even then $n^2$ is even. Proof by contradiction: assume $n$ is even. Then $n = 2k$ , so $n^2 = 4k^2 = 2(2k^2)$ , which is even. This contradicts the assumption that $n^2$ is odd. QED." What's wrong, and what's the honest proof?

What's wrong: This is a fake contradiction proof — the chainsaw misfiring. The author never assumed the negation of the conclusion (" $n^2$ is odd"); they assumed the hypothesis " $n$ is even" and derived " $n^2$ is even" directly, then bolted on a phantom "this contradicts $n^2$ is odd" that was never actually assumed. There is no real contradiction here, just a direct proof wearing a contradiction costume.

The honest proof (direct):

Assume $n$ is even, so $n = 2k$ for some integer $k$ . Then $n^2 = (2k)^2 = 4k^2 = 2(2k^2),$ and $2k^2$ is an integer, so $n^2$ is even. $\blacksquare$

Same algebra, no theatrics, no false "contradiction." The lesson: if you assume $\neg P$ and never use it before reaching the conclusion, you didn't need it — you had a direct proof. Save contradiction for when the negation is a genuine lever (√2, infinitude of primes), not decoration.

☠ KNOWN HAZARDS

Claiming Euclid's $N$ is prime. It isn't necessarily — $2\cdot3\cdot5\cdot7\cdot11\cdot13+1 = 30031 = 59\times 509$ . The argument only needs that $N$ has a prime factor not on the list.
Forgetting the "lowest terms" setup in √2. Without assuming $a/b$ is reduced, deriving " $a$ and $b$ are both even" is no contradiction at all — so what, reduce the fraction. The coprimality is the trap we deliberately lay; without it the proof is just arithmetic going nowhere.
Fake contradiction proofs. If you assume $\neg P$ , prove $P$ directly without ever using $\neg P$ , then yell "contradiction!", you wrote a direct proof in a costume. Use the assumption or drop it.
Deriving a contradiction from a logic error, not the assumption. If your "impossibility" came from a bad algebra step, you've proven nothing about $P$ . The reasoning chain must be valid; only then does the falsehood indict $\neg P$ .

TL;DR

▸
The shape: to prove $P$ , assume $\neg P$ , derive an impossibility (a contradiction), conclude $P$ . Valid because true assumptions never yield falsehoods.
▸
√2 is irrational: assume $\sqrt2 = a/b$ in lowest terms; $a^2 = 2b^2$ forces $a$ even, then $b$ even, so they share factor $2$ — contradicting lowest terms. (Uses the " $n^2$ even $\Rightarrow n$ even" lemma.)
▸
Infinitely many primes (Euclid): assume a finite list $p_1,\dots,p_k$ ; $N = p_1\cdots p_k + 1$ has a prime factor that can't be on the list. Note $N$ need NOT be prime.
▸
Contradiction vs contrapositive: contrapositive proves $P\to Q$ via $\neg Q \to \neg P$ (no falsehood); contradiction proves any $P$ via $\neg P \to$ (false). Contradiction is the more general tool.
▸
Don't overuse it: if the assumption $\neg P$ is never used, you had a direct proof. Reach for contradiction only when negating $P$ hands you a concrete object to break.