# A transitive relation $R$ such that $R\circ R\neq R$?

Find an example of a set $A$ and a transitive relation $R$ on $A$ such that $R\circ R\neq R$.

$R\circ R$ is the relation such that $(a,c)\in R\circ R$ when $(a,b) \in R$ and $(b,c) \in R$. I know this, but I don't understand how that can not equal $R$.

-

To solve such questions it helps to construct small examples of transitive relations in the most obvious way. So, let $A=\{1,2,3\}$ and have $R\{(1,2),(2,3),(1,3)\}$. It is constructed by force to be transitive, but computing $R\circ R$ reveals a that $R\circ R\ne R$.

The moral is not so much any of the particularities of this solution, but rather the general strategy: construct small objects and check!

-

Hint:

• By transitivity you have $R \circ R \subseteq R$, but you do not have $R \subseteq R \circ R$.

• Your relation cannot be reflexive since it would imply $R \subseteq R \circ R$.

Good luck!

-

$R$ is transitive iff $R \circ R \subseteq R$. But the converse inclusion is not true. For example, take $(\mathbb{N},<)$. Then $1 < 2$, but there is no $n \in \mathbb{N}$ with $1 < n < 2$.

-

Hint: Try making the condition of transitivity degenerate; what if $A$ only had two elements?

-

For a real-world example, suppose $A$ is the set of all humans who have ever lived and that $a\:R\:b$ means "$a$ is an ancestor of $b$." Well, if $S:=R\circ R$, then $a\:S\:b$ means that "$a$ is an ancestor of one of $b$'s parents." In particular, then, if $a$ is a parent of $b$, then $a\:R\:b$, but it is not the case that $a\:S\:b$. It is true that $a\:R\:b$ whenever $a\:S\:b$, of course (by definition, since $R$ is transitive), so $R\circ R=S\subsetneq R.$

-