# proof of Zermelo’s well-ordering theorem

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

$$ |

(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 $$, and therefore for every $x\in X$ there is some $$ 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 $$.

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 $\mathrm{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 |