1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Zorn's Lemma Problem

  1. Jan 12, 2008 #1
    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?
    Last edited: Jan 12, 2008
  2. jcsd
  3. Jan 12, 2008 #2
    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.
  4. Jan 12, 2008 #3
    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}
    Last edited: Jan 12, 2008
  5. Jan 12, 2008 #4
    Ok, I think I'm done. Thanks for the help.

    Attached Files:

  6. Jan 12, 2008 #5
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook