RoS is a equivalence relation iff RoS = SoR

1.6k Views Asked by At

Let R and S be two equivalence relation on X.

I wanna prove that $R\circ S$ is an equivalence relation, but I can't prove that it is reflexive and transitive.

For transitivity:

There are arbitrary $x$ and $y$ with $(x,y)\in R\circ S \iff$ there is $z$ with $(x,z)\in R$ and $(z,y)\in S$ ...?

And where I have to use the $R\circ S=S\circ R$?

1

There are 1 best solutions below

1
On

I use the notation $xRy$ instead of $(x,y)\in R$. In particular, $xRSy$ means $xRaSy$ for some $a$. It is also convenient to write $xRySz$ instead of ($xRy$ and $yRz$). In general I would advise you do draw such relations as graphs, with vertices representing points, and edges denoting the relationship.

Assumption $R\circ S=S\circ R$.

Transitivity: Suppose $xRSy$ and $yRSz$, i.e. $xRaSy$ and $yRbSz$ for some $a,b$. Then $aSyRb$, or short, $aSRb$. Since $SR=RS$, we get $aRSb$, let's say $aRcSb$ for some $c$. But then $xRaRcSbSz$, and since $R,S$ are equivalence relations, $xRcSz$, so $xRSz$.

I am confident that you can now prove reflexivity by yourself.

Assumption $R\circ S$ is an equivalence relation.

This direction is very similar to the proof above, you should give it a try.