Well-Orderings

Line the natural numbers up: 0, 1, 2, 3, \dots. Pick any non-empty bunch of them you like — the primes, the multiples of seven, a random handful — and there is always a smallest one. That single, humble property has a name: \mathbb{N} is well-ordered. It is the secret engine behind proof by induction, and generalising it is how mathematics learned to count past infinity.

A well-ordering of a set is a way of lining up its elements — a relation < that is a total order (any two elements are comparable) — with one extra magic ingredient:

Well-ordered, or not?

The figure lines up two familiar orderings. The naturals climb from a definite floor; the integers run off to negative infinity with no bottom. Play through it, then re-read the definition.

So (\mathbb{N}, <) is a well-order, but (\mathbb{Z}, <) with its usual ordering is not — the whole set \mathbb{Z} has no least element, and neither does the subset \{\dots, -2, -1, 0\}. It's the "least element of every subset" clause that fails; being a total order is not enough.

Re-ordering can rescue a set

Here's the subtle part: whether a set is well-ordered depends on the ordering, not the set. The integers under their usual order fail — but you can re-arrange them into

0,\ 1,\ -1,\ 2,\ -2,\ 3,\ -3,\ \dots

and this ordering of \mathbb{Z} is a well-order: it is just a copy of \mathbb{N}'s ordering, so every subset has a least element (the one that appears earliest in the list). The remarkable Well-Ordering Theorem says this is always possible: every set can be well-ordered — even the real numbers. (Nobody can write such an ordering of \mathbb{R} down; its existence rests on the Axiom of Choice.)

// Re-order Z as 0,1,-1,2,-2,... — a well-ordering (a copy of N's order). function zAt(rank: number): number { // rank 0,1,2,3,4,... -> 0,1,-1,2,-2,... return rank % 2 === 1 ? (rank + 1) / 2 : -rank / 2; } const listed: number[] = []; for (let r = 0; r < 9; r++) listed.push(zAt(r)); console.log("Z well-ordered: " + listed.join(", ")); // The least element of ANY subset = whichever appears earliest in this list. console.log("least of {-2, 3, -1} in this order: " + [-1, -2, 3] .sort((a, b) => listed.indexOf(a) - listed.indexOf(b))[0]);

Suppose some non-empty subset A had no least element. Then pick any x_0 \in A; since it isn't least, something smaller x_1 \in A exists; that isn't least either, so x_2 < x_1… and you build an infinite descending chain x_0 > x_1 > x_2 > \cdots. Conversely an infinite descending chain is a non-empty set with no least element. So "every subset has a least element" and "no infinite descent" are two faces of one coin — and the second is exactly why transfinite induction can't run forever.