Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

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.

share|improve this answer
    
I see... Thank you! –  Shir Sivroni Nov 17 '13 at 18:02
    
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$. –  Shir Sivroni Nov 18 '13 at 10:55
    
@Shir: Yes, you are right, you need to slightly modify your approach. I'll slightly modify the answer. –  Asaf Karagila Nov 18 '13 at 11:57
    
I have tried to complete the proof, and eddited what I wrote above. what do you think?? Thanks! –  Shir Sivroni Nov 18 '13 at 14:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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