# R is symmetric and transitive relation, if and only if $R = R^{-1}\circ R$

How do I prove that the following:

Let $$R$$ be a (binary) relation on a set. Prove that $$R$$ is symmetric and transitive relation, if and only if $$R = R^{-1}\circ R$$.

Here, $$R^{-1} \circ R$$ is defined as the relation $$\{(u,v) | \exists x, uR^{-1}x \land xRv\}$$, where $$xRu$$ means $$\left(x,u\right) \in R$$.

I only have a problem with assuming the 2nd, and deriving the first, any tips on the proof technique?

Let $R = R^{-1} \circ R$.

Let $(a,b) \in R$. Since $(a,b) \in R^{-1} \circ R$, there is $c$ such that $(a,c) \in R^{-1}$ and $(c,b) \in R$.

So $(c,a) \in R$. Then, $(a,c) \in R^{-1}$, so $(a,a) \in R^{-1} \circ R = R$, so $(b,a) \in R^{-1} \circ R = R$.

So $R$ is symmetric.

Let $(a,b),(b,c) \in R$. By the above, $(b,a) \in R$, so $(a,b) \in R^{-1}$, so $(a,c) \in R^{-1} \circ R = R$

So $R$ is transitive.

Let $R$ be symmetric and transitive.

Then, let $(a,b) \in R$. Since $R$ is symmetric, $(b,a) \in R$, so $(a,b) \in R^{-1}$. Since $R$ is transitive, $(b,b) \in R$. Therefore, $(a,b) \in R^{-1} \circ R$.

Let $(a,b) \in R^{-1} \circ R$, and let $(a,c) \in R^{-1}$ and $(c,b) \in R$. So $(c,a) \in R$. Since $R$ is symmetric, $(a,c) \in R$. Since $R$ is transitive, $(a,b) \in R$.

Therefore, for all $(a,b)$, $(a,b) \in R \iff (a,b) \in R^{-1} \circ R$, so $R = R^{-1} \circ R$ by axiom of extensionality.