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

How do I prove that the following:

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

• What is the definition of $\circ$ here? – Kenny Lau Sep 18 '17 at 6:06
• it's $\{(u,v) | \exists x uR^{-1}x \land xRv\}$. Where $xRu$ means $(x,y) \in R$ – Dole Sep 18 '17 at 6:09
• @KennyLau Also, I only have a problem with assuming the 2nd, and deriving the first, any tips on the proof technique? – Dole Sep 18 '17 at 6:13

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.