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

elementary-set-theory

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.

Best 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$