Can a relation be acyclic and complete but not transitive?

1.1k Views Asked by At

I have come to understand that transitivity is a stronger condition than acyclicity, and completeness and quasitransitivity together imply acyclicity. But is it true that acyclicity and completeness imply transitivity?

1

There are 1 best solutions below

2
On

Yes, it's true: $\def\R{\mathop{\mathrm R}}$

Let $\R\subseteq A\times A$ be an acyclic and complete relation.
Suppose $a\R b$ and $b\R c$. If we don't have $a\R c$, then by completeness, $c\R a$ follows, but then this produces a cycle $a\R b\R c\R a$.