Results 1 to 4 of 4

Math Help - Partial Orders

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    United Kingdom
    Posts
    28
    Thanks
    1

    Partial Orders

    OK, so I have managed to prove a couple of partial orders already so understand the reflexive, anti-symmetric and transistive properties to some degree but this question has really thrown me, especially for the latter two properties. Could someone please help me out. Thanks x

    Let
    X = {1,2,3} and let Y be the set X2 consisting of all pairs Y ={(x1, x2) : x1, x2 X}. So, e.g., Y consists of things like (3, 1), (1, 2), (3, 3).
    Define a relation on Y by (x1,x2)R(x1,x2) if and only if the followinghold: Either (x1 < x1) or (x1 = x1 and x2 x2). (Where < is the usual “lessthan” relation on the integers 1, 2, 3).
    Prove that this relation is a partial order on Y . Draw its Hasse diagram.Is this also a total order, or not?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Partial Orders

    Quote Originally Posted by carla1985 View Post
    OK, so I have managed to prove a couple of partial orders already so understand the reflexive, anti-symmetric and transistive properties to some degree but this question has really thrown me, especially for the latter two properties. Could someone please help me out. Thanks x

    Let
    X = {1,2,3} and let Y be the set X2 consisting of all pairs Y ={(x1, x2) : x1, x2 X}. So, e.g., Y consists of things like (3, 1), (1, 2), (3, 3).
    Define a relation on Y by (x1,x2)R(x1,x2) if and only if the followinghold: Either (x1 < x1) or (x1 = x1 and x2 x2). (Where < is the usual “lessthan” relation on the integers 1, 2, 3).
    Prove that this relation is a partial order on Y . Draw its Hasse diagram.Is this also a total order, or not?

    Here is a whole webpage on this subject.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,312
    Thanks
    693

    Re: Partial Orders

    this is also called "lexicographical ordering" (it's sort of like the way we alphabetize words in a dictionary).

    but we don't need to know that, we just need to prove it is a partial order.

    aRa, for all a in X:

    for a = (x1,x2), we certainly have x1 = x1, and x2 ≤ x2, so R is reflexive.

    suppose aRb and bRa:

    for a = (x1,x2) and b = (x1',x2'), aRb means either x1 < x1', in which case x1' < x1 could not possibly be true

    nor can be x1' = x1 be true (and thus we could not have bRa),

    or x1 = x1'. in this case, since aRb, we have x2 ≤ x2, and since bRa, we have x2' ≤ x2.

    since the normal ≤ IS anti-symmetric, this forces x2 = x2', so a = b, thus R is anti-symmetric.

    transitivity is a little trickier, because there are several cases. let's do the "easy one first":

    suppose aRb, and bRc with a = (x1,x2), b = (y1,y2) c = (z1,z2),

    where x1 < y1, and y1 < z1.

    then clearly x1 < z1, so aRc.

    however, it may be that x1 = y1, while y1 < z1. we still have x1 ≤ y1 < z1, so x1 < z1

    (because x1 is at most y1, which is smaller than z1). in this case, too aRc.

    it also may be that x1 < y1, but y1 = z1. again, this still means x1 < z1, so aRc.

    finally, it might be that x1 = y1 = z1. in this case we are forced to look at the second coordinate:

    aRb means x2 ≤ y2, and bRc means y2 ≤ z2. hence x2 ≤ z2, by the transitivity of ordinary ≤.

    so in all cases, if aRb, and bRc, aRc, so R is transitive.

    this is, surprisingly enough, a total order:

    (1,1) < (1,2) < (1,3) < (2,1) < (2,2) < (2,3) < (3,1) < (3,2) < (3,3), (here "<" means aRb, but a ≠ b). so its Hasse diagram is a line segment with one node per element of X:

    o---o---o---o---o---o---o---o---o
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2012
    From
    United Kingdom
    Posts
    28
    Thanks
    1

    Re: Partial Orders

    Thanks guys, thats fab. will have a read thru the webpage then re attack it
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Partial Orders
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 6th 2010, 09:33 AM
  2. Partial orders
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 6th 2010, 12:34 AM
  3. Partial Orders
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 15th 2009, 03:20 PM
  4. partial orders
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2009, 06:46 AM
  5. Partial orders
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: January 19th 2009, 10:58 AM

Search Tags


/mathhelpforum @mathhelpforum