Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
8  
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 –  Scaramouche Jan 8 '12 at 5:50
2  
Why did you tag this under general topology? –  Asaf Karagila Jan 8 '12 at 7:15
8  
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. –  Martin Sleziak Jan 8 '12 at 7:37
5  
@AbcdJ: Not knowing on the tag for [axiom-of-choice] is one thing, it does not explain why [general-topology] :-) –  Asaf Karagila Jan 8 '12 at 7:53
1  
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. –  Arturo Magidin Jan 8 '12 at 11:11

2 Answers 2

up vote 5 down vote accepted

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 $P_a = \{x\in P\mid a<x\}$ which are non-empty, i.e. for non-maximal $a$.

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 in $P$ and therefore bounded, thus $\bigcap_{\alpha<\beta} P_\alpha\neq\varnothing$, and let $a_\beta=f(\bigcap_{\alpha<\beta} P_\alpha)$.

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.

share|improve this answer

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.

share|improve this answer
    
A proof of AC$\Rightarrow$ ZL using Bourbaki-Witt theorem was mentioned in another question –  Martin Sleziak Apr 14 '12 at 6:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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