0

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?

Bhavook
  • 1
  • 3

1 Answers1

2

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

Berci
  • 90,745
  • So the answer must be no. Since by completeness and absence of transitivity, we get a cycle. – Bhavook Jan 31 '20 at 12:34
  • If $R$ is complete and acyclic, then $R$ must be transitive (else $R$ wouldn't be acyclic). – Berci Jan 31 '20 at 14:10