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:

Modulus 4, General

  • 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.

 

 

How clear is this post?