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

  • $\begingroup$ Just because I didn't have the time to fully read your new question doesn't mean you have to post a new one. $\endgroup$ – Asaf Karagila Nov 18 '13 at 18:00
  • $\begingroup$ ah, sorry.. my impationt charachter strikes me again.. :( $\endgroup$ – topsi 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.

Now you need to decide whether:

  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$;
  2. or you allow an upper bound from the chain in case it has no proper upper bounds, in which case you stabilize when you reach the maximal element;
  3. or you allow upper bounds to be taken from the chain itself, in which case you have to argue why you're not picking the same element over and over all the time.

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$.

  • $\begingroup$ Got it. I will think about it. Thank you!!! $\endgroup$ – topsi Nov 18 '13 at 18:37

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.