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
Proof:
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
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.