[Math] the equivalence class of this equivalence relation

congruencesdiscrete mathematicselementary-set-theoryequivalence-relationslogic

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 26 pg 645].

Problem:
What is the equivalence class of this equivalence relation?
Relation {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 2), (3, 3)}
on the set {0, 1, 2, 3}.

This is my book's definition of an equivalence class of a.

enter image description here

And This is an example that the book used to demonstrate the concept of an equivalence class
enter image description here

The definition and example combination made sense to me. Finding the equivalence class of 0 of modulo 4 meant all the elements related to 0 of the set congruence modulo 4, meaning all elements that have property $\equiv$ 0 mod(4).
How would you apply the idea to a whole relation(set)? The definition implied that you can only have an equivalence class of an element, not a set.

Best Answer

André Nicolas is correct in the comments, but I would like to try to explain it a bit slower. As your definition says, the equivalence class of an element $a$ is all the elements that are related to $a$ through a given equivalence relation $R$.

So let's take your example. We have the set $X = \{0,1,2,3\}$ and the following equivalence relation on the set: $$R = \{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 1), (2, 0), (2, 2), (3, 3)\}.$$ Notice that, as Emilio Novati pointed out in the comments, the relation you posted in your question is in fact not an equivalence relation, since $(1,2) \in R$, but $(2,1) \notin R$, so it is not symmetric. Hence I have added the element $(2,1)$ to the relation.

Now, what is the equivalence class of $0$? Well, $0$ is related to $1$ through $(0,1) \in R$, it is related to itself (this will always be the case since it is an equivalence relation, and hence reflexive) through $(0,0) \in R$, it is related to $2$ through $(0,2) \in R$, but it is not related to $3$ through any element in $R$. So the equivalence class of $0$ is $$[0] = \{0,1,2\}.$$ Similarly, since we now know that $1 \in [0]$, we must have $[1] = [0]$ and by the same logic we also get $[2] = [0]$.

I hope that now it should also be obvious that $[3] = \{3\}$.