Calculus

Set Theory

Set Theory Logo

Equivalence Classes and Partitions

Equivalence Classes

Definitions

Let \(R\) be an equivalence relation on a set \(A,\) and let \(a \in 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 \(\left[ a \right].\) Thus, by definition,

\[\left[ a \right] = \left\{ {b \in A \mid aRb} \right\} = \left\{ {b \in A \mid a \sim b} \right\}.\]

If \(b \in \left[ a \right]\) then the element \(b\) is called a representative of the equivalence class \(\left[ a \right].\) 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.\)

\[A/R = \left\{ {\left[ a \right] \mid a \in A} \right\}.\]

Properties of Equivalence Classes

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

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}:\)

\[R = \left\{ {\left( {a,b} \right) \mid a \equiv b\;\left( {\bmod 3} \right)} \right\}.\]

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:

\[\left[ 0 \right] = \left\{ { \ldots , - 9, - 6, - 3,0,3,6,9, \ldots } \right\}\]
\[\left[ 1 \right] = \left\{ { \ldots , - 8, - 5, - 2,1,4,7,10, \ldots } \right\}\]
\[\left[ 2 \right] = \left\{ { \ldots , - 7, - 4, - 1,2,5,8,11, \ldots } \right\}\]

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

Partition of a set A.
Figure 1.

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.\)

See solved problems on Page 2.

Page 1 Page 2