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?
How do you find the smallest partial order?
-
1What are you actually trying to do? – 2012-12-09
-
0Finding the smallest partial order for S={(1,5) (2,3) (2,4) (3,3) (4,3) (5,1)} – 2012-12-09
-
0What on earth does that mean? – 2012-12-09
-
0If you are trying to find the smallest partial order containing some relation, look at [closure operations](http://en.wikipedia.org/wiki/Reflexive_transitive_closure). – 2012-12-09
-
0it defines a relation matrix – 2012-12-09
-
0@Chris: I suspect that xeonphi wants to find the reflexive, transitive closure of $S$. – 2012-12-09
-
0I know what to do, but I want a quick way of doing it. – 2012-12-09
-
0@xeonphi How do you define the smallest partial order for $S$? – 2012-12-09
-
0@dtldarek: No kidding! Clearly I’ve been answering too many questions about equivalence relations lately. Thanks. However, I note that there’s going to be a problem with antisymmetry ... – 2012-12-09
-
0@dtldarek: Start by telling us what "smallest partial order for S" means. Like I asked already. – 2012-12-09
-
0Xeonphi, are you sure that there **is** a partial order containing $S$? Note that $S$ contains both $(1,5)$ and $(5,1)$, but a partial order is antisymmetric. – 2012-12-09
-
0@ChrisEagle Yep, but you were misunderstood ("What on earth does $S = \{\ldots\}$ mean?") and your question has been answered ("It defines a relation matrix."). ;-) – 2012-12-09
-
0@dtldarek: that doesn't answer my question at all. The smallest partial order for S is a relation matrix. Ok, WHICH RELATION MATRIX IS IT? – 2012-12-09
-
0@Chris: I no longer have any clear idea of what your point is. Are you very indirectly noting that this $S$ cannot be extended to a partial order on $\{1,2,3,4,5\}$, or what? – 2012-12-09
-
0My point is that I have no idea what question is being asked. There seems to be an opinion developing that the question is "what's the smallest partial order extending $S$". But I can't find anything from the OP to support that, and I would rather find out what they actually want rather than guess wildly. – 2012-12-09
-
0@Chris: It may prove to be wrong, but it’s not a wild guess: the original question and the OP’s comment defining $S$ tend to support that interpretation. – 2012-12-09
1 Answers
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.
-
0@amWhy: I'm not sure it really helps the OP in this case, however. – 2012-12-09