Question

On the set $\mathbb{Z}$ of all integers, consider the relation \[R=\left\{ \left( a,b \right):a-b\text{ is divisible by 3} \right\}\].
Show that R is an equivalence relation on $\mathbb{Z}$.
Also, find the partitioning of $\mathbb{Z}$ into mutually disjoint equivalence classes.

Answer 1

Hint: Recall the definition of an equivalence relation. Use the fact that 0 is divisible by 3 to prove that the relation is reflexive. Use the fact that if a number is divisible by 3, then its negative is also divisible by 3 to prove that the relation is symmetric. Use the fact that the sum of two numbers divisible by 3 is also divisible by 3 to prove that the relation is transitive. Hence prove that the relation is an equivalence relation. Form three classes of numbers, viz the class of numbers leaving 0 as remainder on division by 3, the class of numbers leaving 1 as remainder on division by 3 and the class of numbers leaving 2 as remainder on division by 3. Prove that the classes so formed are equivalence classes and define a partition of the set of integers.

Complete step-by-step answer:
Before solving the question, we need to understand what is an equivalence relation.
Reflexive relation: A relation R on a set “A” is said to be reflexive if $\forall a\in A$ we have $aRa$.
Symmetric relation: A relation R on a set “A” is said to be symmetric if $aRb\Rightarrow bRa$
Transitive relation: A relation R on a set “A” is said to be transitive if $aRb,bRc\Rightarrow aRc$.
Equivalence relation: A relation R on a set “A” is said to be an equivalence relation if the relation is reflexive, symmetric and transitive.
Class of an equivalence relation: A set S is said to be an equivalence class of a relation R if $\forall a,b\in S,aRb$ and if aRb then $a\in S\Rightarrow b\in S$,i.e. any two elements of an equivalence class are related to each other and any two elements which are related to each other are either both present in the equivalence class or both not in the equivalence class.
Reflexivity: We have $\forall a\in \mathbb{Z}$, a- a = 0 and 0 is divisible by 3. Hence, $\forall a\in \mathbb{Z},aRa$. Hence the relation is reflexive.
Symmetricity: We have if a-b is divisible by 3, then –(a-b) = b-a is also divisible by 3. Hence if aRb then bRa and hence the relation is symmetric.
Transitivity: We know that the sum of two integers divisible by 3 is also divisible by 3. Hence if a-b is divisible by 3 and b-c is divisible by 3, then a-b+b-c = a-c is also divisible by 3.
Hence, we have $aRb,bRc\Rightarrow aRc$ , and hence the relation is transitive.
Since the relation is reflexive, symmetric and transitive, the relation is an equivalence relation.
Consider the three classes of integers
$\begin{align}
  & {{C}_{1}}=\left\{ 3n,n\in \mathbb{Z} \right\} \\
 & {{C}_{2}}=\left\{ 3n+1,n\in \mathbb{Z} \right\} \\
 & {{C}_{3}}=\left\{ 3n+2,n\in \mathbb{Z} \right\} \\
\end{align}$
Claim 1: The classes ${{C}_{1}},{{C}_{2}}$ and ${{C}_{3}}$ are equivalence classes of the relation R.
Proof: Let ${{a}_{i}},{{b}_{i}}\in {{C}_{i}}$ for some arbitrary i={1,2,3}
Hence, we have ${{a}_{i}}=3n+\left( i-1 \right)$ and ${{b}_{i}}=3m+\left( i-1 \right)$ where $m,n\in \mathbb{Z}$
Hence, we have ${{a}_{i}}-{{b}_{i}}=3n+\left( i-1 \right)-3m-\left( i-1 \right)=3n-3m=3\left( n-m \right)$
Hence, we have ${{a}_{i}}R{{b}_{i}}$.
Now let $aRb$ and $a\in {{C}_{i}},b\in {{C}_{j}}$
Hence, we have $a=3n+\left( i-1 \right)$ and $b=3m+\left( j-1 \right),i,j\in \left\{ 1,2,3 \right\}$ where $m,n\in \mathbb{Z}$.
Hence, we have $a-b=3\left( n-m \right)+\left( i-j \right)$
Since a-b is divisible by 3, we have i-j is divisible by 3.
Now, we have $i-j\in \left[ -2,2 \right]$
Hence if 3 divides i-j, then i-j = 0.
Hence $i=j$ and hence they belong to the same class.
Hence ${{C}_{1}},{{C}_{2}}$ and ${{C}_{3}}$ are equivalence classes of relation R.
Claim 2: ${{C}_{1}},{{C}_{2}}$ and ${{C}_{3}}$ form a partition of the set of integers.
We know from Euclid’s division lemma $\forall n\in \mathbb{Z},n=3q+r,0\le r\le 2,q,r\in \mathbb{Z}$
Hence every integer is of one of the form 3n,3n+1 or 3n+2
Hence every integer belongs to one of the classes $\text{ }{{C}_{1}},{{C}_{2}}$ or ${{C}_{3}}$
Hence, we have $\mathbb{Z}={{C}_{1}}\bigcup {{C}_{2}}\bigcup {{C}_{3}}$
Also clearly ${{C}_{1}}\bigcap {{C}_{2}}=\phi ,{{C}_{2}}\bigcap {{C}_{3}}=\phi $ and ${{C}_{1}}\bigcap {{C}_{3}}=\phi $. Hence ${{C}_{1}},{{C}_{2}}$ and ${{C}_{3}}$ form a partition of the set of integers.

Note: [1] Students usually make a mistake while proving reflexivity of a relation. In reflexivity, we need all the elements of a to be related with themselves, and even if a single element is found such that it is not related with itself, then the relation is not reflexive.
[2] The set of equivalence classes of an equivalence relation on a set A defines a partition on the set and a partition of a set A defines an equivalence relation on the set A.