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)

  • $\begingroup$ 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). $\endgroup$ – 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.$

  • $\begingroup$ 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. $\endgroup$ – TechJ Nov 2 '15 at 12:11
  • $\begingroup$ Thanks for making it too clear. $\endgroup$ – TechJ Nov 2 '15 at 13:06

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.