The Well-Ordering Principle

Why This Matters

The well-ordering principle of the natural numbers is the single sentence:

Every non-empty subset of $\mathbb{N}$ has a least element.

This is foundational. Many of the proof techniques you will use repeatedly in olympiad mathematics either are well-ordering or are equivalent to it. Smallest-counterexample arguments, the division algorithm, infinite descent, the correctness of the Euclidean algorithm: all run on well-ordering.

Recognize a well-ordering argument when:

You have an existence claim and the negation forms a set bounded below by a natural number (a counterexample is at least 1, or a "minimal violation" exists in $\mathbb{N}$ ).
You want to find a "minimal" object (smallest divisor, shortest path, smallest counterexample, smallest period).
A proof-by-induction would work but you find it cleaner to argue at the smallest counterexample directly.

Well-ordering, mathematical induction, and strong induction are logically equivalent over the natural numbers: each implies the other two, and they are interchangeable in proofs. Choose the form that makes the argument cleanest.

The Principle Itself

Theorem

The Well-Ordering Principle of N

Statement

$S$ has a least element: there exists $m \in S$ such that $m \le n$ for every $n \in S$ .

Intuition

The natural numbers are linearly ordered with no infinite descending chains. Pick any element of $S$ ; if it is not the least, find a smaller one in $S$ ; iterate. The process must terminate (no infinite chain in $\mathbb{N}$ goes downward forever), and the terminating element is the least.

This is not the same statement as " $\mathbb{N}$ is bounded below by 0", which is also true but weaker; well-ordering says every subset, no matter how complicated, has a least element you can name.

Proof Sketch

Several routes:

(a) From induction. Suppose for contradiction $S$ is non-empty but has no least element. Let $T = \{n \in \mathbb{N} : n \notin S \text{ and every } k < n \text{ is also not in } S\}$ . We show $T = \mathbb{N}$ by induction (so $S$ is empty, contradicting non-emptiness).

Base: $0 \in T$ because if $0 \in S$ , $0$ is the least element of $S$ (which we assumed does not exist).

Step: assume $0, 1, \ldots, n \in T$ . If $n + 1 \in S$ , then since $0, \ldots, n \notin S$ , $n + 1$ would be the least element of $S$ , contradiction. So $n + 1 \in T$ .

By induction $T = \mathbb{N}$ , so $S = \emptyset$ , contradicting non-emptiness.

(b) From Peano axioms directly. Construct the least element by a fixed-point or descending-chain argument.

Why It Matters

Well-ordering is the engine of finite descent: any argument that produces a strictly smaller natural number from a hypothetical counterexample loops back into well-ordering. You cannot loop forever because there is a least counterexample, and the strict-decrease step contradicts its leastness.

The same statement fails for many other ordered sets you encounter (the rationals, the reals, the integers themselves), which is precisely why those settings need different tools (completeness, compactness, transfinite induction).

Failure Mode

Well-ordering applies to $\mathbb{N}$ (or any subset of it). It does not apply to:

$\mathbb{Z}$ : $\{-1, -2, -3, \ldots\}$ is non-empty but has no least element under the usual order.
$\mathbb{Q}_{> 0}$ : positive rationals; $\{1/2, 1/3, 1/4, \ldots\}$ is non-empty but has no least element.
$\mathbb{R}_{\ge 0}$ : $\{1/n : n \in \mathbb{N}\}$ is bounded below by 0 but has no least element.

Trying to apply well-ordering in these settings is the most common error. Always verify your set sits inside $\mathbb{N}$ .

The well-ordering theorem of ZFC (every set can be well-ordered) is a separate, much stronger statement equivalent to the axiom of choice. Do not confuse it with the well-ordering principle of $\mathbb{N}$ , which is just a property of the natural numbers and needs no choice.

report a correction →

Application: The Division Algorithm

Example

Division with remainder

Problem. For integers $a$ and $d$ with $d > 0$ , show there exist unique integers $q$ and $r$ with $a = q d + r$ and $0 \le r < d$ .

Solution. Existence uses well-ordering.

Let $S = \{a - q d : q \in \mathbb{Z}, a - q d \ge 0\}$ . We need $S$ to be non-empty: take $q$ very negative (smaller than $a / d$ ) so that $a - q d > 0$ . So $S \subseteq \mathbb{N}$ and $S$ is non-empty.

By well-ordering, $S$ has a least element $r$ . Write $r = a - q d$ . We claim $r < d$ .

If $r \ge d$ , then $r - d = a - (q + 1) d \ge 0$ , so $r - d \in S$ and $r - d < r$ , contradicting $r$ being the least element of $S$ . So $0 \le r < d$ .

Uniqueness: if $a = q d + r = q' d + r'$ with $0 \le r, r' < d$ , then $(q - q') d = r' - r$ , so $d \mid r' - r$ , but $|r'

r| < d $, forcing$ r = r' $, hence$ q = q'$.

The division algorithm is the foundation of greatest common divisors, the Euclidean algorithm, and modular arithmetic. All three trace back to this one well-ordering argument.

Application: Smallest Counterexample

The "smallest counterexample" technique is well-ordering in direct application.

Example

Every integer $\ge 2$ has a prime factor

Problem. Show that every integer $n \ge 2$ has at least one prime factor.

Solution. Suppose for contradiction that some $n \ge 2$ has no prime factor. The set $S$ of such integers is non-empty and contained in $\mathbb{N}$ , so it has a least element $m$ by well-ordering.

If $m$ is prime, then $m$ itself is a prime factor of $m$ , contradicting $m \in S$ . So $m$ is composite: $m = a b$ with $2 \le a \le b < m$ . Now $a < m$ and $a \ge 2$ , so $a \notin S$ (by minimality of $m$ ). Hence $a$ has a prime factor $p$ . Then $p \mid a \mid m$ , so $p$ is a prime factor of $m$ , contradicting $m \in S$ .

Either way we reach a contradiction, so $S$ is empty: every $n \ge 2$ has a prime factor.

Strong induction would prove the same thing. The two phrasings ("smallest counterexample" vs "induct on $n$ ") differ only in direction; the underlying logic is identical.

Common Mistakes

Watch Out

Applying well-ordering outside N

The single most common error. Well-ordering of $\mathbb{N}$ does not give you a least element of a set of integers (could be unbounded below), of rationals (could be unbounded below or have no least element even when bounded), or of reals (likewise). Always verify: is your set a subset of $\mathbb{N}$ , or at least bounded below by an integer? If not, you need a different argument (typically infimum + attainment argument for reals).

Watch Out

Confusing the principle with the theorem

The well-ordering principle says $\mathbb{N}$ is well-ordered under $\le$ . The well-ordering theorem (Zermelo 1904) says every set has some well-order. The theorem is equivalent to the axiom of choice and far stronger. Olympiad and standard mathematics use only the principle, which is provable from the Peano axioms without choice.

Watch Out

Forgetting non-emptiness

Well-ordering requires the subset to be non-empty. The empty set has no least element. In smallest-counterexample arguments the contradiction setup ("suppose the set of counterexamples is non-empty") is doing real work; do not skip it.

Watch Out

Using well-ordering when induction is cleaner

"Smallest counterexample" arguments and induction proofs are logically interchangeable, but stylistically different. If your proof invokes the inductive hypothesis at a single predecessor and the step is mechanical, induction is usually clearer to read. If you need to reason about which smaller counterexamples exist or want to manipulate them as a set, well-ordering reads more naturally.

Exercises

ExerciseCore

Problem

Show that there is no infinite strictly decreasing sequence of natural numbers $a_1 > a_2 > a_3 > \cdots$ .

ExerciseCore

Problem

Use well-ordering to show that for any positive integers $a$ and $b$ there exist integers $x, y$ with $\gcd(a, b) = a x + b y$ .

ExerciseAdvanced

Problem

Show that the equation $x^4 + y^4 = z^2$ has no solutions in positive integers $x, y, z$ .

Cross-Network Links

ProofsPath: induction-strong-vs-weak is logically equivalent; proof-by-infinite-descent is well-ordering's most elegant application; extremal-principle is well-ordering generalized beyond $\mathbb{N}$ ; proof-by-contradiction is the meta-technique that smallest-counterexample arguments inhabit.
TheoremPath: measure-theoretic-probability generalizes to transfinite induction; the well-ordering theorem (with choice) underwrites the construction of non-measurable sets.
ComputationPath: termination of recursive procedures on $\mathbb{N}$ -valued measures is well-ordering in algorithmic guise.

References

See structured references block. Primary entry points: Halmos Naive Set Theory §12 for the foundational construction; Velleman How to Prove It Ch 6 for the equivalence with induction; Hardy-Wright Ch 13 for Fermat's descent argument; Aigner-Ziegler for elegant smallest-counterexample proofs.