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?
 A: 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$.
A: 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.
A: It is really interesting the following case:
When $R \subseteq A\times A$ is transitive, $R \circ R \subseteq R$.
Proof.
Let $(a, c) \in R \circ R$, by definition, $\exists b \in A$ s.t. $(a, b) \in R$ and $(b, c) \in R$ which implies, due to the transitive of $R$, that $(a, c) \in R$.
When $R \subseteq A\times A$ is reflexive, $R \subseteq R \circ R$.
Proof.
Let $(a, b) \in R$, since $R$ is reflexive, $(a, a) \in R$. So it $\exists a \in A$, due to reflexive property of $R$, such that $(a, a) \in R$ and $(a, b) \in R$, then $(a, b) \in R\circ R$.
So we can say that for $R \subseteq A\times A$, if $R$ is reflexive and transive then $R\circ R = R$.
Will the implication be given?
