Understanding Equivalence Classes / Representatives of a Class

Question

I'm currently struggling to understand most aspects of set theory, including this. I don't necessarily want a direct answer, but more of a push or a hint towards how to get the correct answer, as I don't even know where to begin.

In this problem, I've already proven that (Rn = {(x,y) ∈ Z×Z|(x−y)is divisible by n}) is an equivalence class by proving it is reflective, symmetric, and transitive, but now I'm being asked asked to list all the different equivalence classes with respect to Rn with a representative for each class. They also provided this for additional help:

Suppose n is a positive integer. For any integers x and y, (x−y) is divisible by n ⇐⇒ (x mod n)=(y mod n)

where (x mod n) denotes the remainder1 in the division of x by n.

P.S. - If you've seen any of my past questions I've posted in the last day or two, you'll understand I'm struggling heavily with discrete mathematics. This is easily one of the most difficult and challenging classes I've ever taken (and I love high level math and programming). Its a bit bothersome how little of this subject I understand.

Answer 1

Observe that you need to have, as representatives of equivalence classes, a whole set of numbers $\;\{x_1,...,x_n\}\;$ for which you can not deduce $\;x_i-x_j\;$ is divisible by $\;n\;$ for $\;1\le i\neq j\le n\;$ .

For example, take $\;x_1:=0=$ the integer zero. Can you see what equiv. class does $\;0\;$ represent? Can you now come up with other rather easy-to-get representatives for the rest?

An advice: if you still struggle, try to do some easy examples, as with $\;x=3,4\;$ or so.

Answer 2

Try considering a simple example where $n=3$. When we consider the equivalence classes given by the relation you've described, notice that two things are in the same equivalence class if and only if they have the same remainder modulo $n$; in our case, modulo $3$. But this is essentially the same thing as asking, "What are the different number of remainders I can get when I divide by $3$?"

When we divide any integer by $3$, we know we are going to get a remainder of $0$, $1$, or $2$. In other words, when we group integers together according to their remainder after dividing by $3$, we get $3$ such groups, i.e. $3$ equivalence classes (you can think of them being equivalent modulo $3$).

Usually, when we talk about equivalence classes, we write them by picking a representative from each equivalence class. So if we pick $a$ to be a representative of an equivlance class, we denote the equivalence class by $[a]$.

Consider the first equivalence class of integers whose remainder is $0$ after dividing by $3$. If we just list some of these out, we get $\dots, -6, -3, 0, 3, 6, \dots$ and so on. We can pick any of these to be our representative; however, one choice is the most natural: $0$. So we denote this equivalence class by $[0].$

Similarly, for the next two equivalence classes, clearly $1 \bmod 3 = 1$ and $2 \bmod 3 = 2$ and thus $1$ and $2$ are valid representatives for the equivalence classes of integers whose remainder is $1$ and $2$ respectively after dividing by $3$. So our next two equivalence classes are $[1]$ and $[2]$.

We now have our three equivalence classes: $[0], [1], [2]$. Writing out what each equivalence class contains, we see:

$[0] = \{\dots, -6, -3, 0, 3, 6, \dots\}$

$[1] = \{\dots, -5, -2, 1, 4, 7, \dots\}$

$[2] = \{\dots, -4, -1, 2, 5, 8, \dots\}$

When finding representatives for equivalence classes, there are two things we need to check:

• Are any of our equivalence classes equivalent? If so, then we are overcounting the number of equivalence classes. By eyeballing the sets above, it seems clear that $[0] \neq [1]$, $[1] \neq [2]$, and $[0] \neq [2]$ so we are good (you'll want to show this more rigorously in your proof). What if we include the equivalence class $[3]$? Well, $3 \bmod 3 = 0$ and thus it would be in the equivalence class of integers whose remainder is $0$ when dividing by $3$. But that's the same equivalence class as$[0]$!, i.e., $[0] = [3]$. It is for this reason why we don't include $[3]$ in our list of equivalence classes since we've already included $[0]$.
• Every element is in some equivalence class (since it is at least related to itself by reflexivity of the equivalence relation). Thus, in order to see if we got all the equivalence classes, we need to check for every element (in our case, every integer) that that element is in one of the equivalence classes we've listed. In our case, we need to show that for every $x \in \mathbb{Z}$, that $x \in [0]$, $x \in [1]$, or $x \in [2]$. By looking at the sets above, this seems to be true and you can show it is true by using the fact that the remainder you get after dividing $x$ by $3$ must be either one of $0$, $1$, or $2$.

Sorry for the quite verbose post. I hope this is of some help.