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?
Best Answer
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.