# equivalence of Zorn’s lemma and the axiom of choice

Let $X$ be a set partially ordered by $$ such that each chain has an upper bound. Define $$. Let $p(X)=\{p(x)\mid x\in X\}$. If $p(x)=\mathrm{\varnothing}$ then it follows that $x$ is maximal.

Suppose no $p(x)=\mathrm{\varnothing}$. Then by the axiom of choice^{} (http://planetmath.org/AxiomOfChoice) there is a choice function $f$ on $p(X)$, and since for each $p(x)$ we have $f(p(x))\in p(x)$, it follows that $$. Define ${f}_{\alpha}(p(x))$ for all ordinals^{} $\alpha $ by transfinite induction^{}:

${f}_{0}(p(x))=x$

${f}_{\alpha +1}(p(x))=f(p({f}_{\alpha}(p(x))))$

And for a limit ordinal^{} $\alpha $, let ${f}_{\alpha}(p(x))$ be an upper bound of ${f}_{i}(p(x))$ for $$.

This construction can go on forever, for any ordinal. Then we can easily construct an injective function from $Ord$ to $X$ by $g(\alpha )={f}_{\alpha}(p(x))$ for an arbitrary $x\in X$. This must be injective, since $$ implies $$. But that requires that $X$ be a proper class^{}, in contradiction^{} to the fact that it is a set. So there can be no such choice function, and there must be a maximal element^{} of $X$.

For the reverse, assume Zorn’s lemma and let $C$ be any set of non-empty sets. Consider the set of functions $F=\{f\mid \forall a\in \mathrm{dom}(f)(a\in C\wedge f(a)\in a)\}$ partially ordered by inclusion. Then the union of any chain in $F$ is also a member of $F$ (since the union of a chain of functions is always a function). By Zorn’s lemma, $F$ has a maximal element $f$, and since any function with domain smaller than $C$ can be easily expanded, $\mathrm{dom}(f)=C$, and so $f$ is a choice function for $C$.

Title | equivalence of Zorn’s lemma and the axiom of choice |
---|---|

Canonical name | EquivalenceOfZornsLemmaAndTheAxiomOfChoice |

Date of creation | 2013-03-22 12:59:04 |

Last modified on | 2013-03-22 12:59:04 |

Owner | Henry (455) |

Last modified by | Henry (455) |

Numerical id | 10 |

Author | Henry (455) |

Entry type | Proof |

Classification | msc 03E25 |