Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
2  
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
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.