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!

Least upper bound proof (again)

  1. Aug 18, 2011 #1
    1. The problem statement, all variables and given/known data

    Okay, this is essentially the same question I had in an earlier thread, but i am trying to make my questions and uncertainties more clear for more accurate assistance:


    Suppose R is a partial order on A and B ⊆ A. Let U be the set of all upper bounds for B.
    a) Prove that every element of B is a lower bound for U.
    b) Prove that if x is the greatest lower bound of U, then x is the least upper bound of B.


    2. Relevant equations

    My trouble is in proving part b). Also, I feel part a)- which i have proven below- is used in the part b) proof, I just can't seem to piece the two together appropriately.

    3. The attempt at a solution

    Here is my proof for part a)

    Let b ∈ B. Let u ∈ U. Then by the definition of upper bound, (b,u) ∈ R. Since u was arbitrary, b is a lower bound of U. Since b was arbitrary, every element of B is a lower bound of U.

    To prove part b) obviously you assume the antecedent of the statement to be proven. That is, x is the greatest lower bound of U. You can also assume the result obtained in part a). Now our goal is x is the least upper bound of B. Logically this translates to for all b in B, (b,x) is an element of R. Also, for all u in U, (x,u) is an element of R. So I am trying to prove these separately.

    My confusion begins here:

    Does the antecedent mean x is a lower bound of U AND x is the greatest element of the set of lower bounds of U (which, as far as i can come up with, is A\U)?

    How do you show x is an upper bound of B? I feel this is a start to the rest of the proof.
     
  2. jcsd
  3. Aug 18, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    So far so good.

    Correct.

    This is not true if you're only working with partial orders. Let A=B=[0,1] with the usual ordering and adjoin an element y that has no relationship with elements of A. Then U={1} is the only upper bound of A. But y is not a lower bound of U.

    Take [itex]b\in B[/itex]. We must prove that [itex]b\leq x[/itex]. But b is a lower bound of U and x is the greatest lower bound.
     
  4. Aug 18, 2011 #3
    I guess this was my "intuitive" understanding of the theorem. The only reason I can't seem to formalize it is that translating the antecedent into its logical form poses a problem:

    Since x is the greatest lower bound of U, x is a lower bound of U AND x is the greatest element of the set of lower bounds of U. The first conjunct can be expressed by: for all u in U, (x,u) is an element of R. But for the second conjunct... for all z in (what set then?) (x,z) is an element of (what set)?

    Is that making sense?
     
  5. Aug 18, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The second could be formalized as follows
    if for all u in U it holds that (y,u) in R, then (y,x) is in R.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Least upper bound proof (again)
  1. Least Upper bounds proof (Replies: 11)

Loading...