Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


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.