Thread: 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

Would also work?
Why or why not?

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!

But . Is it?
Antisymmetric says that in both then it must be true that .

There is something that I am obviously not understanding. (2,1) does not belong to the set you listed.

I believe the set is antisymmetric, since for it not to be antisymmetric we would have to have: 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.

Originally Posted by gate13

I believe the set is antisymmetric, since for it not to be antisymmetric we would have to have: 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?

I believe the other partial order would be :

{(1,1), (2,1), (2,2)} for the same reasons listed previously.

I just wanted to thank you Plato for your time and explanations. Many thanks.