# If $R$ and $S$ are equivalence relations and transitive then does their compositions?

If $R$ and $S$ are endorelations then are the following statement true or false

(1) If $R$ and $S$ are transitive, then so is $R \circ S$

(2) If $R$ and $S$ are irrefexive, then so is $R \circ S$

(3) If $R$ and $S$ are equivalence relations, then so is $R \circ S$

I was able to conclude that (2) is false by giving a counter example. i.e. If $R=\{(0,1)\}$ and $S=\{(1,0)\}$ then $R \circ S=\{(0,0)\}$ which is reflexive. Hence (2) is false

Does anybody have same counter examples or proofs for the (1) and (3)

• So you use the convention that $R \circ S = \{(x,z) \in X^2: \exists y \in X: (x,y) \in R, (y,z) \in S\}$ (one often sees the reverse order by analogu to function composition). – Henno Brandsma Nov 2 '15 at 12:49

You can kill (1) and (3) with one blow by giving two equivalence relations whose composition is not transitive. Consider these equivalence relations $R$ and $S$ on the set $\{0,1,2\}$: $$R=\{(0,0),(1,1),(2,2),(0,1),(1,0)\}$$ $$S=\{(0,0),(1,1),(2,2),(1,2),(2,1)\}$$ In fact $R\circ S$ is neither transitive nor symmetric. This follows from the facts:
$(2,1)\in R\circ S\$ [since $(2,2)\in R$ and $(2,1)\in S$];
$(1,0)\in R\circ S\$ [since $(1,0)\in R$ and $(0,0)\in S$];
$(0,2)\in R\circ S\$ [since $(0,1)\in R$ and $(1,2)\in S$];
$(2,0)\notin R\circ S.$
• So the composition $R \circ S$ comes out as $\{(0,0),(1,1),(2,2),(0,2),(1,0)\}$ But here I can see that it is not symmetric as for $(0,2)$ there doesn't exist $(2,0)$. In the similar fashion all pairs of this set are obeying transitivity. So I am not getting exactly what was your answer. – TechJ Nov 2 '15 at 12:11