Well-ordering Theorem - Statement and Sketch of Proof

Statement and Sketch of Proof

For every set X, there exists a well ordering with domain X.

The well ordering theorem follows easily from Zorn's Lemma. Take the set A of all well orderings of subsets of X: an element of A is an ordered pair (a,b) where a is a subset of X and b is a well ordering of a. A can be partially ordered by continuation. That means, define E ≤ F if E is an initial segment of F and the ordering of the members in E is the same as their ordering in F. If E is a chain in A, then the union of the sets in E can be ordered in a way that makes it a continuation of any set in E; this ordering is a well ordering, and therefore, an upper bound of E in A. We may therefore apply Zorn's Lemma to conclude that A has a maximal element, say (M,R). The set M must be equal to X, for if X has an element x not in M, then the set M∪{x} has a well ordering that restricts to R on M, and for which x is larger than all elements of M. This well ordered set is a continuation of (M,R), contradicting its maximality, therefore M = X. Now R is a well ordering of X.

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, E, take the union of the sets in E and call it X. There exists a well ordering of X; let R be such an ordering. The function that to each set S of E associates the smallest element of S, as ordered by (the restriction to S of) R, is a choice function for the collection E. An essential point of this proof is that it involves only a single arbitrary choice, that of R; applying the well ordering theorem to each member S of E separately would not work, since the theorem only asserts the existence of a well ordering, and choosing for each S a well ordering would not be easier than choosing an element.