# Prove that if relation $SR$ is symmetric, then $SR = RS$.

Let $$R$$ and $$S$$ be equivalence relations on set $$A$$.
Prove that if relation $$SR$$ is symmetric, then $$SR = RS$$.

$$R$$ and $$S$$ are equivalence relations on set $$A$$, so $$R\subseteq A\times A$$ and $$S\subseteq A\times A$$. In order to be equivalence relations, they need to meet these three conditions:

• be reflexive: $$a\in A : aRa$$ (analogically for $$S$$)
• be symmetric: $$a,b\in A : aRb \rightarrow bRa$$
• be transitive: $$a,b,c\in A : (aRb \wedge bRc)\rightarrow aRc$$

I do not really know where to start, I was thinking about it the following way:

Composition of relations $$S$$ and $$R$$ can be written as $$SR\subseteq A\times A$$, as both relations are on set $$A$$. If relations $$S$$ and $$R$$ are equivalence relations, then their composition should also be an equivalence relation.

but I am not sure whether it is correct and I also get stuck there. It is kind of problematic, as I need a formal proof to it.

• My gut instinct would be to use the definition of relation composition, suppose we have $(x,y) \in SR$, and then work through the definition and use symmetry to show $(x,y) \in RS$ (or, equivalently, $(y,x)$ - not sure which would be more convenient). That would imply the equivalence of the two relations since it would show all elements of $SR$ are shared by $RS$. – Eevee Trainer Dec 13 '18 at 6:08
• How are you defining $SR$? What order of composition? – Andrew Li Dec 13 '18 at 6:21
• If $P\subseteq A\times B$ and $Q\subseteq B\times C$, then $PQ\subseteq A\times C$. – whiskeyo Dec 13 '18 at 6:35

## 1 Answer

If $$SR$$ is symmetric then $$xSRy\iff ySRx$$.

We have to show $$xSRy\iff xRSy$$.

So it suffices to show $$xRSy\iff ySRx$$. So we need to show:

$$\exists z(xRzSy)\iff\exists z(ySzRx)$$.

But both of $$R$$ and $$S$$ are symmetric, so we can use the same $$z$$ in both cases. $$\Box$$