2
$\begingroup$

So I have the question:

Prove that any directed cycle in the graph of a partial order must only involve one node.

So I know that a partial order must be transitive, antisymmetric, and reflective, but from there I am pretty lost. I also know that any path of one or more edges from a node to itself is a directed cycle, but from there I am having trouble connecting everything.

I kind of need help as to where to start thinking, and the first step as to how to answer this question.

$\endgroup$
  • 2
    $\begingroup$ Follows directly from transitivity and antisymmetry, doesn't it? $\endgroup$ – G. Bach Oct 24 '13 at 2:09
2
$\begingroup$

I'm assuming your partial orders are of the type "$a \leq b$" rather than of the type "$a < b$", though the proof is very similar to both cases. Each edge $a \to b$ in the graph corresponds to an inequality $a \leq b$. Now suppose you had a triangle $a \to b \to c \to a$. Such a triangle would imply $$a \leq b \leq c \leq a, $$ which has some implications since $\leq$ is a partial order. The case of longer (or shorter) cycles is similar.

$\endgroup$
1
$\begingroup$
  • A cycle is a strongly connected component (there is a path from every node to every other node).
  • In a partial order, all nodes in a strongly connected component are all equally related; because there is a path from every node to every node: due to the transitive property, this means that $a \le b \wedge b \le a$ for all $a,b$ in the strongly connected component.

Spoiler (mouseover):

This can contradict the antisymmetric property. "More formally, R is antisymmetric precisely if for all a and b in X: if R(a,b) and R(b,a), then a = b, or, equivalently, if R(a,b) with a ≠ b, then R(b,a) must not hold." - wikipedia. It requires that: iif two nodes are equally related to eachother, that they are the same node. Thus, if a cycle contains more than one node, there are two nodes that are equally related ($a\le b, b\le a$), yet not the same ($a \ne b$). If the cycle is one node, then it is equal to itself and the same and thus the antisymmetric property holds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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