I have the following proof and there are some steps I do not understand. Can anyone explain to me what is going on?

Claim: (AC) $\implies$ Zorn's lemma


Assume that $S$ is a partial ordered set, and that every chain in $S$ has an upper bound. To show: $S$ has a maximal element.

For $A\subset S$ define $\Delta(A):=\{y\in S:\forall x\in A(y>x)\}$. Let $f:\mathcal{P}\to S$ be a choice function. For $A\subset S$ define \begin{equation} U(A)= \begin{cases} f(\Delta(A)),\ \text{ for }\Delta(A)\neq\emptyset\\ f(S),\ \text{ otherwise } \end{cases} \end{equation}

Use transfinite recursion: There exists a class function $G:\Omega\to V$ such that \begin{equation} \begin{cases} G(\alpha)=U(G\mid_\alpha)\\ G(\emptyset)=U(\emptyset)=f(S)=:a_0\\ \end{cases} \end{equation} where $G\mid_\alpha=\{\langle\beta,G(\beta)\rangle:\beta\in\alpha\}$. Hartogs theorem implies that there exists an ordinal $\gamma\in\Omega$ for which there is no injection $\gamma\to S$. Then $G(\gamma)=a_0$.

What is this proof doing actially? I think the idea is to construct a chain which is actually $S$ but I do not see how is it doing here. And what about the conclusion? Can someone give me the missing details?

Thank you

  • 1
    $\begingroup$ The least you can do when someone actually puts energy into writing an answer is to indicate that you have read it. If you also want to add whether or not you found it useful, not very useful, or why, that's even better. But at least some indication that I didn't waste my time would be great. $\endgroup$ – Asaf Karagila Aug 10 '16 at 6:05
  • 1
    $\begingroup$ @AsafKaragila I think I have done this by voting the answer I found useful and putting votes... What am I missing? $\endgroup$ – sky90 Aug 10 '16 at 6:11
  • 1
    $\begingroup$ Voting is anonymous. I couldn't have known that you were one of the voting parties until 30 seconds ago. $\endgroup$ – Asaf Karagila Aug 10 '16 at 6:12

Here's the intuition behind the proof. You want to find a maximal element of $S$. How do you find it? You start with an element $s_0\in S$. If $s_0$ is maximal, you're done. If not, then you can find a bigger element $s_1\in S$. If $s_1$ is maximal, you're done. If not, you can find a bigger element $s_2\in S$. If $s_2$ is maximal, you're done. If not, ...

OK, so you keep repeating this. But what if you define $s_0<s_1<s_2<\dots$ for infinitely many steps without ever finding a maximal element? Then $\{s_0,s_1,s_2,\dots\}$ is a chain, so by hypothesis it has an upper bound. Choose such an upper bound and call it $s_\omega$. Now we can start the process all over: if $s_\omega$ is maximal, we're done. Otherwise, choose a larger element and call it $s_{\omega+1}$. If $s_{\omega+1}$ is maximal, we're done. And so on.

You can continue this process defining $s_\alpha$ for ordinals $\alpha$ by induction. If $s_\alpha$ is ever maximal, you win. If $s_\alpha$ is not maximal, define $s_{\alpha+1}$ to be something bigger than $s_\alpha$. If $\alpha$ is a limit ordinal and you've defined $s_\beta$ for all $\beta<\alpha$, all the $s_\beta$ you have defined so far form a chain, so choose an upper bound for this chain and call it $s_\alpha$.

By Hartogs' theorem, this process can't go on forever, since it would give an injection from all the ordinals to $S$. The only way it can stop is if you find a maximal element. Therefore, you will eventually find a maximal element.

The proof is just making the idea above a bit more precise. Instead of describing an iterative inductive process, it more rigorously invokes transfinite recursion to give a definition of the function $G$ (what it calls $G(\alpha)$ is what I called $s_\alpha$) all at once. And the axiom of choice is used in a key way. At each step of the induction, you need to choose an element $s_{\alpha+1}>s_\alpha$, or an upper bound for your chain. In order to make all these choices, you use the axiom of choice to name a choice function $U$ ahead of time which you will use to make all the choices.

  • $\begingroup$ Thank you for your explanations. That was helpful. I would still have just some questions more: As you said, I am constructing my chain by using the function $G$, and with this I am fine. By Hartog's theorem the process has to end, and for this to hold, I need that $\Delta(G\mid_\alpha)=\emptyset$ implying that there exists a smallest $\alpha\in\Omega$ such that $G(\alpha)=a_0$. But $a_0$ is not the maximal element, that's just the last term where the chain terminate. Now I have to conclude by saying that this holds for any ordinal, since I am using transfinite recursion. $\endgroup$ – sky90 Aug 10 '16 at 5:11
  • $\begingroup$ So I have to look at three cases: If $\alpha=\emptyset$ then $a_0$ is already maximal and the claim holds. If $\alpha=\beta+1$ then the element $a_\beta$ is the maximal element of $S$ by construction. If $\alpha$ is a limit ordinal my notes claims that $G(\alpha)$ is a maximal element of the chain $G\mid_\alpha$ meaning that every upper bound of the chain is bigger than $a_\beta$ for all $\beta\in\alpha$ then we would have $G(\alpha)\neq a_0$. Could you tell me if I am right with the conclusion and what is actually going on in this last case? thanks once again $\endgroup$ – sky90 Aug 10 '16 at 5:11
  • 1
    $\begingroup$ The first two cases are right. In the last case, the key point is that $\Delta(G|_\alpha)\neq\emptyset$, since the range of $G|_\alpha$ is a chain and hence has an upper bound in $S$. Thus $G(\alpha)$ will be defined to be $f(\Delta(G|_\alpha))$ and will not be $a_0$. $\endgroup$ – Eric Wofsey Aug 10 '16 at 5:22
  • $\begingroup$ Ok but then you have a contradiction... what can I get from it? In order to prove something by using transfinite induction the statement has to hold for limit ordinals to right? $\endgroup$ – sky90 Aug 10 '16 at 5:35
  • 1
    $\begingroup$ Well, what you've shown is that if you take the least $\alpha>0$ such that $G(\alpha)=a_0$, then $\alpha$ can only be a successor, and then if $\alpha=\beta+1$, $G(\beta)$ is a maximal element of $S$. $\endgroup$ – Eric Wofsey Aug 10 '16 at 5:39

This proof uses transfinite recursion to construct a chain. Then arguing that it has an upper bound, by the assumption on the partial order, which has to be a maximal element.

The construction is simple, if there is a way to extend the chain by adding a proper upper bound, use the axiom of choice to choose an element for this extension. If not, then we had to have a maximal element already. This process has to stop since otherwise we constructed an injection from the class of ordinals into our set. Which we know we cannot do.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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