# Help with a proof of Zorn's lemma

I am working on a proof of Zorn's lemma using AC, and need some help. I'll skectch main steps, and describe where I am stuck.

Let $(A,<)$ be partially ordered set without any maximal elements, such that every chain (i.e. totally ordered subset) has an upper bound. Let $\mathcal L$ be set of all chains in $A$, and for a chain $L$ let $M(L) \subseteq A$ be set of all upper bounds of $L$.

• Construct a function $h \colon \mathcal L \to A$ such that $h(L) \in M(L)\setminus L$ for every $L\in \mathcal L$. This is OK.
• Define $$\mathcal L_0 = \{L \in \mathcal L \ \colon \ L\neq \emptyset \text{ and for all X \subsetneq L initial segments we have} \ h(X)=\inf_L(L\setminus X)\}.$$ Then one shows that $\mathcal L_0 \neq \emptyset$ and that $(\mathcal L_0, \subseteq)$ is a chain. This is OK.

[ EDIT: Q0: If $L,L' \in \mathcal L_0$ such that $L \subsetneq L'$, how to show that $L$ is initial segment in $L'$? ]

• Define $$\mathcal L_0^\ast = \bigcup_{L \in \mathcal L_0} L \quad \subseteq A.$$ It is obvious that $\mathcal L_0^\ast$ is a chain in $A$. I would like to show more, that $\mathcal L_0^\ast \in \mathcal L_0$ This is where I'm stuck. Let's try. Take any $X \subsetneq \mathcal L_0^\ast$ initial segment (i.e. with the property: $x \in X$, $y \in \mathcal L_0^\ast$, $y<x$ implies $y \in X$). Then the author claims: It is obvious that there exists $Y \in \mathcal L_0$ such that $X \subsetneq Y$. Q1: Why is that obvious? How to prove this? From that unproven claim, we get $$h(X) = \inf_Y(Y\setminus X).$$ What we want to get is $h(X) = \inf_{\mathcal L_0^\ast}(\mathcal L_0^\ast\setminus X)$ of course. Let's take $x_0$ any lower bound for set $\mathcal L_0^\ast \setminus X$. Then again, the author claims: It is obvious that there exists $Y' \in \mathcal L_0$ such that $X \subsetneq Y'$ and $x_0 \in Y'$. Q2: Why is that obvious? How to prove this? When I resolve that, i get $$\inf_Y(Y\setminus X) = h(X) = \inf_{Y'}(Y' \setminus X),$$ from which I get $x_0 \leq \inf_Y(Y\setminus X)$. Then the author concludes: $\inf_Y(Y\setminus X) = \inf_{\mathcal L_0^\ast}(\mathcal L_0^\ast\setminus X)$, but what I miss is Q3: How do I see that $\inf_Y(Y\setminus X)$ is lower bound for $\mathcal L_0^\ast \setminus X$?

The rest is easy: One sees that $\mathcal L_0^\ast \cup \{h(\mathcal L_0^\ast)\} \in \mathcal L_0$, so we get $h(\mathcal L_0^\ast) \in \mathcal L_0^\ast$, contradicting the first step.

I know this is technical, but if anyone has a bit patience to try to help me, I would be very grateful.

-
This is a model question. It provides a good example, for beginners askers on how to ask a question. – leo Jan 28 '13 at 18:40

For your first question, you have $X$ a proper initial segment of $\mathcal{L}_0^*$, so there is an $x\in\mathcal{L}_0^*\setminus X$. By the definition of $\mathcal{L}_0^*$ there must be some $Y\in\mathcal{L}_0^*$ such that $x\in Y$. Clearly $X\subsetneqq Y$, since $y\in Y\setminus X$. This proves the claim, and we now have $h(X)=\inf_Y(Y\setminus X)$.

Clearly $Y\setminus X\subseteq\mathcal{L}_0^*\setminus X$, so $\inf_{\mathcal{L}_0^*}(\mathcal{L}_0^*\setminus X)\le\inf_Y(Y\setminus X)=h(X)$, and we want to show that $h(X)\le\inf_{\mathcal{L}_0^*}(\mathcal{L}_0^*\setminus X)$. At this point I think that you’ve misstated the argument: $x_0$ is not an arbitrary lower bound for $\mathcal{L}_0^*\setminus X$, but rather an arbitrary element of $\mathcal{L}_0^*\setminus X$. The argument that there is a $Y'\in\mathcal{L}_0$ such that $X\subsetneqq Y'$ and $x_0\in Y'$ is essentially identical to the argument answering your first question, and it follows in exactly the same way that $\inf_{Y'}(Y'\setminus X)=h(X)$. And since $x_0\in Y'\setminus X$, we now know that $h(X)\le x_0$. But $x_0$ was an arbitrary element of $\mathcal{L}_0^*\setminus X$, so we’ve shown that $h(X)\le x$ for every $x\in\mathcal{L}_0^*\setminus X$ and hence that $h(X)$ is a lower bound for $\mathcal{L}_0^*\setminus X$. And that’s exactly what we wanted, because it says that

$$h(X)\le\inf_{\mathcal{L}_0^*}(\mathcal{L}_0^*\setminus X)\;.$$

This takes care of your third question as well.

-
Clearly I'm missing something obvious - still didn't get the first question. What is clear to me is just $X \neq Y$. For the inclusion, $z \in X \implies$ ... ? – rafaelm Jan 28 '13 at 2:46
@rafaelm: Every $L\in\mathcal{L}_0$ is an initial segment of $\mathcal{L}_0^*$; does that help? – Brian M. Scott Jan 28 '13 at 2:48
That would solve my problems if I could prove it! So if $x \in L$, $y \in L_1$ and $y<x$, i must see that $y \in L$. If $L_1 \subseteq L$ I am finished, so assume $L \subsetneq L_1$. How can I derive contradiction? I guess using the definition of $\cal L_0$ in some way, but i don't seem to manage it. – rafaelm Jan 28 '13 at 3:19
@rafaelm: Let $z=\inf_{L_1}(L_1\setminus L)$. Let $X=\{u\in L:u<z\}=\{u\in L_1:u<z\}$; $X$ is a proper initial segment of $L_1$, so $u=h(X)$. But $X$ is also a proper initial segment of $L$, so $u=h(X)$ ought to be in $L$. Contradiction. – Brian M. Scott Jan 28 '13 at 3:29
@rafaelm: I just realized what you’re missing that I was taking for granted. Back up and start over. Show that each $L\in\mathcal{L}_0$ is well-ordered by $<$. Then show that if $L,L'\in\mathscr{L}_0$ with $L\ne L'$, then one is a proper initial segment of the other. – Brian M. Scott Jan 28 '13 at 19:22