# Is $R=\left \{ (a,a),(a,b),(b,a),(b,b),(c,c),(c,d),(d,c),(d,d) \right \}$ an equivalence relation on $X$?

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$?

• You should use different variable names for the properties of an equivalence relation and the elements of the set $X$. – augurar Aug 9 '14 at 8:06
• Your argument that $R$ is not transitive is incorrect. – alex.jordan Aug 9 '14 at 8:13
• 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. – 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.

• So what pair of elements work? I am struggling to find it. Also should $x\neq y\neq z$ for transitivity? – OGC Aug 9 '14 at 8:42
• 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. – usermath Aug 9 '14 at 8:49
• 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$. – OGC Aug 9 '14 at 8:49
• I understand now. I thought that $x$,$y$, and $z$ cannot be equal to one another for transitivity. – OGC Aug 9 '14 at 8:51

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.

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

• $(d,a)\not\in R$. – jgon May 11 '15 at 4:33