0

In another post entitled: "Proof that composition of equivalence relations $R$ and $S$ is transitive if and only if $R \circ S = S \circ R$" the following proof is given for the forward direction.

Assume $R\circ S$ is transitive. Let $(a,c) \in R \circ S$. Then, for some b , we have (a,b)∈R and (b,c)∈S . Since the relations are symmetric, (c,b)∈S and (b,a)∈R , from which it follows by an earlier remark that (c,b)∈R∘S and (b,a)∈R∘S . Now, by hypothesis, it follows that (c,a)∈R∘S , whence (a,c)∈S∘R ... .

I understand why $(c,a) \in R \circ S$. but why does this imply that $(a,c) \in S \circ R$.

Geoffrey Critzer
  • 1

1 Answers1

0

I'd actually do it this way: we easily have

$$SR \subseteq RSRS \subseteq RS$$ where the first inclusion follows from reflexivity of $R$ and $S$, and the second from transitivity that is assumed of $RS$. So $SR \subseteq RS$. Using symmetry of $R$ and $S$, rewrite this as $S^{op} R^{op} \subseteq R^{op}S^{op}$.

The main thing to check now is $S^{op} R^{op} = (RS)^{op}$ for any relations $R$, $S$ whatsoever. It then follows from the previous paragraph that $(RS)^{op} \subseteq (SR)^{op}$. From this, $RS \subseteq SR$ follows easily.

user43208
  • 8,289