# Proving that a relation $R$ is transitive iff $R \circ R \subset R$.

Problem: Let $R$ be a relation over $X$, i.e. let $R = \left\{ (x,y) \in X \times X \mid x \in X \wedge y \in X \right\}$. Prove that $R$ is transitive if and only if $R \circ R \subset R$.

Attempt at proof: I proved one direction already. This is what I did: Suppose $R$ is transitive. Let $q \in R \circ R$ be arbitrary. Then $q = (x,y) \in X \times X$. By definition of composition there then exists a $z \in X$ such that $(x,z) \in R$ and $(z,y) \in R$. From transitivity it then follows that $(x,y) \in R$. Since $q$ was arbitrary, this proves that $R \circ R \subset R$.

Now, suppose that $R \circ R \subset R$. Let $(x,y) \in R$. Now, I don't know how to proceed since I don't know how to use my assumption this time. Any help?

• Note that $R = \left\{ (x,y) \in X \times X \mid x \in X \wedge y \in X \right\}$ means that $R$ is the full relation ($xRy$ holds for all $x,y$ ,or simply $R=X\times X$). I assume you wanted to say $R\subseteq X\times X$ instead. – Hagen von Eitzen Aug 6 '15 at 14:53

The second part should rather start "Now, suppose that $R\circ R\subseteq R$. Let $(x,y)\in R$ and $(y,z)\in R$." Then you want to show that $(x,z)\in R$.

• How do I do that? I don't know how to use $R \circ R \subset R$. – Kamil Aug 6 '15 at 15:22

Hagen was right; since the question is really of the form:

$$R\circ R \subset R \to \forall x\forall y\forall z ((x,y)\in R \land (y,z)\in R \to (x,z)\in R)$$

It is legitimate for you to assume $R\circ R \subset R$ and $(x,y)\in R \land (y,z)\in R$ (since you would need to do a universal proof of the RHS of the conditional).

$R\circ R$ really comes down to this, after having done a universal instantiation:

$$(x,z)\in A\times A|\exists y \in A (x,y)\in R \land (y,z)\in R$$

But note that the 'such that' is synonymous to IFF, i.e. if you can satisfy $\exists y \in A (x,y)\in R \land (y,z)\in R$ you get $(x,z)\in R \circ R$.

With $(x,y)\in R \land (y,z)\in R$ you can existential generalise it to $\exists y \in A (x,y)\in R \land (y,z)\in R$, and you should then be able to utilise the 1st assumption.

• This should be the answer. – Tsangares Dec 1 '17 at 22:46