# Partial Orders

• Feb 12th 2013, 04:02 AM
carla1985
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?
• Feb 12th 2013, 04:27 AM
Plato
Re: Partial Orders
Quote:

Originally Posted by carla1985
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.
• Feb 12th 2013, 04:33 AM
Deveno
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
• Feb 12th 2013, 04:40 AM
carla1985
Re: Partial Orders
Thanks guys, thats fab. will have a read thru the webpage then re attack it :)