1
$\begingroup$

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?
I saw the answer(odd numbered problems have answers) is {<1,2>,<2,1>,<1,1>,<2,2>,<3,3>}.
However, I don't understand why <3,3> is included in the relation.

  • 0
    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$.2012-04-06

1 Answers 1

1

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$.