Well-order

Mathematical induction on $\mathbb{N}$ works because there is no infinite downward chain $\cdots < n_2 < n_1 < n_0$: every non-empty set of natural numbers has a smallest element. This property — called well-ordering — is strictly stronger than a total order, and it turns out to be logically equivalent to induction itself.

Definition

A total order $(S, \leq)$ is a well-order if every non-empty subset of $S$ has a least element:

$$\forall A \subseteq S,\quad A \neq \emptyset \;\Longrightarrow\; \exists\, m \in A \;\text{ such that }\; \forall a \in A,\; m \leq a$$

The pair $(S, \leq)$ is then called a well-ordered set.

An equivalent characterisation replaces the “least element” condition with a no infinite descending chain condition:

$(S, \leq)$ is a well-order if and only if there is no infinite sequence $a_0 > a_1 > a_2 > \cdots$ in $S$.

The two formulations are equivalent, and each is useful in different contexts. The “least element” form is convenient for existence arguments; the “no descending chain” form is convenient for contradiction arguments.

Examples

Natural numbers under $\leq$

$(\mathbb{N}, \leq)$ is the canonical well-order. Given any non-empty $A \subseteq \mathbb{N}$, pick any $a_0 \in A$. If $a_0$ is not the minimum of $A$, there is a strictly smaller element $a_1 \in A$; if $a_1$ is not the minimum, there is a smaller $a_2$; and so on. Since all elements are non-negative integers, this strictly decreasing sequence $a_0 > a_1 > a_2 > \cdots$ cannot continue indefinitely — you cannot subtract $1$ from a natural number forever. The sequence must terminate at the least element of $A$.

This well-ordering is the foundation on which mathematical induction rests.

Finite totally ordered sets

Every non-empty finite totally ordered set is well-ordered: any non-empty subset of a finite set is also finite, so you can find its minimum by scanning all elements and keeping track of the smallest seen so far.

Initial segments of $\mathbb{N}$

The set $\{0, 1, 2, \ldots, n\}$ for any $n \in \mathbb{N}$, ordered by the usual $\leq$, is well-ordered as a finite totally ordered set.

Non-examples

Integers under $\leq$

$(\mathbb{Z}, \leq)$ is a total order, but not a well-order. The subset $\mathbb{Z}$ itself has no least element: for any $n \in \mathbb{Z}$, the element $n - 1$ is strictly smaller. More explicitly, the subset $\{\ldots, -3, -2, -1, 0\}$ has no minimum.

Rationals and reals under $\leq$

$(\mathbb{Q}, \leq)$ and $(\mathbb{R}, \leq)$ are total orders, but neither is a well-order. The open interval $(0, 1)$ is a non-empty subset of both, and it has no least element: for any $q \in (0, 1)$, the element $q/2$ is strictly smaller and still lies in $(0, 1)$.

Well-ordering and mathematical induction

For $\mathbb{N}$, the well-ordering principle and the principle of mathematical induction are logically equivalent — each implies the other.

Well-ordering implies induction. Let $P$ be a property of natural numbers. Suppose $P(0)$ holds and, for every $k \in \mathbb{N}$, $P(k) \Rightarrow P(k+1)$. Define the failure set:

$$F \;\coloneqq\; \{n \in \mathbb{N} \mid \neg P(n)\}$$

Suppose for contradiction that $F$ is non-empty. By well-ordering, $F$ has a least element $m$. Since $P(0)$ holds, $m \neq 0$, so $m \geq 1$ and $m - 1 \in \mathbb{N}$. Since $m$ is the least element of $F$, the natural number $m - 1$ is not in $F$, so $P(m - 1)$ holds. Applying the inductive step gives $P(m)$, contradicting $m \in F$. Therefore $F = \emptyset$ and $P$ holds universally.

Induction implies well-ordering. By strong induction you can prove: for every $n \in \mathbb{N}$, every non-empty subset of $\{0, 1, \ldots, n\}$ has a minimum. Combining these cases covers all of $\mathbb{N}$, establishing well-ordering.

The equivalence shows that the well-ordering of $\mathbb{N}$ is not a separate assumption — it is the same fact as induction, viewed from a different angle.

The well-ordering theorem

A natural question is: can every set, even an uncountable one like $\mathbb{R}$, be well-ordered?

Remarkably, the answer is yes — but the proof requires the Axiom of Choice (AC), which asserts that for any collection of non-empty sets, you can simultaneously pick one element from each. From AC the following theorem follows:

Well-ordering theorem. Every set can be well-ordered.

The well-ordering theorem is equivalent to AC within the standard Zermelo–Fraenkel axioms of set theory (ZF): each implies the other. This means that while $\mathbb{R}$ can be well-ordered in principle, the well-order cannot be written down explicitly — its existence is non-constructive. No formula will tell you which real number comes first.

Summary

• A well-order is a total order in which every non-empty subset has a least element; equivalently, there are no infinite strictly descending sequences.
• $(\mathbb{N}, \leq)$ is the prototypical well-order; every finite totally ordered set is also well-ordered.
• $(\mathbb{Z}, \leq)$, $(\mathbb{Q}, \leq)$, and $(\mathbb{R}, \leq)$ are total orders but not well-orders.
• The well-ordering principle on $\mathbb{N}$ is logically equivalent to mathematical induction.
• The well-ordering theorem states that every set can be well-ordered, but this requires — and is in fact equivalent to — the Axiom of Choice.