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!

Ordered relations, lower upper bounds of a set

  1. Oct 14, 2014 #1
    1. The problem statement, all variables and given/known data
    Suppose that R is a partial order on A, B1 ⊆ A, B2 ⊆ A, x1 is the least
    upper bound of B1, and x2 is the least upper bound of B2. Prove that if
    B1 ⊆ B2 then x1Rx2.

    2. Relevant equations


    3. The attempt at a solution
    I split the proof into two different cases:

    case 1: x_1 is an element of B_1, therefore (x_1 R x_2)

    case 2: x_1 is not an element of B_1 then there are two subcases:

    case 2a: x_1 is an element of B_2, therefore (x_1 R x_2)

    case 2b: x_1 is not an element of B_2, therefore since x_1 is the least upper bound of B_1 and since x_1 is in neither B_1 or B_2, x_1 is an upper bound of B_2, in fact x_1 is the least upper bound of B_2 therefore (x_1 R x_2) by reflexivity of partial orders.

    It's pretty straightforward for cases 1, and 2a, but for 2b how would I represent this mathematically? In my proof it relies on the fact that x_1 is the lowest upper bound of B_2 when
    a) it is a lowest upper bound of B_1
    b) it is not in either B_1 or B_2
    c) B_1 is a subset of B_2

    I can understand why it works, but I am just unsure of how to write it down.
     
  2. jcsd
  3. Oct 14, 2014 #2

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Is this true? What about if ##A=\mathbb{R}##, ##B_1 = [0,1)##, and ##B_2 = [0,1)\cup(1,2]## and the usual ##\le## is the relation?

     
  4. Oct 14, 2014 #3

    RUber

    User Avatar
    Homework Helper

    You might be able to get at it more quickly by contradiction.
     
  5. Oct 15, 2014 #4
    You're right, my case-by-case is actually a contradiction, sorry about that.

    But then I'd have to deal with a negative that doesn't really provide much information for an arbitrary partially ordered relation, since the conditions of the relations are undefined. I did attempt it but I ran into a dead end. Could you give me a hint for this method if it is possible?

    I tried other case-by-case but all of them ended up being contradictions.

    I tried the case where ##x_2## is the only element of ##U_2## where ##U_2 = \{u \in A | \forall b \in B_1 (bRu)\}##, i.e. it is the only upper bound, in order to prove that it is the largest element of ##A## since that would easily lead to the conclusion that for ##x_1##, an element of A, ##x_1 R x_2##

    The other case being where it is not the only element of ##U_2##, i.e. there are multiple upper bounds for ##B_2##.

    Even if ##x_2## is the only element of ##U_2##, that doesn't necessitate that it is the largest element though, example:

    $$A = \{ \emptyset , \{0\}, \{1\}, \{2\}, \{0,1\} \}$$ where the ordered relation, ##R##, is the subset relation on ##A##.
    Then R is a partially ordered relation on A
    Let ##B_1 =\{\{2\}\}## and ##B_2 = \{\{2\}, \emptyset\}##
    then the least upper bound of ##B_2## would be ##\{2\}##, but it is obviously not the greatest since it is not 'greater' than all the elements of ##B_2##

    I've tried a few different scenarios as well, trying to find sub-proofs that would lead me to the conclusion that ##x_1 R x_2## but I seem to be stuck. If anyone can point me in the right direction or shed some light it would be much appreciated.
     
  6. Oct 15, 2014 #5

    RUber

    User Avatar
    Homework Helper

    Let m be an element in B1, and n be an element in B2. m and n are both in A.
    x1 is the least upper bound for B1, so for all m, mRx1.
    Similarly x2 is the least upper bound for B2, so for all n, nRx2.
    If B1 is a subset of B2, then all m R x2.
    So all m R x1 and all m R x2.
    Case 1:
    If there is an n such that x1Rn in B2, (transitivity).
    Case 2:
    If there is no n such that x1 R n in B2, (least upper bound).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Ordered relations, lower upper bounds of a set
  1. Upper and lower bounds (Replies: 0)

  2. Upper/Lower Bounds (Replies: 8)

  3. Upper and Lower Bounds (Replies: 4)

Loading...