1

I know this has been asked before, but the answer provided contradicted what I've been taught. I've been taught that it is possible for a relation to be acyclic and complete without being transitive. Is there a simple counter example that I am missing? I've included the definitions provided to me below.

acyclic: $\forall x_1, x_2,...,x_n \in X, x_1Px_2, x_2Px_3... x_{n-1}Px_{n}$ implies $x_1Rx_n$

complete: $\forall x,y \in X, $ either $xRy$ or $yRx$

It appears to me that being acyclic directly implies transitivity once we assume completeness, as we can arbitrarily reduce the size of $X$ to show that $x_1Rx_{n-1}, x_1Rx_{n-2}... x_1Rx_{3}, x_1Rx_2.$

Any help explaining where my thinking is wrong is greatly appreciated.

Corran Horn
  • 61
  • Actually this (broken) definition of "acyclic" implies that the relation can never relate two different elements (take $n=2$) -- so every relation that satisfies it is automatically transitive too. – hmakholm left over Monica Sep 03 '18 at 22:07

1 Answers1

1

I'm slightly confused by your notation since you seem to sometimes use $P$ as your relation and sometimes $R$. Assuming that these mean the same thing, then I think the definition of acyclic you are using is slightly non-standard and wonder if there's a typo involved or a misreading. Acyclic normally for a relation means that the final implication should be that $x_n R x_1$ is false, not that it is true. The point of being called "acyclic" is that this means there are no cycles of following the relationship back to where you started.

JoshuaZ
  • 1,752