1. Not finding help here? Sign up for a free 30min 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!

Zorn's Lemma Problem

  1. Apr 24, 2008 #1
    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. jcsd
  3. Apr 24, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

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

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  6. Apr 25, 2008 #5
    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
  7. Apr 25, 2008 #6
    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 }.
     
  8. Apr 25, 2008 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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: Apr 25, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Zorn's Lemma Problem
  1. Zorn's lemma problem (Replies: 15)

  2. Zorn's Lemma Problem (Replies: 4)

  3. Banach's Lemma (Replies: 1)

Loading...