The Smallest Counterexample

Intro to Proofs · Axiom Academy

If a claim about whole numbers were false, it would have to fail somewhere first. Chase that first failure — and watch it vanish. The trick: assume it fails, then chase the first failure Some statements are true for every natural number 1, 2, 3, …, and you'd like to prove it without checking infinitely many cases. Here's a daring move. Suppose the statement were false. Then some numbers break it — and among any collection of whole numbers there is always a smallest one. Grab that smallest troublemaker and squeeze it. Watch the marker land on the claimed smallest counterexample, then construct an even smaller one — and hop to it. Each step the "smallest so far" drops. It can keep going forever, so a true smallest never existed. That impossibility is the whole proof. There is no bottom rung. A "smallest counterexample" that always spawns a smaller one cannot exist — so the claim has no counterexamples at all. Why this only works for the whole numbers The move hinges on one fact: every non-empty set of natural numbers has a smallest element. Drag the candidate down and feel the difference. Among the whole numbers you hit a hard floor at 1 — a true smallest. Among the positive fractions, the machine just halves whatever you pick, so there is never a smallest at all. A hard floor versus no floor. That floor — the well-ordering of the whole numbers — is exactly what lets the smallest counterexample exist to be squeezed. Squeeze a counterexample on a real theorem

This is the written version of the interactive lesson above. See the full Intro to Proofs course.