• Support PF! Buy your school textbooks, materials and every day products Here!

Zorn's Lemma Problem

  • Thread starter andytoh
  • Start date
359
3
If r is partial ordering on X, prove that r is contained in a total ordering on X. Hint: Consider the collection of all partial orderings containing r. Use Zorn's Lemma.

I've already proven using Zorn's Lemma that there exists a maximal partial ordering m containing r. But I can't seem to prove that m is a total ordering. Suppose a and b are not comparable by m. I tried to prove that m U {(a,b)} is a partial ordering (to contradict the maximality of m), but can't. What's the correct contradiction? How about I make b greater than every element in X (that is not already greater than b)? Nope that doesn't work either (transitivity fails).
 
Last edited:

Answers and Replies

Dick
Science Advisor
Homework Helper
26,258
618
If you call the relation '>' and if a and b are unrelated then suppose you just define a>b. The only way you could be wrong is if there is an element c such that a<c and c<b, right? Because it would fail transitivity. If you define b>a then the only way you could be wrong is if there is an element d such that a>d and d>b, also right? So the only way you could be wrong both ways if there are both. And there can't be both. Since that would violate transitivity. So you must be able to extend the order relation. So it's not maximal? I'm putting lot of question marks because it's a long time since I looked at this stuff. I'm only replying because no one more knowledgeable has.
 
Last edited:
359
3
Thanks. But suppose we define a<b, and we have c<a but there is no relation between c and b at all? (remember that so far we only know that the maximal element is a partially ordered set only), or if we have b<d but there is no relation between a and d? Same problem if we define a>b.
 
Last edited:
Dick
Science Advisor
Homework Helper
26,258
618
The only thing that would prevent you from DEFINING a<b is the existence of another element that is related to both a and b. If there is no such element then you can just define the relation a<b. And nobody gets hurt.
 
359
3
But if we define a<b, and we have c<a from our maximal partial ordering (for example) but no relation between c and b in our maximal partial ordering, then transitivity also fails because we don't have c<b when we are supposed to. So we can define c<b, but I've checked that this runs into problems too (due to the many other cases).
 
Last edited:
359
3
How about

m U { (a, x), x in X such that (b, x) in m } U { (x, b), x in X such that (x, a) in m }.
 
Dick
Science Advisor
Homework Helper
26,258
618
How about

m U { (a, x), x in X such that (b, x) in m } U { (x, b), x in X such that (x, a) in m }.
I see what you mean. You can't just define a>b. You also have to define all of the other relations needed by transitivity. But I don't think there is any problem doing that once you've made the choice between a>b and b>a. As you did above.
 
Last edited:

Related Threads for: Zorn's Lemma Problem

  • Last Post
Replies
15
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
829
Replies
6
Views
1K
Replies
2
Views
755
Replies
2
Views
854
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
3
Views
2K
Top