[Math] Equivalence Relation & corresponding equivalence Classes

discrete mathematicselementary-set-theoryequivalence-relations

From my basic understanding, $R$ is an equivalence relation on the set $A$, which is
a relation between elements of a set that is reflexive, symmetric, and transitive.

I am not sure how to find the distinct equivalence classes of $R$ in the following relation:

$$A = \{-4,-3,-2,-1,0,1,2,3,4,5\}$$ $$\text{For all}\;x, y \in A,\;x\,R\,y \iff 3 \mid (x-y)$$

Best Answer

You are correct that the relation defined is an equivalence relation on A is an equivalence relation, essentially $$\forall x \in A, xRy \iff 3\mid (x - y) \iff x\equiv y \pmod 3$$

The relation $R$, i.e., defines congruence modulo $3$. So your task boils down to finding the congruence classes, $\pmod 3$.

Do you know how to find the equivalence classes of your set, $\pmod 3$?

  • Class one: Which elements have are divisible by $3$? $\quad A_0 = \{-3, 0, 3\}$
  • Class two: Which elements leave a remainder of $1$ when divided by $3$? $\quad A_1 =\{-2, 1, 4\}$
  • Class three: Which elements leave a remainder of $2$ when divided by $3$? $\quad A_2 = \{-4, -1, 2, 5\}$

You're done: three equivalence classes.

$$A = A_0 \cup A_1 \cup A_2 = \{-4,-3,-2,-1,0,1,2,3,4,5\},$$ $$ \quad A_i \cap A_j = \varnothing, \;\text{when}\;\;i\neq j, \text{ for}\;\; i, j \in \{0, 1, 2\}$$

Related Question