A Garden of Meditations

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$.

Axiom of Choice $\implies$ Well-ordering