Take the 2-minute tour ×
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.

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|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
    
Welcome to math.SE: since you are fairly new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are so far; this will prevent people from telling you things you already know, and help them write their answers at an appropriate level. If this is homework, please add the [homework] tag; people will still help, so don't worry. Also, many find the use of imperative ("Find", "Show") to be rude when asking for help; please consider rewriting your post. –  Arturo Magidin 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
    
Hi @Matt. You can upvote and/or accept helpful answers. See here how to do it: meta.math.stackexchange.com/questions/3286/… I thought the answer below was quite helpful so I upvoted it. –  Matt N. Apr 6 '12 at 15:05
    
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
show 1 more comment

1 Answer

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|improve this answer
add comment

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.