Partial orders - Question

Printable View

• Mar 11th 2010, 01:38 PM
gate13
Partial orders - Question
Good day to all,

We have just started relations and I came across the following question in my textbook:

Let X = {1, 2}. List all the partial orders that can be defined on X.

My solution:

I began by computing X x X (Cartesian product) which gave me:

X x X ={(1,1), (1,2), (2,1), (2,2)}

Since we are looking for partial orders, the relation has to be simultaneously reflexive, antisymmetric and transitive.

If the relation R on X is reflexive then it must contain (1,1) and (2,2)

The ordered pairs (1,2) and (2,1) cannot belong to R for if they did and R is also antisymmetric then that would imply 1=2, which is false.

Therefore I concluded that the list of partial orders is the set:
{(1,1), (2,2)}

I was wondering if my logic is flawed and if so what errors have I committed?

Finally, is it possible in this problem to determine the number of partial orders (cardinality)?

Any advice would be greatly appreciated.

Kindest regards
• Mar 11th 2010, 01:44 PM
Plato
Would $\{(1,1),(1,2),(2,2)\}$ also work?
Why or why not?
• Mar 11th 2010, 01:58 PM
gate13
Thank you Plato for your quick response.

I am not sure. The definition of antisymmetric states:

for every a,b in X ((a,b) belongs to R and (b,a) belongs to R implies a=b)

If (1,2) belongs to R and (2,1) does not belong to R (based on the set you listed) then the hypothesis of the implication is false which means that the implication is true. If this is a valid reasoning could we not say the same for the set: {(1,1), (2,1), (2,2)}

Slightly confused!
• Mar 11th 2010, 02:06 PM
Plato
But $(2,1)\notin\{(1,1),(1,2),(2,2)\}$. Is it?
Antisymmetric says that in both $(a,b)\in R~\&~(b,a)\in R$ then it must be true that $a=b$.
• Mar 11th 2010, 02:35 PM
gate13
There is something that I am obviously not understanding. (2,1) does not belong to the set you listed.

I believe the set http://www.mathhelpforum.com/math-he...26e4344e-1.gif is antisymmetric, since for it not to be antisymmetric we would have to have: http://www.mathhelpforum.com/math-he...0853db63-1.gif and a different than b. Therefore the set you provided is a partial order as well (reflexive, transitive and antisymmetric).

I apologize as I realize this may be obvious to many.
• Mar 11th 2010, 02:38 PM
Plato
Quote:

Originally Posted by gate13
I believe the set http://www.mathhelpforum.com/math-he...26e4344e-1.gif is antisymmetric, since for it not to be antisymmetric we would have to have: http://www.mathhelpforum.com/math-he...0853db63-1.gif and a different than b. Therefore the set you provided is a partial order as well (reflexive, transitive and antisymmetric).

That is correct. And there is one more p.o. on the set.
What is it?
• Mar 11th 2010, 02:43 PM
gate13
I believe the other partial order would be :

{(1,1), (2,1), (2,2)} for the same reasons listed previously.
• Mar 11th 2010, 03:01 PM
gate13
I just wanted to thank you Plato for your time and explanations. Many thanks.