Transitive vs Acyclic Relations

1.4k Views Asked by At

My question is that if a relation is transitive does it have to be acyclic? My first thought is yes, because if aRb, bRc, cRd then by transitivity aRc, bRd and applying transitivity once more implies aRd, thus R is acyclic because c cannot be related to a.

1

There are 1 best solutions below

0
On BEST ANSWER

Let's take the simplest relation you know : the equality relation ($x \mathcal{R} y \Leftrightarrow x = y$).

Obviously this relation is transitive and is not acyclic.

More generally, if your relation is an equivalence relation, it is then transitive and symetric, so it cannot be acyclic.