composition of an equivalence relation

Question

I am trying to prove that the composition R o R of an equivalence relation of R is also an equivalence relation.

I believe I have to prove that the composition of R o R is symmetric, reflexive and transitive.

But I am really stuck. It would be great if someone could help.

Answer 1

Let $Q$ be an arbitrary binary relation. Can you prove: 1/ if $Q$ is transitive then $Q \circ Q$ is transitive 2/ if $Q$ is reflexive then $Q \circ Q$ is reflexive 3/ if $Q$ is symmetric then $Q \circ Q$ is symmetric ?

Answer 2

We assume that $R$ is an equivalence relation on a set $S$. Let $x,y,z\in S$. To show reflexivity, we need to show that $x R\circ R x$ for all $x$. This is equivalent to saying that there exists some $x'$ such that $xRx'$ and $x'Rx$.

To show symmetry, we need to show that if $xR\circ R y$, then $yR\circ R x$. If $xR\circ Ry$, then there exists some $x'$ such that $xRx'$ and $x' R y$. To show $yR\circ Rx$, we need some $y'$ such that $yRy'$ and $y'Rx$.

To show transitivity, we need to show that if $xR\circ R y$ and $yR\circ Rz$, then $xR\circ R z$. This is equivalent to finding $z'$ such that $xRz'$ and $z'Rz$. If $xR\circ Ry$, then there exists $x'$ such that $xRx'$ and $x'Ry$. If $yR\circ Rz$, then there exists $y'$ such that $yRy'$ and $y'R z$.

Now just find $x', y'$, and $z'$ for each case. You can name them explicitly using elements mentioned in each case.