A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The well-ordering principle states every non-empty set of positive integers has a least element. Logically equivalent to mathematical induction, it can prove statements by assuming a counterexample exists and deriving a contradiction via the least element.
You've worked with strong induction, which lets you assume the statement holds for all positive integers smaller than n in order to prove it for n. The well-ordering principle is a restatement of the same fundamental fact about the natural numbers from a different angle: every non-empty subset of the positive integers contains a smallest element. This might seem obvious — of course you can find the minimum — but it is a genuine axiom, not a logical tautology. The real numbers, for example, do *not* satisfy this property: the open interval (0, 1) is a non-empty set of positive numbers with no least element.
The logical equivalence between well-ordering and induction is deep. Given well-ordering, you can derive induction: if P(1) holds and P(k) → P(k+1) for all k, suppose for contradiction that P fails somewhere. The set of failures is a non-empty set of positive integers, so by well-ordering it has a least element n. Since P(1) holds, n > 1. Since n is the *least* failure, P(n−1) is true. But then P(n−1) → P(n) gives P(n) — contradiction. Conversely, induction implies well-ordering. The two principles are two faces of the same structural fact about ℕ.
Well-ordering suggests a direct proof technique distinct from induction's step-by-step structure: proof by minimal counterexample. To prove a statement P holds for all positive integers, assume for contradiction that it fails for some positive integer. By well-ordering, there is a *smallest* counterexample — call it n. Now derive a contradiction: either show that a smaller counterexample must exist (ruling out n being minimal), or show directly that P(n) must hold (contradicting it being a counterexample). For example, to prove every integer greater than 1 has a prime factor: if not, let n be the smallest integer greater than 1 with no prime factor. Then n is not prime (or it would be its own prime factor), so n = ab with 1 < a, b < n. Since a < n and n was minimal, a has a prime factor p. But p divides a and a divides n, so p divides n — contradiction.
Choose between well-ordering and induction based on which argument flows more naturally. Induction is more natural when you can explicitly build P(n) from P(n−1). Well-ordering (minimal counterexample) is often cleaner when the proof works by contradiction and the structure of the "smallest failure" is easier to analyze than an inductive step. Both are always available for any statement about positive integers, and facility with both gives you the flexibility to pick the proof that reads most transparently.