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: Partial Order/Upper Bound Proof from How to Prove It

  1. Sep 1, 2010 #1
    Partial Order/Upper Bound Proof from "How to Prove It"

    1. The problem statement, all variables and given/known data
    Suppose R is a partial order on A and B is a subset of A. Let U be the set of all upper bounds for B. Prove that U is closed upward; that is, prove that if x E U and xRy then y E U.


    2. Relevant equations

    N/A

    3. The attempt at a solution

    This is Velleman's:

    Suppose that x E U and xRy. To prove that y E U, we must show that y is an upper bound for B, so suppose that b E B. Since x E U, x is an upper bound for B, so bRx...

    The proof goes on, but I am stuck at the bolded part. How do we know that the relation R is a relation such that, if x > b, then bRx? What if the relation R is defined as: {(x,y) E A x A | x >= y}? Isn't my definition of R reflexive, transitive, and antisymmetric, and therefore partially ordered, as the given states? And wouldn't my definition then mean that, if x > b, it is not true that bRx? Where am I going wrong?

    Thanks in advance.
     
  2. jcsd
  3. Sep 1, 2010 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Partial Order/Upper Bound Proof from "How to Prove It"

    What you wrote is a partial order, but obviously the author intended this partial order is xRy if x<y
     
  4. Sep 1, 2010 #3
    Re: Partial Order/Upper Bound Proof from "How to Prove It"

    But, taking my literalist, unsubtle (more charitably: rigorous) approach, is my objection valid?
     
  5. Sep 2, 2010 #4

    HallsofIvy

    User Avatar
    Science Advisor

    Re: Partial Order/Upper Bound Proof from "How to Prove It"

    No, it is not. There is no "< " defined. The author is taking "aRb" as the order relation and defining "upper bound" in terms of that relation. Saying that "x is an upper bound on set B then, by definition of "upper bound", bRx for all b in B.

    You cannot object to a statement in terms of symbols or relations that have not been defined for that particular statement.
     
  6. Sep 2, 2010 #5
    Re: Partial Order/Upper Bound Proof from "How to Prove It"

    But how is he able to say that bRx immediately follows if x >= all b in B?

    I don't think I understand this part of your answer:

     
  7. Sep 2, 2010 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Partial Order/Upper Bound Proof from "How to Prove It"

    He didn't. He said that bRx follows from x being an upper bound for B.

    You have thoroughly confused yourself by introducing a second partial order and mixing the two of them up.

    If you're studying two orders at once, you really should qualify all order-related terms so you know which order it's related to.
     
  8. Sep 2, 2010 #7
    Re: Partial Order/Upper Bound Proof from "How to Prove It"

    Wait, how is what I said different from what you said? Isn't an upper bound defined as an element that is greater than or equal to every element in some subset?

    In other words, how is "x >= all b in B" different from "x being an upper bound for B"?
     
  9. Sep 2, 2010 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Partial Order/Upper Bound Proof from "How to Prove It"

    Yes. But don't confuse the order R with the order [itex]\leq[/itex]. "x is greater than or equal to y" literally means "yRx" in this order!
     
  10. Sep 2, 2010 #9
    Re: Partial Order/Upper Bound Proof from "How to Prove It"

    >_< How can I not confuse R with <= when you've just said that x >= y implies yRx; in other words, x <= y implies xRy!
     
  11. Sep 2, 2010 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Partial Order/Upper Bound Proof from "How to Prove It"

    I never said I am using the word "greater" relative to the ordering [itex]\leq[/itex]!
     
  12. Sep 2, 2010 #11
    Re: Partial Order/Upper Bound Proof from "How to Prove It"

    I think I'm going to re-read the chapter this question comes from. It's pretty clear I don't understand it very well, since I still can't understand the last post!

    Topic closed, for the time being, I suppose?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook