I am trying to prove that well ordering principle implies Zorn's Lemma. I think that I'm close but don't quite know to make the last step of my proof. Here is what I wrote so far:

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 a maximal element, 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


1 Answer 1


Some issues:

  1. Zorn's lemma is about partial ordered sets where every chain has an upper bound, not a maximal element. It can be very easy to arrange a chain without a maximal element in a partial ordered set which has an infinite chain to begin with.

  2. Using $\kappa^+$ to denote $\kappa\setminus\{\varnothing\}$ is a horrible choice of notation, since $\kappa^+$ denotes the successor cardinal of $\kappa$.

  3. You need to slightly modify the construction of the chain. Suppose that $\{g(\beta)\mid\beta<\alpha\}$ were defined, then $g(\alpha)$ is the least (in the well-order) such that $\{g(\beta)\mid\beta\leq\alpha\}$ is a chain. If no such choice is possible, then $\{g(\beta)\mid\beta<\alpha\}$ is a maximal chain already.

  4. You didn't have to use contradiction here.

  • $\begingroup$ I have thought about it and still have a problem. I don't think that the chain is neccesarly maximal. For instance, if $\alpha$ is a successor ordinal and $\alpha = \beta + 1$, I took, $g(\alpha)$ to be the first element $a$ by $S$ s.t. $g(\beta) < a$. but, as I understand the construction, there could be an element $g(\beta)<_{R}x<_{R}a$ in $A$. $\endgroup$
    – topsi
    Nov 18, 2013 at 10:55
  • $\begingroup$ @Shir: Yes, you are right, you need to slightly modify your approach. I'll slightly modify the answer. $\endgroup$
    – Asaf Karagila
    Nov 18, 2013 at 11:57
  • $\begingroup$ I have tried to complete the proof, and eddited what I wrote above. what do you think?? Thanks! $\endgroup$
    – topsi
    Nov 18, 2013 at 14:50

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.