[Math] Proof that composition of equivalence relations R and S is transitive if and only if R∘S=S∘R

discrete mathematicselementary-set-theorylogicrelations

Proof that composition of equivalence relations $R$ and $S$ is transitive if and only if $R$∘$S$ = $S$∘$R$.

I'm trying to understand how it could be proved: as I know composition of transitive is transitive, but I have no idea what should be done next.

Best Answer

We use the fact that for every reflexive binary relations $R, S$ on a set, $R \subseteq R \circ S$ and $R \subseteq S \circ R$, and that $R$ is transitive iff $R \circ R = R$.

$(\Rightarrow:)$ Let us suppose that $R \circ S$ is transitive and let $(a,c) \in R \circ S$.
Then, for some $b$, we have $(a,b) \in R$ and $(b,c) \in S$.
Since the relations are symmetric, $(c,b) \in S$ and $(b,a) \in R$, from which it follows by an earlier remark that $(c,b) \in R \circ S$ and $(b,a) \in R \circ S$.
Now, by hypothesis, it follows that $(c,a) \in R \circ S$, whence $(a,c) \in S \circ R$.
We conclude that $R \circ S \subseteq S \circ R$.

The reverse inclusion follows from $S \circ R \subseteq R \circ S \circ R \circ S = R \circ S$, by hypothesis.
So $R \circ S = S \circ R$.

$(\Leftarrow:)$ Suppose $(a,b), (b,c) \in R \circ S$.
Then, there exist $u,v$ such that $$a R u S b \quad \text{ and } \quad b R v S c.$$ From $b R v S c$ it follows that $(b,c) \in R \circ S = S \circ R$, and so $(b,c) \in S \circ R$.
Now, from $u S b (S \circ R) c$ it follows that $(u,c) \in S \circ R$, and from $a R u (S \circ R)c$, it follows that $(a,c) \in R \circ (S \circ R) = R \circ (R \circ S) = R \circ S$, and so $R \circ S$ is transitive.

Related Question