Proving Zorn's Lemma for Total Order on X: Help Needed

[andytoh]

Question: Show that if r partially orders X, then there exists a total order relation m such that m contains r and m totally orders X. Hint: Consider the collection of partial ordering relations which contain r and use Zorn’s Lemma.



So far, I've proven that if A is the collection of all partial ordering relations on X which contain r, then A has a maximal element m (where the partial order relation on A is set inclusion). Now I'm stuck trying to prove that X is totally ordered by m.

I first assume that m does not totally order X. Then there exist distinct elements a and b in X such that neither (a,b) nor (b,a) are in m. To get my contradiction, I let

s = m U {(a,b)} U {(a,x),(x,b) | x in X}

and tried to show that s partially orders X, thus contradicting the maximality of m in A. But I can't show that antisymmetry and transitivity is met by s. For example, if (x,a),(a,y) belong to s, there's no reason why (x,y) belongs to s. I've tried other constructions for s, but it only made it worse. Can someone suggest an s that works?

 

[Mystic998]

Well, the second one definitely can't be a partial ordering because a and b are assumed to be distinct, but (a,b) and (b,a) are in the set.

Anyway, I think you're going to have to be less sweeping in the other stuff you add to the set (other than (a,b) or (b,a)) because you have to assume that there are at least two elements which aren't related, not that there are only 2. Specifically, the set {(a,x),(b,x),(x,a),(x,b) | x in X} should really only take x that are ordered by m. I don't know if that helps any in proving that it's a partial ordering though. I'm still thinking about it.

As a side note, you could show that there is a partial ordering containing r which does relate a and b. It's more of a constructive proof. But I think the idea is the same either way.

 

[andytoh]

Ok, using some properties of m to construct s is an idea. Also, I haven't been using any properties of r (which m and s contain) in constructing s either. I'll dig into these new ideas.


I'm looking into
s = m U {(a,b)} U {(a,x),(x,b) | (x,a),(a,x),(x,b),(b,x) are in m}

 

[andytoh]

Ok, I think I'm done. Thanks for the help.

 

[andytoh]

Wait, there's still a problem.

s = m U {(a,b)} U {(a,x),(x,b) | (x,a),(a,x),(x,b),(b,x) are in m}

is simply s = m U {(a,b)} since s contains m.