$R_1$ and $R_2$ are equivalence relations on $A$. Prove or disprove: $R_1 \circ R_2$ is also an equivalence relation.

I check on internet what mean the notation $\circ$. Is defined like that:

$$R \circ S = \left\{(x,z) \in A \times A \mid \exists y \in A: xRy \wedge ySz\right\}$$

For equivalence relation you need show that is reflexive, transitive, symmetric.

I think I find good example that this no work for transitive and symmetric.

Say $A = \left\{0,1,2\right\}$, we say $R_1=\left\{(0,0),(1,1),(2,2),(0,1),(1,0)\right\}$ and $R_2=\left\{(0,0),(1,1),(2,2),(1,2),(2,1)\right\}$.

Then $R_1 \circ R_2= \left\{(0,0),(1,1),(1,2),(2,2),(2,1),(0,1),(0,2),(1,0)\right\}$

This is no symmetric because $(0,2)$ exist but $(2,0)$ no exist.

This is no transitive because $(2,1)$ exist and $(1,0)$ exist, but $(2,0)$ don't exist.

Now only missing is reflexive. I don't know how show it because it must be reflexive. But how show it's reflexive? I show the other correct? Because I ask friend and he say when you find counter example you have proof good.

Pls help need for exam how solve these example.

  • $\begingroup$ sure about $R \circ S$ definition? Maybe $xSy \land yRz$? $\endgroup$ – Kirill Nov 17 '17 at 22:14
  • $\begingroup$ @Kirill Yes sure I also check from book I have from library :) $\endgroup$ – roblind Nov 17 '17 at 22:16
  • $\begingroup$ anyway, relations are subsets of a cartesian product of $A \times A$. So, they are sets. So - as usually - take an $(x,z) \in R \circ S$ and you use definitions. Or, argue by contradiction. $\endgroup$ – Kirill Nov 17 '17 at 22:17
  • $\begingroup$ for me it is wrong, as $R \circ S = SR$. You first compute $S$, then $R$. So, first $xSy$, then $yRz$. $\endgroup$ – Kirill Nov 17 '17 at 22:19
  • $\begingroup$ @Kirill I think it don't matter the order. Maybe other peoples can say about this because I'm not sure? But I take the definition from book and book is of professor $\endgroup$ – roblind Nov 17 '17 at 22:21

Your example is correct, and you don't need to do any more work! To show a relation is not an equivalence relation, you only need to show that one of the three conditions (reflexive, symmetric, transitive) fails. To be an equivalence relation, all three need to be true, as as soon as one of them fails, it's not an equivalence relation. So you have shown that $R_1\circ R_2$ is not an equivalence relation in your example.

(In fact, if $R_1$ and $R_2$ are reflexive, then $R_1\circ R_2$ always is reflexive as well. The proof is easy: for any $x\in A$, $(x,x)\in R_1$ and $(x,x)\in R_2$, so $(x,x)\in R_1\circ R_2$ (taking the $y$ in the definition of $R_1\circ R_2$ to be $x$).)

  • $\begingroup$ Oh yes I just read on internet one counterexample for one of the type of relation is enough for show it's no equivalence relation. But for interest can pls say how show this is reflexive? $\endgroup$ – roblind Nov 17 '17 at 22:16
  • $\begingroup$ Thank you very much I don't know it's even more easy then the other!!!! :) $\endgroup$ – roblind Nov 17 '17 at 22:20

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.