Zorn's Lemma And Axiom of Choice

How can I prove Zorn's lemma is equivalent to Axiom of choice?

Assume the axiom of choice. Let $(P,\le)$ a partially ordered set that every chain has an upper bound. Let $f$ to be a choice function from all non-empty subsets of $P$, and let $P_a = \{x\in P\mid a<x\}$ then $P_a=\varnothing$ if and only if $a$ is a maximal element.

We define by using transfinite induction:

Let $a_0$ be an element of $P$, if it is maximal then we have finished. Otherwise $P_0 = \{x\in P\mid a_0<x\}$ is non-empty, let $a_1 = f(P_0)$.

Suppose $a_\alpha$ was defined, if it is maximal then we are done, otherwise $P_\alpha=\{x\in P\mid a_\alpha<x\}$ is non-empty and $a_{\alpha+1} = f(P_\alpha)$.

If $\alpha$ is a limit ordinal, and for all $\beta<\alpha$ we have chosen $a_\beta$, then $\{a_\beta\mid \beta<\alpha\}$ is a chain without a maximal element in $P$, and therefore bounded with an upper bound above all the elements of the chain, thus $\bigcap_{\beta<\alpha} P_\beta\neq\varnothing$, and let $a_\alpha=f(\bigcap_{\beta<\alpha} P_\beta)$.

We argue that this must stop at some point, otherwise we have an injection from the proper class of the ordinals into the set $P$. Why did the process stop? It can only stop if we have reached a maximal element at some $a_\gamma$, as wanted.

Assume Zorn's lemma, and let $X$ be a non-empty collection of non-empty sets. Let $(C,\subseteq)$ be the set of all choice functions from some elements of $X$.

This is a non-empty set, since we can always choose from finitely many sets. Given a chain of choice functions, the union is indeed a function. So the condition of Zorn's lemma is satisfied. We have a maximal element $f$.

If $f$ is not a choice function from all the members of $X$ then we can extend it to one more element, which contradicts the maximality.

Even though this is a standard result, which can be found elsewhere (probably in most standard textbooks and lecture notes on set theory); I think some brief discussion and giving some pointers could be useful.

Perhaps the first important thing is to stress that when you want show that something is equivalent to Axiom of Choice, you have to work in an axiomatic systems where AC is not an axiom. I would say ZF is used most frequently.

The proof of ZL $\Rightarrow$ AC is similar to most applications of Zorn's lemma. We want to show that there exists a selector (choice function). This selector is obtained from ZL as maximal partial selector. So the only thing is to show that union of a chain (w.r.t. inclusion) of partial functions, which select one element from each set is again such a function.

The proof of AC $\Rightarrow$ ZL which I like best relies on transfinite induction. We assume that there is a set which fulfills the assumptions of ZL and has no maximal elements. In this way we inductively construct a chain with no upper bound. The use of AC is to select some element from the non-empty set of upper bounds of already selected elements in each step. This kind of proof assumes that we already know something about ordinals and transfinite induction; but I think that this technique is very useful in general.

However, for various reasons, some authors prefer to avoid using transfinite induction. As an example I can mention the papers of Weston and Lewin bellow. As I mentioned, the proof can be found in almost all standard textbooks. I've included Devlin and Halmos, to give at least one example of a book which uses ordinals in this proof and one example of a book which avoids them.

Some references:

• J. D. Weston: A short proof of Zorn's Lemma, Archiv der Mathematik, Volume 8, Number 4, 279, DOI: 10.1007/BF01898788. One page long proof of AC $\Rightarrow$ ZL without using transfinite induction.

• Lewin, J. (1991). A simple proof of Zorn's lemma. The American Mathematical Monthly, 98(4), pp. 353-354. jstor Another short proof of AC $\Rightarrow$ ZL avoiding the use of ordinals.

• K. Devlin: Joy of Sets. Theorem 2.7.5 on p.60 gives the proof of AC $\Rightarrow$ ZL using transfinite induction. The opposite implications is given as a series of implications in theorems following this one.

• P. Halmos: Naive Set Theory, p.62. Halmos chooses approach avoiding the transfinite induction.