Recall the  relation \(\equiv \text{ mod} (4)\) on the set \(\mathbb{ N}.\)

One of the equivalence classes is \([0] = \{ ..., -8, -4, 0, 4, 8, ...\}\) which is equivalent to writing \([0] = [4] = [-4] = [8] = [-8] ...\)

We could do this because the equivalence class collects all the natural numbers that are related to zero under the relation \(\equiv \text{ mod} (4)\)

The following theorem generalises this idea for any relation \(\equiv \text{ mod} (n)\) on the set \(\mathbb{ N}:\) for the integer \(n.\)

Let \(R\) be an equivalence relation on set \(A.\) If \(a, b \in A,\) then \([a] = [b] \iff  aRb.\)

Essentially, equivalence classes  \([a] = [b]\) are equal if the elements  \(a, b \in A,\) are related under the relation \(R.\) And simultaneously, knowing that elements \(a, b \in A,\) are related under \(R\) means their equivalence classes  \([a] = [b]\) are equal.

An equivalence class  \(\equiv \text{ mod} (n)\) divides set a \(A\) into \(n\) equivalence classes. We call this situation a partition of set \(A.\)

A partition of a set \(A\) is defined as a set of non-empty subsets of \(A,\) such that both these conditions are simultaneously satisfied:

 (i) the union of all these subsets equals \(A.\)

(ii) the intersection of any two different subsets is

Let’s return to our example: \(\equiv \text{ mod} (4)\) on the set \(\mathbb{ N}.\) We could represent this set as:

• NOTE: Each equivalence class above represents an infinite set and despite the drawing suggesting \([0]\) is larger than \([3]\) for instance, this is not true.
• The union of these equivalence classes gives the whole set:

\[[0] \cup [1] \cup [2] \cup [3] = \mathbb{ Z}\]

In general, \([0] \cup [1] \cup [2] \cup ... \cup [n-1] \cup [n] = A\) for the relation \(\equiv \text{mod}(n)\) on a set \(A.\)

• The intersection of any of the equivalence classes results in an empty set:

\([0] \cap [1]\) for example is an empty set \(\emptyset\) since there are no elements in \([0]\) that are also in \([1]\)

In general, we write \([a] \cap [b] = \emptyset \text{ } \forall a, b \in  \mathbb{N}\)

• The partition formed for this set \(\{ [0], [1], [2], [3] \}\)

Let’s consider a new example.

Consider the partition \(P = \big \{ \{ ..., -4, -2, 0, 2, 4, ... \} \text{, } \{ ..., -5, -3, -1, 1, 3, 5, ... \} \big \} \text{ of } \mathbb{ Z}.\)

Let \(R\) be the equivalence relation on the set of integers. The equivalence classes are the two elements of \(P.\) We want to identify the equivalence relation \(R.\)

Solution:

• Clearly, the set \(\mathbb{Z}\) has been split into odd and even integers. So we write

\(R : \equiv \text{(mod)} 2\) on the set of integers.

Note the following:

• We have exactly two equivalence sets, each are infinite. Since this is a partition, the sets do not intersect.
• Since \(P\) is a partition, we also know the union of the two sets gives us \(\mathbb{ Z}.\)
• So we can conclude that these are the equivalence classes of \(\mathbb{ Z }\) if the relation \(R = \equiv \text{( mod)} 2.\)

Hence:

• So \([0] \cup [1] = \mathbb{ Z}\)
• The equivalence classes do not intersect: \([0] \cap [1] = \emptyset\)

Consider the next example:

List all the partitions of the set \(X = \{ a, b\}\)

Solution:

• We have the partition \(\{ \{a\}, \{b\} \}\) which corresponds to the equivalence relation We have \(R = \{ (a,a),  (b,b)\}\)
• We also have the partition \(\{ \{a, b \} \}\) corresponding to the equivalence relation \(R =\{ (a,a), (a,b), (b,a), (b,b)\}\)
• Note in both partitions, the union of the elements give the set \(X\) and the intersection of the elements is empty.