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!

Homework Help: How to Prove It, Sec. 4.4, #18a

  1. Oct 17, 2011 #1
    1. The problem statement, all variables and given/known data
    Suppose R is a partial order on A. B1[itex]\subseteq[/itex]A, B2[itex]\subseteq[/itex]A, and
    and [itex]\forall[/itex]x[itex]\in[/itex]B2[itex]\exists[/itex]y[itex]\in[/itex]B1(xRy).

    Prove that [itex]\forall[/itex]x[itex]\in[/itex]A, x is an upperbound of B1 if and only if
    x is an upperbound of B2.

    2. Relevant equations
    R is a partial order on A if R is reflexive, transitive and antisymmetric.

    Definition of an upper bound: Suppose R is a partial order on A, B[itex]\subseteq[/itex]A,
    and a [itex]\in[/itex]A. Then a is called an upper bound for B if [itex]\forall[/itex]x[itex]\in[/itex]B(xRa).

    3. The attempt at a solution
    Is this way off base?
    What if A = {(x,y)[itex]\in[/itex]Z X Zl Z are integers}
    R = {(x,y)[itex]\in[/itex]Z X Z l n[itex]\in[/itex]Z, y=2n, x=2n+1 and x≥y}
    B1 = {1, 3, 5, 6, 8} B2 = {0, 2, 4, 7, 9}
    A= {(1,0), (3,2), (5,4), (7,6), (9,8)}

    →Let x be an arbitrary upper bound of B1. Since B1[itex]\subseteq[/itex]A, then x[itex]\in[/itex]A. [itex]\forall[/itex]x[itex]\in[/itex]B1[itex]\exists[/itex]y[itex]\in[/itex]B2(xRy). Also,
    [itex]\forall[/itex]x[itex]\in[/itex]B2[itex]\exists[/itex]y[itex]\in[/itex]B1(xRy). Since
    R is the relation x ≥ y, then (xRy) means x is an upper bound of B2.

    [itex]\leftarrow[/itex]Let x be an arbitrary upper bound of B2. Similar reasoning (or lack thereof) to show reverse if, then statement.
  2. jcsd
  3. Oct 18, 2011 #2
    Proof. let x [itex]\in[/itex]A. Suppose x is an upperbound of B1. That means
    yRx for all y[itex]\in[/itex]B1. Let z[itex]\in[/itex]B2. By assumption this z[itex]\in[/itex]B2,
    [itex]\exists[/itex]w[itex]\in[/itex]B1 such that zRw. Since w[itex]\in[/itex]B1 and yRx for
    all y [itex]\in[/itex]B1, we know wRx. By transitive property, zRw and wRx implies zRx.

    [itex]\leftarrow[/itex]Similarly, suppose x is an upperbound of B2.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook