# Zorn's Lemma Problem

1. Apr 24, 2008

### andytoh

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: Apr 24, 2008
2. Apr 24, 2008

### Dick

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: Apr 24, 2008
3. Apr 25, 2008

### andytoh

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: Apr 25, 2008
4. Apr 25, 2008

### Dick

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.

5. Apr 25, 2008

### andytoh

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: Apr 25, 2008
6. Apr 25, 2008