1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Eevee Trainer Dec 13 '18 at 6:08
  • $\begingroup$ How are you defining $SR$? What order of composition? $\endgroup$ – Andrew Li Dec 13 '18 at 6:21
  • $\begingroup$ If $P\subseteq A\times B$ and $Q\subseteq B\times C$, then $PQ\subseteq A\times C$. $\endgroup$ – whiskeyo Dec 13 '18 at 6:35
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.