Well-ordering theorem

Proof from axiom of choice

The well-ordering theorem follows from the axiom of choice as follows.

Let the set we are trying to well-order be ${\displaystyle A}$, and let ${\displaystyle f}$ be a choice function for the family of non-empty subsets of ${\displaystyle A}$. For every ordinal ${\displaystyle \alpha }$, define by transfinite recursion an element ${\displaystyle a_{\alpha }}$ that is in ${\displaystyle A}$ by setting ${\displaystyle a_{\alpha }=f(A\setminus \{a_{\xi }\mid \xi <\alpha \})}$ if this complement ${\displaystyle A\setminus \{a_{\xi }\mid \xi <\alpha \}}$ is nonempty, or leaves ${\displaystyle a_{\alpha }}$ undefined if the complement is empty. That is, ${\displaystyle a_{\alpha }}$ is chosen from the set of elements of ${\displaystyle A}$ that have not yet been assigned a place in the ordering (or undefined if the entirety of ${\displaystyle A}$ has been successfully enumerated). Then the order ${\displaystyle <}$ on ${\displaystyle A}$ defined by ${\displaystyle a_{\alpha }<a_{\beta }}$ if and only if ${\displaystyle \alpha <\beta }$ (in the usual well-order of the ordinals) is a well-order of ${\displaystyle A}$ as desired, of order type ${\displaystyle \{\alpha \mid a_{\alpha }\text{ is defined}\}}$ (in the von Neumann representation).

Proof of axiom of choice

The axiom of choice can be proven from the well-ordering theorem as follows.

To make a choice function for a collection of non-empty sets, ${\displaystyle E}$, take the union of the sets in ${\displaystyle E}$ and call it ${\displaystyle X}$. There exists a well-ordering of ${\displaystyle X}$; let ${\displaystyle R}$ be such an ordering. The function that to each set ${\displaystyle S}$ of ${\displaystyle E}$ associates the smallest element of ${\displaystyle S}$, as ordered by (the restriction to ${\displaystyle S}$ of) ${\displaystyle R}$, is a choice function for the collection ${\displaystyle E}$.

An essential point of this proof is that it involves only a single arbitrary choice, that of ${\displaystyle R}$; applying the well-ordering theorem to each member ${\displaystyle S}$ of ${\displaystyle E}$ separately would not work, since the theorem only asserts the existence of a well-ordering, and choosing for each ${\displaystyle S}$ a well-ordering would require just as many choices as simply choosing an element from each ${\displaystyle S}$.