# Zorn's Lemma, Choice, & Well-ordering

These three very powerful axioms in set theory turn out to be equivalent, and it is not easy to see why. To review what they say,

1. Zorn’s Lemma : a partially ordered set with upper bounds for every totally ordered subset has at least one maximal element
2. Axiom of Choice : if $F$ is a function on $I$ such that $F(i)\neq\phi, \forall i\in I$, then there exists a choice function $f$ on $I$ such that $f(i)\in F(i), \forall i\in I$
3. Well-ordering Principle : every set can be totally ordered

As the popular joke goes

The Axiom of Choice is obviously true, the Well-ordering principle is obviously false; and who can tell about Zorn’s Lemma?

# Zorn’s Lemma $\implies$ Axiom of Choice

1. Define $X$ as the partially successful attempts to construct a choice function, i.e. set of pairs $\langle J, g\rangle$ such that $J\subset I$ and $g$ is a partial choice function on $J$.
2. Define a partial order on $X$ as

$\langle J, g\rangle\leq \langle J', g'\rangle\\ \iff\\ J\subset J'\textrm{ and } g = g'|_J (\textrm{i.e. g' extends g})$
3. If $Y$ is any totally ordered subset of $X$, then we can construct a maximal element $\langle \bar{J}, \bar{g}\rangle$ as follows

$\bar{J} = \bigcup_{\langle J, g \rangle\in Y} J,\\ \bar{g}(j) = g(j),\textrm{ for any defined } g(j)\in Y$

Observe that total ordering of $Y$ forces a unique choice for $g(j)$.

4. Thus, by Zorn’s Lemma there exists a maximal element $\langle J_{max}, g_{max}\rangle$. Now it suffices to prove that $J_{max} = I$, as it implies $g_{max}$ is the choice function on $I$.
5. Assume on the contrary that $i\in I$ and $i\not\in J_{max}$. Then we can extend $\langle J_{max}, g_{max}\rangle$ as $\langle J_{max}\cup \{ i \}, g_{max}\cup (g_{max}(i) := a)\rangle$ for any $a\in F(i)$, contradicting maximality. Note that choosing any $a\in F(i)$ is not the same as the Axiom of Choice – making a single arbitrary choice only requires ZF axioms (exercise : try to prove!), whereas the latter is about making arbitrary choices arbitrary number of times.

# Well-ordering $\implies$ Zorn’s Lemma

The intuition behind this proof is to construct a totally ordered subset $B$ of a set $A$ satisfying the antecedent of Zorn’s lemma such that $B$ has no strict upper bound, forcing any upper bound to be the maximal element in $A$.

TODO