The Well-Ordering of Natural Numbers

Every nonempty set of natural numbers contains a least element. This property is logically equivalent to the principle of mathematical induction and serves as the foundation for recursive constructions.

Statement

Theorem3.4Well-ordering principle for N

Every nonempty subset $S \subseteq \mathbb{N}$ has a least element: there exists $m \in S$ such that $m \leq n$ for all $n \in S$ .

Proof

We prove that well-ordering follows from the principle of strong induction.

Suppose for contradiction that $S \subseteq \mathbb{N}$ is nonempty and has no least element. Define $T = \mathbb{N} \setminus S$ . We show $T = \mathbb{N}$ by strong induction, contradicting $S \neq \emptyset$ .

Base case: $0 \in T$ . If $0 \in S$ , then $0$ would be the least element of $S$ (since $0 \leq n$ for all $n \in \mathbb{N}$ ), contradicting our assumption. So $0 \in T$ .

Inductive step: Assume $\{0, 1, \ldots, k\} \subseteq T$ (i.e., $\{0, \ldots, k\} \cap S = \emptyset$ ). We show $k + 1 \in T$ . If $k + 1 \in S$ , then $k + 1$ would be the least element of $S$ (since all smaller natural numbers are in $T$ ), contradicting our assumption. So $k + 1 \in T$ .

By strong induction, $T = \mathbb{N}$ , hence $S = \emptyset$ , contradicting the hypothesis that $S$ is nonempty. $\blacksquare$

■

Equivalence with Induction

Theorem3.5Equivalence of induction and well-ordering

The following are equivalent over the base axioms of Peano arithmetic (or ZFC minus the axiom of infinity, augmented with the axiom of infinity):

Mathematical induction: If $S \subseteq \mathbb{N}$ with $0 \in S$ and $n \in S \implies n+1 \in S$ , then $S = \mathbb{N}$ .
Strong induction: If $(\forall m < n,\, m \in S) \implies n \in S$ for all $n$ , then $S = \mathbb{N}$ .
Well-ordering: Every nonempty $S \subseteq \mathbb{N}$ has a least element.

ExampleApplication to divisibility

Claim: Every natural number $n \geq 2$ has a prime divisor.

By well-ordering, the set $D = \{d \in \mathbb{N} : d \geq 2 \text{ and } d \mid n\}$ is nonempty (since $n \in D$ ) and has a least element $p$ . We claim $p$ is prime: if $p = ab$ with $1 < a, b < p$ , then $a \mid p \mid n$ , so $a \in D$ with $a < p$ , contradicting minimality.

RemarkWell-ordering beyond N

The well-ordering principle for $\mathbb{N}$ is a theorem of ZFC. The well-ordering theorem (that every set can be well-ordered) is equivalent to the axiom of choice and is far stronger. The natural numbers are "naturally" well-ordered by $\leq$ , but sets like $\mathbb{R}$ require the axiom of choice for a well-ordering to exist.