# How do you find the smallest partial order? [closed]

The thing I find the most difficult is the transitive part. The only way that I know of is to see if the relation is transitive, but I have to do check if it is transitive for every relation possible on a given matrices. It gets quite cumbersome when you have a matrix of 5 elements or more. So is there some sort of shortcut?

-

## closed as not a real question by Chris Eagle, dtldarek, Henry T. Horton, tomasz, Cameron BuieDec 9 '12 at 3:40

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

What are you actually trying to do? – Chris Eagle Dec 9 '12 at 0:08
Finding the smallest partial order for S={(1,5) (2,3) (2,4) (3,3) (4,3) (5,1)} – xeonphi Dec 9 '12 at 0:09
What on earth does that mean? – Chris Eagle Dec 9 '12 at 0:10
If you are trying to find the smallest partial order containing some relation, look at closure operations. – dtldarek Dec 9 '12 at 0:11
it defines a relation matrix – xeonphi Dec 9 '12 at 0:11

Draw a picture. Make a dot for each of the elements. Whenever you know that $a\prec b$, draw an arrow from $b$ to $a$.

Except that if you know that $a\prec b$ and $b\prec c$, don't bother drawing an arrow for $a\prec c$, because you'll be able to see at a glance that $a\prec c$. Also don't bother to draw the arrow from $a$ to itself, because you'll know they are there anyway.

If you have $a\prec b$ and $b\prec a$ for some $a$ and $b$, this will be apparent, and to make the order into a partial order, you merge $a$ and $b$ into a single dot. Similarly any cycle of arrows $a\prec b\prec c\prec\cdots\prec a$ collapses down to a single point in a partial order.

Then look at the picture. Maximal and minimal elements will be obvious; elements that can't be compared will be obvious; relations implied by transitivity will be obvious.

After you absorb the picture, try drawing it again, and this time when $a\prec b$, instead of drawing an arrow from $b$ to $a$, just try drawing $b$ above $a$ on the paper. For example, here's when we have $a\prec 1, 0\prec c, b\prec 1, c\prec a, 0\prec b$:

Clearly 1 is maximal, 0 is minimal, and $b$ is not comparable with $a$ or $c$. Also it's obvious that $0\prec a$ by transitivity.

-
+1. Nice answer, and nice approach! – amWhy Dec 9 '12 at 1:54
@amWhy: I'm not sure it really helps the OP in this case, however. – MJD Dec 9 '12 at 1:57