proof of Zermelo’s well-ordering theorem

Let $X$ be any set and let $f$ be a choice function on $\mathcal{P}(X)\setminus\{\emptyset\}$ . Then define a function $i$ by transfinite recursion on the class of ordinals as follows:

i(\beta)=f(X-\bigcup_{\gamma<\beta}\{i(\gamma)\})\text{ unless }X-\bigcup_{% \gamma<\beta}\{i(\gamma)\}=\emptyset\text{ or }i(\gamma)\text{ is undefined % for some }\gamma<\beta

(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 $\beta=i^{-1}[X]=\{\gamma\mid i(\gamma)=x\text{ for some }x\in X\}$ . Since $\beta$ is a set of ordinals, it cannot contain all the ordinals (by the Burali-Forti paradox).

Since the ordinals are well ordered, there is a least ordinal $\alpha$ not in $\beta$ , and therefore $i(\alpha)$ is undefined. It cannot be that the second unless clause holds (since $\alpha$ is the least such ordinal) so it must be that $X-\bigcup_{\gamma<\alpha}\{i(\gamma)\}=\emptyset$ , and therefore for every $x\in X$ there is some $\gamma<\alpha$ such that $i(\gamma)=x$ . Since we already know that $i$ is injective, it is a bijection between $\alpha$ and $X$ , and therefore establishes a well-ordering of $X$ by $x<_{X}y\leftrightarrow i^{-1}(x)<i^{-1}(y)$ .

The reverse is simple. If $C$ is a set of nonempty sets, select any well ordering of $\bigcup 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