# well ordering principle implies Zorn's Lemma

In here: Proving that well ordering principle implies Zorn's Lemma. I asked how to finish a proof of this statement. After a few helpful remarks, I think I have managed to finish it. What do you think?

Given that on every set, a well ordering can be defined, we should prove that Given a partially ordered set $A$, if every increasing chain in $A$ has an upper bound in $A$, Then $A$ has a maximal element.

Proof: Take $A$ partially ordered by $R$. We know that there exists a well ordering $S$ on $A$. Let $k$ be the smallest ordinal s.t. $k=|A|$ and let, $k^+=k+1$. Define by transfinite induction, a function, $g:k^+ \rightarrow A$ as follows:

1. $g(0)$ is the first element in $A$ by $S$.

For any , $\alpha < k^+$:

1. If $\alpha$ is a successor ordinal, s.t. $\alpha = \beta + 1$, then, define $g(\alpha)$, the first element (by $S$), $a \in A$ such that $g(\beta) <_{R} a$

2. if $\alpha$ is a limit ordinal, then, The set $\{g(\beta);\beta<\alpha\}$, is linearly ordered by $R$. Therefor it has an upper bound. From all the uppers bounds, we will take the first (By $S$) to be $g(a)$.

3. $g(k^{+})$ is linearly ordered. So, by the lemma assumption, it has an upper bound in $M \in A$.

4. We claim that $M$ is a maximal element of $A$. Because, if there would be $x >_{R} M$ in $A$, by the construction of $g$, $g(k^{+})$ would contain an element which ia greater or equall (by $R$) to $x$, contradicting the fact that $M$ is an upper bound of $g(k^{+})$.

The step which I'm not sure of is step 5. I am not sure weather the fact that $|k|=|A|$ and that $g(k^{+})$ is isomorphic to $k$ are enough. What do you think?

Thank you! Shir

-
Just because I didn't have the time to fully read your new question doesn't mean you have to post a new one. –  Asaf Karagila Nov 18 '13 at 18:00
ah, sorry.. my impationt charachter strikes me again.. :( –  Shir Sivroni Nov 18 '13 at 18:12

There is an issue here. Note that if $A$ is infinite then $k$ is a limit ordinal. This means that the induction, if resumed up to $k$, must stop before it. Otherwise you will have exhausted the entire set $A$, but it cannot have a maximal element.
1. you always take a strict upper bound (i.e. not one of the elements chosen so far), in which case you will have to run into a maximal element before exhausting the ordinals below $k$;
I suggest the second case. Then you have to argue that the upper bound is in fact maximal. Either by arguing towards contradiction if you chose the first case; or by showing that directly in the second case. The idea is that if it weren't maximal then $\{g(\alpha)\mid\alpha<k\}$ is a chain, and has an upper bound, but this upper bound has to be with index $\alpha<k$ in the order $S$; therefore it is a contradiction to the choice of $g(\beta)$ where $\beta$ is the first time we chose $g(\beta)$ with index $\geq\alpha$.