Relation $R$: $R\circ R \subseteq R \implies R$ is transitive

Question

Let $R$ be a relation on $X$, a set. If $R\circ R\subseteq R$, then is $R$ transitive?

Answer 1

Just apply the definitions. (This advice applies to most elementary problems of this general type.) In order to show that $R$ is transitive, you must show that if $x,y,z\in X$ and $\langle x,y\rangle,\langle y,z\rangle\in R$, then $\langle x,z\rangle\in R$. Since you know that $R\circ R\subseteq R$, you know that it would be enough to show that $\langle x,z\rangle\in R\circ R$: that would ensure that $\langle x,z\rangle\in R$ and hence that $R$ is transitive.

Now just use the definition of $R\circ R$ to show that if $\langle x,y\rangle,\langle y,z\rangle\in R$, then $\langle x,z\rangle$ is in $R\circ R$.

Added: The composition $R\circ R$ is the relation on $X$ defined as follows:

$$R\circ R=\left\{\langle x,y\rangle\in X\times X:\exists z\in X\Big(\langle x,z\rangle\in R\text{ and }\langle z,y\rangle\in R\Big)\right\}\;.$$

Informally, you can think of $R$ as a list of the ‘steps’ you can take in $X$: $\langle x,y\rangle\in R$ means that it’s possible to step from $x$ to $y$. In these informal terms, $\langle x,y\rangle\in R\circ R$ means that you can get from $x$ to $y$ in two steps: there’s at least one intermediate ‘stepping-stone’ $z$ in $X$ such that you can step from $x$ to $z$ and then from $z$ to $y$.