Let $X= \left \{ a,b,c,d \right \}$ and $R=\left \{ (a,a),(a,b),(b,a),((b,b),(c,c),(c,d),(d,c),(d,d) \right \}$. I want to show that $R$ is an equivalence relation on $X$.

My work:

$R$ is reflexive: If $a\in X$, $aRa$ since $(a,a) \in R$.

$R$ is symmetric: If $a,b \in X$, then $(a,b) \in R \Leftrightarrow (b,a) \in R$.

$R$ is not transitive: If $a,b,c \in X$, then $aRb$ and $bRc$ implies $aRc$. But $(b,c)$ is not an element of $R$ and $(a,c)$ is not an element of $R$.

So $R$ is not an equivalence relation. But I am supposed to show that $R$ is an equivalence relation on $X$. For transitivity should $a\neq b\neq c$?

  • 1
    $\begingroup$ You should use different variable names for the properties of an equivalence relation and the elements of the set $X$. $\endgroup$ – augurar Aug 9 '14 at 8:06
  • $\begingroup$ Your argument that $R$ is not transitive is incorrect. $\endgroup$ – alex.jordan Aug 9 '14 at 8:13
  • 1
    $\begingroup$ When you write "If $a,b,c\in X...$" those three things are not literally the $a,b,c$ in your first declaration of what $X$ is. It would be less confusing to use "If $x,y,z\in X...$". Next, $aRc$ would have to be true if both $aRb$ and $bRc$ were true. But if say $bRc$ is false, there is no evidence against transitivity to glean here. $\endgroup$ – alex.jordan Aug 9 '14 at 8:17

Please note that $R$ is transitive if $(x,y) \in R$ and $(y,z) \in R \Rightarrow (x,z) \in R$

Now as $(a,b) \in R$ and $(b,c) \notin R$ you need not check for $(a,c)$ for this pair.

So whenever you find any pair of elements $(x,y)$ and $(y,z)$ both belonging to $R$ then only you check whether $(x,z)$ is in $R$ or not.

| cite | improve this answer | |
  • $\begingroup$ So what pair of elements work? I am struggling to find it. Also should $x\neq y\neq z$ for transitivity? $\endgroup$ – OGC Aug 9 '14 at 8:42
  • $\begingroup$ Try to understand the definition of transitive relation. If you find that (x,y) and (y,z) both are in R then (a,c) must be in R if R is transitive.In your case see for example (a,a) and (a,b) are both in R and also (a,b) in R.If you still not getting it just observe by taking x=a,y=a,z=b.Now you check that whenever elements of the form (x,y) and (y,z) both in R then (x,z) are also in R. $\endgroup$ – usermath Aug 9 '14 at 8:49
  • $\begingroup$ If $x=y=z \in X$, then I get transitivity because $(a,b) \in R$ and $(b,b) \in R$ implies $(a,b) \in R$. $\endgroup$ – OGC Aug 9 '14 at 8:49
  • $\begingroup$ I understand now. I thought that $x$,$y$, and $z$ cannot be equal to one another for transitivity. $\endgroup$ – OGC Aug 9 '14 at 8:51
  • $\begingroup$ Glad to help you.. $\endgroup$ – usermath Aug 9 '14 at 8:53

It doesn't matter whether (b,c) $\in$ R or not. Had it been the case that (a,b) $\in$ R and (b,c) $\in$ R, but (a,c) $\notin$ R, then I would conclude that R is not transitive. In this case, (b,c) $\notin$ R, so I dont worry. The relation is, by default transitive. You have done for reflexive and symmetric. So it is an equivalence relation.

| cite | improve this answer | |

for a relation to be an equivalence relation it must be reflexive, symmetric and transitive.

$R$ is reflexive if $ \forall x (x,x) \in R $ and $(a,a),(b,b),(c,c),(d,d) \in R$ so it is refexive

$R$ is symmetric if $ \forall x y \left( (x,y) \in R \to(y,x) \in R \right) $test this yourself.

$R$ is transitive if $ \forall x yz \left( \left((x,y) \in R \land (y,z) \in R \to (x,z) \in R \right) \right) $ test this also yourself

If your set pases all these tests it is an equivalence relation

Good luck

| cite | improve this answer | |
  • $\begingroup$ $(d,a)\not\in R$. $\endgroup$ – jgon May 11 '15 at 4:33

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.