Zorn's Lemma Implies Zermelo's Well-Ordering Theorem

Theorem

Zorn's Lemma implies Zermelo's Well-Ordering Theorem.

Proof

Let $X$ be a set.

If $X = \O$ the theorem holds vacuously.

Assume $X$ is not empty.

Let $\WW$ be the collection of pairs $\tuple {W, \preceq}$ such that:

$W \subseteq X$

$\preceq$ well-orders $W$

Next, define the partial ordering $\preccurlyeq$ on $\WW$ by $\tuple {W, \preceq} \preccurlyeq \tuple {W', \preceq'}$ if and only if:

$W \subseteq W'$

$\preceq$ is the restriction of $\preceq'$ to $W$

For all $w \in W$ and $w' \in W' \setminus W$: $w \preceq' w'$

To apply Zorn's Lemma, we need to show that every chain in $\WW$ has an upper bound.

Let $\CC \subseteq \WW$ be such a chain.

Then we claim $\bigcup \CC \in \WW$ and $\bigcup \CC$ is an upper bound for $\CC$, where we define $\bigcup \CC$ as:

$\ds \bigcup \CC := \tuple { \bigcup_{ \tuple{W, \preceq} \in \CC } W, \bigcup_{ \tuple{W, \preceq} \in \CC } \preceq }$

First to show $\bigcup \CC \in \WW$.

By Union of Subsets is Subset: Set of Sets:

$\ds \bigcup_{\tuple{W, \preceq} \mathop \in \CC} W \subseteq X$

Next, let $S \subseteq \bigcup_{\tuple {W, \preceq} \mathop \in \CC} W$ be non-empty.

Fix $s \in S$.

Then for some $\tuple {W, \preceq} \in \bigcup \CC$, we have $s \in W$.

Let $w$ be the smallest element of $S \cap W$ with respect to $\preceq$.

Now let $s' \in S$ be arbitrary.

If $s' \in W$, then $w \preceq s'$ and therefore $w \preceq_{\bigcup \CC} s'$.

If $s' \notin W$, then $s' \in W'$ for some $\tuple {W', \preceq'} \in \bigcup \CC$.

But since $\CC$ is a chain, we have:

$\tuple {W, \preceq} \preccurlyeq \tuple {W', \preceq'}$

and therefore, $w \preceq' s'$ since $w \in W$ and $s' \in W' \setminus W$.

Then, by definition, $w \preceq_{\bigcup \CC} s'$.

Thus $w$ is the smallest element of $S$ and we conclude $\bigcup \CC$ is well-ordered.

Therefore $\bigcup \CC \in \WW$.

Now to show $\bigcup \CC$ is the sought upper bound of $\CC$.

We observe, for all $\tuple {W, \preceq} \in \CC$:

$W \subseteq \bigcup_{\tuple {W, \preceq} \mathop \in \CC} W$ by Set is Subset of Union

$\preceq$ is the restriction of $\preceq_{\bigcup \CC}$ to $W$

For all $w \in W$ and $w' \in \bigcup \CC \setminus W$, $w \preceq_{\bigcup \CC} w'$

and conclude that:

$\ds \tuple {W, \preceq} \preccurlyeq \bigcup \CC$

That is, $\ds \bigcup \CC$ is an upper bound of $\CC$.

Thus the hypotheses of Zorn's Lemma hold and we can conclude that $\WW$ has a maximal element.

Let $\tuple {E, \preceq}$ be the maximal element of $\WW$.

Suppose that $E \ne X$.

Then there exists $x_0 \in X \setminus E$.

Define an ordering $\preceq'$ on $E \cup \set {x_0}$ as follows:

$y \preceq' x$ if and only if $x = x_0$ or $x, y \in E$ and $y \preceq x$.

This is a well-order on $E \cup \set {x_0}$ with:

$\struct {E, \preceq} \preccurlyeq \struct {E \cup \set {x_0}, \preceq'}$

This contradicts that $\tuple {E, \preceq}$ is the maximal element of $\WW$.

So $E = X$.

Hence $X$ is well-orderable.

$\blacksquare$

Sources

• 1984: Gerald B. Folland: Real Analysis: Modern Techniques and their Applications: $(\text P.3)$