proof of Zermelo’s well-ordering theorem

Let X be any set and let f be a choice function on 𝒫(X){}. Then define a function i by transfinite recursion on the class of ordinalsMathworldPlanetmathPlanetmath as follows:

i(β)=f(X-γ<β{i(γ)}) unless X-γ<β{i(γ)}= or i(γ) is undefined for some γ<β

(the function is undefined if either of the unless clauses holds).

Thus i(0) is just f(X) (the least element of X), and i(1)=f(X-{i(0)}) (the least element of X other than i(0)).

Define by the axiom of replacement β=i-1[X]={γi(γ)=x for some xX}. Since β is a set of ordinals, it cannot contain all the ordinals (by the Burali-Forti paradoxMathworldPlanetmath).

Since the ordinals are well ordered, there is a least ordinal α not in β, and therefore i(α) is undefined. It cannot be that the second unless clause holds (since α is the least such ordinal) so it must be that X-γ<α{i(γ)}=, and therefore for every xX there is some γ<α such that i(γ)=x. Since we already know that i is injectivePlanetmathPlanetmath, it is a bijection between α and X, and therefore establishes a well-ordering of X by x<Xyi-1(x)<i-1(y).

The reverse is simple. If C is a set of nonempty sets, select any well orderingMathworldPlanetmath of C. Then a choice function is just f(a)= the least member of a under that well ordering.

Title proof of Zermelo’s well-ordering theorem
Canonical name ProofOfZermelosWellorderingTheorem
Date of creation 2013-03-22 12:59:07
Last modified on 2013-03-22 12:59:07
Owner Henry (455)
Last modified by Henry (455)
Numerical id 9
Author Henry (455)
Entry type Proof
Classification msc 03E25