Equivalence Class.

Question

Let $R$ be the relation of congruence mod 4 on $\mathbb{Z}$:

$aRb \iff a - b = 4k$, for some $k \in \mathbb{Z}$

What integers are in the equivalence class of 31? How many distinct equivalence classes are there? What are they?

I don't understand how to find equivalence classes so I don't know where to begin.

Answer 1

As this lecture explains, an equvalance class is just a set of objects that are equal.

Let us start by defining equality: we say that a relation is an equality (denoted by '$=$' usually, but can be arbitrarily represented), if and only if it is:

• reflexive: this simply means the an object is equal to itself (e.g. $a =a$, we obviously need this to be true, or else we could say things like $1 \not = 1$ !)
• Symetric: this means that if $a = b $ then $b = a$ (again this should be obvious because if not, then we could say things like $2 = 1 + 1$ and at the same time say $1 + 1 \not = 2$.)
• Transitive: this means that if $a = b$ and $b = c $ then $a = c$ ( if this were not true then i could say $ a = 1$ and $b = a$ and yet say $ b \not = 1$)

Now let's talk about equivalence classes. We say $A$ is an equivalence class under the equivalence relation '=' of $a$ if and only if $\forall x \in A, x= a $ and $\forall x = a, x \in A$. In simple terms this means that we have group of objects called $A$, that are all equal to $a$.

Notice, though, I have been using '=' as we know it from elementary school. This is not necessarily the case! The only thing necessary for us to call something an equality is the three properties above.

Now on to the problem:

Your equivalence relationship is denoted '$R$', not '$=$', but (like I said), that is arbitrary. To find the equivalence class of $31$, we must first find what it is equivalent to! Now our definition says:

$a R b \mod(4)$ if and only if $a - b = 4k_{\in \mathbb{Z}}$

which for our case reads

$31 R b \mod(4)$ if and only if $31 - b = 4k_{\in \mathbb{Z}}$

Our goal is to find all of the $b$s, because they are equal to $a$. Now we can simply solve for $b$, because this is a regular algebra equation, with the regular concept of equality. solving for $b$ we get: $$ 31 - 4k_{\in \mathbb{Z}} = b$$

Now we can define our equivalence class. Our equivalence class is simply the set of all objects equal to 31 (with equal meaning $R$, in this case), therefore we can define the set $A$ to be the equivalence class of $31$ as follows: $$A := \{a| 31Ra\}$$ and because we know that the all of the numbers equal to $31$ are of the form $31 - 4k_{\in \mathbb{Z}} = b$ we can rewrite $A$ as follows: $$A := \{a | a = 31 - 4k_{\in \mathbb{Z}}\}$$

You might notice that the smallest positive number in this equivalence class is $3$, and all of the numbers are of the form $ 3 + 4k_{\in \mathbb{Z}} $. Well, if you add one, so that your numbers are of the form $4 + 4k_{\in \mathbb{Z}}$, then that is the same are the form $4k_{\in \mathbb{Z}}$, meaning that they are equivalent (you can prove this using your equivalence relation). If you continue to do this, you find that there is a pattern: all numbers will be equivalent to one of the following:

• $0$, if the number is of the form $0 + 4k_{\in \mathbb{Z}} $

• $1$, if the number is of the form $1 + 4k_{\in \mathbb{Z}} $

• $2$, if the number is of the form $2 + 4k_{\in \mathbb{Z}} $

• $3$, if the number is of the form $3 + 4k_{\in \mathbb{Z}} $

at which point the cycle would start again. Therefore there are $4$ equivalence classes.