# Show that Zorns lemma follows from AC

1. May 28, 2012

### Kontilera

Hello!
I´m currently reading Halmos - 'Naive Set Theory' on my own and try to solve the problems that the author has supplied by myself. When it comes to the chapter of Zorns Lemma I feel a bit confused and have not manage to solve the problem in the end of the chapter.. In other words to show that Zorns Lemma follows from the Axiom of Choice.

I do not have the book with me right now, but can qoute the whole question when I get back home. Thanks in advance!

/ Kontilera

2. May 28, 2012

### Hurkyl

Staff Emeritus
I haven't done this exercise myself, and my instincts would involve a combination of the well-ordering theorem along with choice.

At first glance, there seem to be two clear leads:

• Find a collection whose choice function would yield a maximal element (or could be used to construct one
• Set up a situation with a choice that would only be possible if there isn't a maximal element, and derive a contradiction

I have ideas about how the second one would work, but I haven't thought them through yet -- I don't want to present a polished suggestion, instead I want to point out the thought process one might go through!

3. May 28, 2012

### AKG

Assume choice and let $(P,<)$ be a poset satisfying the hypotheses of Zorn's Lemma, but failing to have a maximal element. Let $X$ be the collection of subsets of $P$ which are well-ordered by $<$. Let

$F : X \to \mathcal{P}(P)\setminus \{\emptyset\}$

be such that $F(x)$ is the set of all strict upper bounds for $x$. Such an $F$ exists by the assumptions on $P$. Let $f : X \to P$ be a choice function on the sequence of sets $\langle F(x) | x \in X\rangle$. Now, one can use transfinite recursion to build a well-ordered subset of $P$ of arbitrarily large order type (using $f$ to choose the next element of the subset at each stage of the recursion), contradicting Hartog's Lemma.

4. May 29, 2012

### Kontilera

Planning to read these chapters again to make sure I understand everything. Is there any nice way to show the opposite, i.e. that AC follows from Zorns lemma?

Best Regards
Kontilera

5. May 29, 2012

### Hurkyl

Staff Emeritus
The poset of partial choice functions would work, I think.

6. May 29, 2012

### Hurkyl

Staff Emeritus
It would be nice if there was a "pure choice" approach, rather than resorting to transfinite iteration, which in my mind counts as a "well-ordering theorem"-type proof.

7. May 29, 2012

### micromass

Here is a proof without transfinite induction: http://www2u.biglobe.ne.jp/~nuida/m/doc/ACtoZorn_v2.pdf