Equivalence Classes and Partitions

Equivalence Classes

Definitions

Let R be an equivalence relation on a set A, and let a ∈ A. The equivalence class of a is called the set of all elements of A which are equivalent to a.

The equivalence class of an element a is denoted by [a]. Thus, by definition,

If b ∈ [a] then the element b is called a representative of the equivalence class [a]. Any element of an equivalence class may be chosen as a representative of the class.

The set of all equivalence classes of \(A\) is called the quotient set of \(A\) by the relation \(R.\) The quotient set is denoted as \(A/R.\)

Properties of Equivalence Classes

If \(R \) (also denoted by \(\sim\)) is an equivalence relation on set \(A,\) then

• Every element \(a \in A\) is a member of the equivalence class \(\left[ a \right].\)
  \[\forall\, a \in A,a \in \left[ a \right]\]
• Two elements \(a, b \in A\) are equivalent if and only if they belong to the same equivalence class.
  \[\forall\, a,b \in A,a \sim b \text{ iff } \left[ a \right] = \left[ b \right]\]
• Every two equivalence classes \(\left[ a \right]\) and \(\left[ b \right]\) are either equal or disjoint.
  \[\forall\, a,b \in A,\left[ a \right] = \left[ b \right] \text{ or } \left[ a \right] \cap \left[ b \right] = \varnothing\]

Example

A well-known sample equivalence relation is Congruence Modulo \(n\). Two integers \(a\) and \(b\) are equivalent if they have the same remainder after dividing by \(n.\)

Consider, for example, the relation of congruence modulo \(3\) on the set of integers \(\mathbb{Z}:\)

The possible remainders for \(n = 3\) are \(0,1,\) and \(2.\) An equivalence class consists of those integers that have the same remainder. Hence, there are \(3\) equivalence classes in this example:

Similarly, one can show that the relation of congruence modulo \(n\) has \(n\) equivalence classes \(\left[ 0 \right],\left[ 1 \right],\left[ 2 \right], \ldots ,\left[ {n - 1} \right].\)

Partitions

Let \(A\) be a set and \({A_1},{A_2}, \ldots ,{A_n}\) be its non-empty subsets. The subsets form a partition \(P\) of \(A\) if

• The union of the subsets in \(P\) is equal to \(A.\)
  \[\bigcup\limits_{i = 1}^n {{A_i}} = {A_1} \cup {A_2} \cup \ldots \cup {A_n} = A\]
• The partition \(P\) does not contain the empty set \(\varnothing.\)
  \[{A_i} \ne \varnothing \;\forall \,i\]
• The intersection of any distinct subsets in \(P\) is empty.
  \[{A_i} \cap {A_j} = \varnothing \;\forall \,i \ne j\]

There is a direct link between equivalence classes and partitions. For any equivalence relation on a set \(A,\) the set of all its equivalence classes is a partition of \(A.\)

The converse is also true. Given a partition \(P\) on set \(A,\) we can define an equivalence relation induced by the partition such that \(a \sim b\) if and only if the elements \(a\) and \(b\) are in the same block in \(P.\)