Prove Total Ordering on X with Zorn's Lemma & r Partial Ordering

[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).

 

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

 

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

 

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

 

[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).

 

[andytoh]

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]

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.