# Discrete Math: Equivalence relations and quotient sets

1. For each of the sets below and the corresponding binary relation, prove that the relation is binary relation and find the quotient set.

(a) Let A={1,2,3,4,…} be the set of natural numbers. Consider the binary relation R on A defined by: for all n,m∈A, (n,m)∈R if, and only if, their difference n−m is divisible by 10.

So, for this question, I already verified that it is reflexive, symmetric, and transitive. However, I am not sure how to begin to find the quotient set... Won't there be infinity equivalence classes?

Can someone please explain to me how to approach this?

Thanks!

• "... Won't there be infinity equivalence classes? " In this case, no. But would that be a problem if it were? Sep 23 '19 at 15:54
• yes because I couldn't give an extensional definition for A/R Sep 23 '19 at 15:57
• Let $A = \mathbb R$ let $a R b \iff a-b \in \mathbb Z$. Then there are infinitely many equivalence classes. If that's a problem... we have to work it out because.... it exists. In this case, the equivalence class of, say, $\pi$ is $\{\pi + k|k\in \mathbb Z\}$. But there are infinitely many classes. $A/R = \{\{x_0+z|z\in \mathbb Z\}: x_0 \in [0,1)\}$. That's an infinite set of classes. But we had to find a way to describe it. Sep 23 '19 at 16:02

Let's look at the class of $$0$$ : $$0^\equiv = \{\dots; -20; -10; 0, 10 ; 20 ;\dots\}$$ Now look at the class of $$7$$ : $$7^\equiv = \{\dots; -13; -3; 7, 17 ; 27 ;\dots\}$$

Each class is infinite, but there will be exactly 10 equivalence classes. They correspond to the different remainders you can get with an Euclidean division by 10.

In other words, $$m\equiv n \Longleftrightarrow m \operatorname{Mod}10 = n \operatorname{Mod} 10$$.

• can you explain to me what "different rests you can get with an Euclidean division by 10" means? Thanks Sep 23 '19 at 15:37
• @FrodoBaggins Sorry rest := remainder ! I'll edit that! Sep 23 '19 at 15:44

One recipe to visualize equivalence classes is to pick a generic natural number and determine which other numbers are equivalent (considered "equal" in that sense) to it. Take $$2$$, e.g., then the numbers $$12$$, $$22$$, $$32$$, $$42$$ and so on are equivalent to $$2$$. Hence $$$$, the equivalence class of $$2$$, is $$=\{2,12,22,32,42,52, \dots\}.$$

If two numbers, $$a$$ and $$b$$, are equivalent the $$10|a-b$$ which means there exists an integer $$k$$ so that $$a-b = 10k$$. Which means $$a = 10k + b$$.

So a number is equivalent to $$b$$ if and only if the number is equal to $$10k+b$$ for some integer $$k$$.

So the equivalence class of $$b$$ which be belongs to is: $$\{n=10k + b| n> 0; k \in \mathbb Z\}$$

So, for instance, the equivalence class of $$57$$ is $$\{n=10k + 57|n > 0; k\in \mathbb Z\} = \{57,47,37,27,17,7,67,77,.....\} = \{7, 17, 27,37,.....\}$$.

Now the quotient set is ... the set of the equivalence classes.

You ask if there will be infinitely many equivalence classes. Well, in this case no but in general there is nothing wrong with that.