equivalence of Zorn’s lemma and the axiom of choice
Let be a set partially ordered by such that each chain has an upper bound. Define .Let . If then it follows that is maximal.
Suppose no . Then by the axiom of choice (http://planetmath.org/AxiomOfChoice) there is a choice function on , and since for each we have , it follows that . Define for all ordinals
by transfinite induction
:
And for a limit ordinal , let be an upper bound of for .
This construction can go on forever, for any ordinal. Then we can easily construct an injective function from to by for an arbitrary . This must be injective, since implies . But that requires that 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 .
For the reverse, assume Zorn’s lemma and let be any set of non-empty sets. Consider the set of functions partially ordered by inclusion. Then the union of any chain in is also a member of (since the union of a chain of functions is always a function). By Zorn’s lemma, has a maximal element , and since any function with domain smaller than can be easily expanded, , and so is a choice function for .