-2
$\begingroup$

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?

  • 1
    What are you actually trying to do?2012-12-09
  • 0
    Finding the smallest partial order for S={(1,5) (2,3) (2,4) (3,3) (4,3) (5,1)}2012-12-09
  • 0
    What on earth does that mean?2012-12-09
  • 0
    If 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
  • 0
    it defines a relation matrix2012-12-09
  • 0
    @Chris: I suspect that xeonphi wants to find the reflexive, transitive closure of $S$.2012-12-09
  • 0
    I 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
  • 0
    Xeonphi, 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
  • 0
    My 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 1

2

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

some partial order

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