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!

  • $\begingroup$ If I understood this correctly, is the answer to the second problem {a}, {b,d} and {c}? $\endgroup$ – Sameer Anand Dec 2 '13 at 23:53
  • $\begingroup$ Yes, it is: $[a]=\{a\}$, $[b]=[d]=\{b,d\}$, and $[c]=\{c\}$. $\endgroup$ – 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\}$.

Leave a comment if you are still uncertain.

  • $\begingroup$ You didn't prove symmetric, i.e. (4,0) in R. $\endgroup$ – Jossie Calderon Feb 20 at 1:14

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.