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

  • 10
    $\begingroup$ Have you tried googling it? I did and got a few good links: plato.stanford.edu/entries/axiom-choice/#MaxPriZorLem planetmath.org/encyclopedia/ProofOfZornsLemma.html $\endgroup$ Jan 8 '12 at 5:50
  • 16
    $\begingroup$ I am against closing the question. As the user who voted to close did not leave an explanation, I can only guess what his reasons were. If it was because this result can be found in many standard references, I do not think this is good enough reason. I believe we have plenty of such questions. If, for example, the proof that that identity is unique in a group is not too trivial for this site, the proof of equivalence of AC and ZL is definitely not too trivial. $\endgroup$ Jan 8 '12 at 7:37
  • 2
    $\begingroup$ George Bergman has a nice handout proving the equivalence of Zorn's Lemma, the Axiom of Choice, the Well-Ordering Theorem, and Bernstein's Theorem; it is in postcript, and here's a link to it. $\endgroup$ Jan 8 '12 at 11:11

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.

  • $\begingroup$ A proof of AC$\Rightarrow$ ZL using Bourbaki-Witt theorem was mentioned in another question $\endgroup$ Apr 14 '12 at 6:06
  • $\begingroup$ can you refer me to a proof for ZL $\Longrightarrow$ AC? $\endgroup$
    – Jneven
    Feb 26 '19 at 10:58
  • 1
    $\begingroup$ @Jneven There are many sources where this proof can be found. (I'd guess that it should be in most standard textbooks of set theory.) Anyway, we can discuss this in set theory chatroom - I'll post there some suggestions I am able to find. $\endgroup$ Feb 26 '19 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.