Results 1 to 10 of 10

Math Help - Proof of a problem concerning least upper bounds

  1. #1
    Newbie
    Joined
    Aug 2011
    Posts
    18

    Proof of a problem concerning least upper bounds

    The exercise:

    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 (x1,x2) ∈ R.

    (looking for an informal proof here)

    My attempt at solving:

    I have been finding this problem somewhat difficult. After assuming B1 ⊆ B2, I have been trying to construct a proof by cases- however, I am not even certain that this is the best way to proceed. The cases I have attempted are x1 ∈ B2 or x1 ∉ B2, but i haven't found a way to complete the proof this way, and so i am beginning to doubt this proof strategy (by cases). As such, I have also attempted a proof by contradiction, but this doesn't seem to make it too far either.

    My main questions are:

    1) If this IS a proof that should proceed via cases, are there any suggestions as to which cases should be used?
    2) If this is not a proof by cases, what method of proof should be used, and in what ways does the problem suggest this?

    I have been practicing proofs in set theory for about a year and am now reviewing for a credit by examination test I will be taking this semester by performing some of the problems which occur later in the problem sets in Velleman's text on proofs/set thoery. If you have any insight, I would also like to ask your opinion as to the degree of difficulty you believe this problem is (I'm interested in assessing my mastery of the subject). The proofs which appear in the examples within the text and earlier within problem sets I can easily achieve, but the later ones usually leave me thinking for many hours, and sometimes even a day or two (oftentimes without much progress toward the solution).

    Any help is appreciated
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,642
    Thanks
    1594
    Awards
    1

    Re: Proof of a problem concerning least upper bounds

    Quote Originally Posted by Syrus View Post
    [B]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 (x1,x2) ∈ R.
    This is a language proof.
    You know that B_1\subseteq B_2.
    Does that mean that x_2 is an upper bound for B_1~?
    What does it mean for x_1 to be the least upper bound of B_1~?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2011
    Posts
    18

    Re: Proof of a problem concerning least upper bounds

    Well, for x1 to be the least upper bound of B1, this means (∀b1 ∈ B1)((b1,x1) ∈ R) and (∀z ∈ A)([(∀b1 ∈ B1)((b1,z) ∈ R)] --> (x1,z) ∈ R.)

    This is along the right lines?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,642
    Thanks
    1594
    Awards
    1

    Re: Proof of a problem concerning least upper bounds

    As a general matter, if \alpha=\text{LUB}(S) and \beta is also an upper bound of S then \alpha\preceq\beta~.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2011
    Posts
    18

    Re: Proof of a problem concerning least upper bounds

    I guess my intuitive understanding of this exercise used your comment above. I guess I'm just a bit confused as to formalizing that x2 is also an upper bound of B1.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,642
    Thanks
    1594
    Awards
    1

    Re: Proof of a problem concerning least upper bounds

    Quote Originally Posted by Syrus View Post
    I guess my intuitive understanding of this exercise used your comment above. I guess I'm just a bit confused as to formalizing that x2 is also an upper bound of B1.
    You given that B_1\subseteq B_2 so any upper bound of B_2 is also an upper bound of B_1.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Aug 2011
    Posts
    18

    Re: Proof of a problem concerning least upper bounds

    Aha! Perhaps:

    Complete Proof of Original post:

    Lemma: 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, x2 is an upper bound of B1.

    Proof: Assume B1 ⊆ B2. Let b1 ∈ B1. Then b1 ∈ B2. Thus, (b1, x2) ∈ R, so x2 is an upper bound of B1 (since b1 was arbitrary).

    Q.E.D.

    __________________________________________________ ________________________________

    Problem: 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, (x1, x2) ∈ R.

    Proof: By the lemma above, we know x2 is an upper bound of B1. But since x1 is the least upper bound of B1, it follows that (x1, x2) ∈ R.

    Q.E.D.

    Big thanks to Plato
    Last edited by Syrus; August 22nd 2011 at 09:15 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Aug 2011
    Posts
    18

    Re: Proof of a problem concerning least upper bounds

    I hope?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,642
    Thanks
    1594
    Awards
    1

    Re: Proof of a problem concerning least upper bounds

    Quote Originally Posted by Syrus View Post
    I hope?
    You are making too much of this.
    Did you read reply #4? That is the meaning of least upper bound.
    In this problem we are given three facts to work with.
    b_1=\text{LUB}(B_1),~b_2=\text{LUB}(B_2),~\&~B_1 \subseteq B_2.
    The last condition means that b_2 is also an upper bound for B_1.
    By the definition of least upper bound that means that b_1\preceq b_2.
    At that point the proof is done.

    But, from the given it could be that b_1=b_2
    Also it could be that b_1\notin B_2.
    That does not change that proof in any way.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Aug 2011
    Posts
    18

    Re: Proof of a problem concerning least upper bounds

    Yes, i understand what you're saying Plato. The text this exercise appears in, however, is rather elementary and prefers (I would guess, since it contains itself such) more introductory/ technical proofs like the one I have attempted (eg. working with the logical forms of the statements and writing out many of the particular details of the derivation).

    Your expertise with the subject is most likely leagues ahead of this, though, which may explain why you're scratching your head as to why I'm making a meal out of this.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Least Upper Bounds
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 3rd 2010, 06:15 PM
  2. Upper bounds
    Posted in the Calculus Forum
    Replies: 3
    Last Post: July 31st 2009, 06:10 AM
  3. least upper bounds!
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 10th 2008, 12:41 PM
  4. Greatest lower bounds and least upper bounds
    Posted in the Calculus Forum
    Replies: 3
    Last Post: March 31st 2008, 06:31 PM
  5. more help upper bounds
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 14th 2006, 08:00 PM

Search Tags


/mathhelpforum @mathhelpforum