Show that Zorns lemma follows from AC

[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.

If anybody has solved it, please help me.

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

 

[Hurkyl]

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!

 

[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.

 

[Kontilera]

Thanks for the answers! I think I follow :)
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

 

[Hurkyl]

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

 

[Hurkyl]

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.

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.

 

[micromass]

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.

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