1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Yes, an equivalence class is the equivalence class of an element. Here there are two equivalence classes, $\{0,1,2\}$ and $\{3\}$. $\endgroup$ Mar 4, 2015 at 6:40
  • $\begingroup$ What is {3} the equivalence class of? And same of {0, 1, 2}? $\endgroup$ Mar 4, 2015 at 6:44
  • $\begingroup$ $\{3\}$ is the equivalence class of $3$. The other one is the equivalence class of $0$. It is also the equivalence class of $1$. It is also the equivalence class of $2$. Think of an equivalence class as a family. The numbers $0,1,2$ are in the same family. But $3$ is solitary, it is not related to anybody except himself. $\endgroup$ Mar 4, 2015 at 7:07
  • $\begingroup$ Is your problem correct? don't you have forget $(2,1)$ in the relation definition? $\endgroup$ Mar 4, 2015 at 11:22

1 Answer 1

1
$\begingroup$

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\}$.

$\endgroup$
2
  • $\begingroup$ Thank you!! That makes it more clear. Why theorem did you use to state that "we now know that $1 \in [0]$, we must have $[1] = [0]$"? $\endgroup$ Mar 4, 2015 at 16:10
  • $\begingroup$ @committedandroider It's not really any particular theorem. It's just that since we know that $1$ is related to $0$, $0$ must also be related to $1$ (by symmetry), and it must be related to every other element in the class (by transitivity), so if an element $x$ is in another element $y$'s equivalence class, then $[x] = [y]$. In fact, this is the whole idea behind equivalence classes and why they are interesting! $\endgroup$
    – mrp
    Mar 4, 2015 at 17:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .