# Equivalence Classes and Partitions

## Trigonometry # 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

• 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}:$$

$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

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