# Partial Order Relations and Total Order Relations

Question:
A={1,2,3}
1) How many partial order relations can be induced over A ?
2) How many total order relations can be induced over A ?
3) Does A exist a transitive relation?

I guess total order relations over A is P(3,3)=3!=6, but I don't know how to count partial order relations over A.

Any help will be greatly appreciated!

[UPDATE]
According to Scott's reply, I get the following result,
Type 1: 3!=6
Type 2: 3
Type 3: 3
Type 4: 3
Type 5: 3!=6

So there are 21(6+3+3+3+6) partial orders on A.
Is it right? I hope someone can check it.thanks.
[UPDATE2]
Thanks for Henry's help.

Type 4:6
Type 5:1
So there are 19(6+3+3+6+1) partial orders on A.
I am not sure I am right but I hope to get corrected.

3)Does A exist a transitive relation?
However, I don't understand why <3,3> is included in the relation.

-
Please show what you've tried so far so we can better help you. – Austin Mohr Apr 5 '12 at 16:00
You have types 1, 2 and 3 correctly counted but there are not three of type 4 (there are more), nor six of type 5 (there are fewer). – Henry Apr 6 '12 at 8:37
Your updated counts for types for types (4) and (5) are correct. In type (4) there are $3$ ways to choose the loner, and then $2$ ways to order the other two elements, for a total of $3\cdot 2=6$. In type (5) it doesn’t matter how you label the three elements, it’s still the same order: the only ordered pairs in it are $\langle 1,1\rangle,\langle 2,2\rangle$, and $\langle 3,3\rangle$. – Brian M. Scott Apr 6 '12 at 18:33
For your last question, probably $\langle 3,3\rangle$ was included just to ensure that every element of $A$ was in the domain of the relation. There are actually many transitive relations on $A$, because every partial order on $A$ is a transitive relation on $A$. – Brian M. Scott Apr 6 '12 at 18:36

Counting the partial order relations is a bit messy. Perhaps the most straightforward way is to organize them by their ‘shapes’. In the following diagrams the order is from bottom to top.

1. They can be linear:

 *
|
*
|
*

2. They have a minimum element but no maximum:

 *   *
\ /
*

3. They can have a maximum but no minimum:

   *
/ \
*   *

4. They can have two related elements and one unrelated element:

 *
|   *
*

5. They can have three unrelated elements:

 *   *   *


You’ve already counted the partial orders that are linear: there are indeed $3!=6$ of them. Now you just have to count the partial orders of types (2)-(5) above. To get you started, in type (2) any one of the three elements of $A$ can be the minimum element. Once you’ve chosen that, however, the partial order is completely determined:

    1   2                  2   1
\ /        and         \ /
3                      3


are the same partial order, just drawn differently. Thus, there are $3$ partial orders of type (2) on $A$.

-