# Discrete Math - Equivalence Classes

I'm trying to understand a problem that my textbook gives me. Here is the problem:

The relation $R$ is an equivalence relation on the set $A$. Find the distinct equivalence classes of $R$.

$A = \{0, 1, 2, 3, 4\}$

$R = \{(0,0), (0,4), (1,1), (1,3), (2,2), (3,1), (3,3), (4,0), (4,4)\}$

Here is the solution:

$[0] = \{x \in A | x\;R\;0 \} = \{0, 4\}$

$[1] = \{x \in A | x\;R\;1 \} = \{1, 3\}$

$[2] = \{x \in A | x\;R\;2 \} = \{2\}$

$[3] = \{x \in A | x\;R\;3 \} = \{1, 3\}$

$[4] = \{x \in A | x\;R\;4 \} = \{0, 4\}$

Note that $[0]=[4]$ and $[1]=[3]$. Thus the distinct equivalence classes of the relation are $\{0,4\}$, $\{1,3\}$, and $\{2\}$.

My problem here is that I am not understanding the solution. I do not understand how it came up with an answer for each equivalence class of every element $A$. As in, how is $\{0,4\}$ equal to $\{x \in A | x\;R\;0 \}$, and how is that equal to $[0]$? I can understand that $[0]=[4]$ since they both equal $\{0,4\}$ but I'm not sure how to arrive at that answer.

I'm trying this problem:

$A = \{a, b, c, d\}$

$R = \{(a,a), (b,b), (b,d), (c,c), (d,b), (d,d)\}$

However, I am lost because I do not understand how to arrive at answers for every element in $A$.

Any help explaining this to me would be much appreciated!

• If I understood this correctly, is the answer to the second problem {a}, {b,d} and {c}? – Sameer Anand Dec 2 '13 at 23:53
• Yes, it is: $[a]=\{a\}$, $[b]=[d]=\{b,d\}$, and $[c]=\{c\}$. – Brian M. Scott Dec 2 '13 at 23:55

for the first problem $0 \sim 4 ,1 \sim 3, 2 \sim 2$ so you have 3 equivalence classes (note that R is an equivalence realation) . for the second one $a \sim a , b \sim d , c\sim c$.

Firstly, you have to understand the definition of an equivalence relation. A relation is an equivalence relation if the following conditions are satisfied:

1. $\forall x\in A, \quad x\sim x,$
2. $\forall x,y\in A, \quad x\sim y\implies y\sim x,$
3. $\forall x,y,z\in A, \quad x\sim y, y\sim z \implies x\sim z$.

So given the information above (your example, I'll leave the exercise to you), since we have $(0,0),(0,4),(4,4)\in R$, we can conclude that $0\sim0\sim4\sim4$, hence $[0]=[4]=\{0,4\}$.