# Calculus

## Set Theory # 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. $\require{AMSsymbols}{\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( \kern-2pt{\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.$$

## Solved Problems

Click or tap a problem to see the solution.

### Example 1

Which of the following collections of subsets are partitions of $$\left\{ {0,1,2,3,4,5} \right\}?$$
1. $$\left\{ {0,1,2} \right\},\left\{ {4,3} \right\},\left\{ {5,4} \right\}$$
2. $$\left\{{}\right\},\left\{ {0,2,1} \right\},\left\{ {4,3,5} \right\}$$
3. $$\left\{ {5,4,0,3} \right\},\left\{ 2 \right\},\left\{ 1 \right\}$$
4. $$\left\{ 5 \right\},\left\{ {4,3} \right\},\left\{ {0,2} \right\}$$
5. $$\left\{ 2 \right\},\left\{ 1 \right\},\left\{ 5 \right\},\left\{ 3 \right\},\left\{ 0 \right\},\left\{ 4 \right\}$$

### Example 2

List all the partitions of the following sets:
1. $$A = \left\{ {1,2} \right\}$$
2. $$B = \left\{ {1,2,3} \right\}$$

### Example 3

List the ordered pairs in the equivalence relation $$R$$ induced by the partition $$P = \left\{ {\left\{ {a,b,c} \right\},\left\{ d \right\},\left\{ e \right\}} \right\}$$ of the set $$\left\{ {a,b,c,d,e} \right\}.$$

### Example 4

A relation $$R$$ on the set $$A = \left\{ {a,b,c,d,e} \right\}$$ is defined as follows: $$R = \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {b,a} \right),\left( {b,b} \right),\left( {c,c} \right),}\right.$$ $$\kern-2pt\left.{\left( {c,d} \right),\left( {c,e} \right),}\right.$$ $$\kern-2pt\left.{\left( {d,c} \right),\left( {d,d} \right),}\right.$$ $$\kern-2pt\left.{\left( {d,e} \right),\left( {e,c} \right),}\right.$$ $$\kern-2pt\left.{\left( {e,d} \right),\left( {e,e} \right)} \right\}.$$
Determine the equivalence classes of $$R.$$

### Example 5

The relation $$R = \left\{ {\left( {a,b} \right) \mid \left| {a + 1} \right| = \left| {b + 1} \right|} \right\}$$ is defined on the set of integers $$\mathbb{Z}.$$ Find the equivalence classes for $$R.$$

### Example 6

Suppose $$R$$ is an equivalence relation on a finite set $$A,$$ and every equivalence class has the same cardinality $$m.$$ Express the cardinality of the relation $$\left| R \right|$$ in terms of $$\left| A \right|$$ and $$m.$$

### Example 1.

Which of the following collections of subsets are partitions of $$\left\{ {0,1,2,3,4,5} \right\}?$$
1. $$\left\{ {0,1,2} \right\},\left\{ {4,3} \right\},\left\{ {5,4} \right\}$$
2. $$\left\{{}\right\},\left\{ {0,2,1} \right\},\left\{ {4,3,5} \right\}$$
3. $$\left\{ {5,4,0,3} \right\},\left\{ 2 \right\},\left\{ 1 \right\}$$
4. $$\left\{ 5 \right\},\left\{ {4,3} \right\},\left\{ {0,2} \right\}$$
5. $$\left\{ 2 \right\},\left\{ 1 \right\},\left\{ 5 \right\},\left\{ 3 \right\},\left\{ 0 \right\},\left\{ 4 \right\}$$

Solution.

1. The collection of subsets $$\left\{ {0,1,2} \right\},\left\{ {4,3} \right\},\left\{ {5,4} \right\}$$ is not a partition of $$\left\{ {0,1,2,3,4,5} \right\}$$ since the element $$4$$ is contained in two blocks.
2. The subsets $$\left\{{}\right\},\left\{ {0,2,1} \right\},\left\{ {4,3,5} \right\}$$ are not a partition because they have the empty set.
3. The collection of subsets $$\left\{ {5,4,0,3} \right\},\left\{ 2 \right\},\left\{ 1 \right\}$$ is a partition of $$\left\{ {0,1,2,3,4,5} \right\}.$$
4. The subsets $$\left\{ 5 \right\},\left\{ {4,3} \right\},\left\{ {0,2} \right\}$$ are not a partition of $$\left\{ {0,1,2,3,4,5} \right\}$$ because the element $$1$$ is missing.
5. The subsets $$\left\{ 2 \right\},\left\{ 1 \right\},\left\{ 5 \right\},\left\{ 3 \right\},\left\{ 0 \right\},\left\{ 4 \right\}$$ form a partition of the set $$\left\{ {0,1,2,3,4,5} \right\}.$$

### Example 2.

List all the partitions of the following sets:
1. $$A = \left\{ {1,2} \right\}$$
2. $$B = \left\{ {1,2,3} \right\}$$

Solution.

1. The set $$A = \left\{ {1,2} \right\}$$ has $$2$$ partitions: $\left\{ 1 \right\},\left\{ 2 \right\}$ $\left\{ {1,2} \right\}$
2. The set $$B = \left\{ {1,2,3} \right\}$$ has $$5$$ partitions: $\left\{ 1 \right\},\left\{ 2 \right\},\left\{ 3 \right\}$ $\left\{ {1,2} \right\},\left\{ 3 \right\}$ $\left\{ {1,3} \right\},\left\{ 2 \right\}$ $\left\{ 1 \right\},\left\{ {2,3} \right\}$ $\left\{ {1,2,3} \right\}$

### Example 3.

List the ordered pairs in the equivalence relation $$R$$ induced by the partition $$P = \left\{ {\left\{ {a,b,c} \right\},\left\{ d \right\},\left\{ e \right\}} \right\}$$ of the set $$\left\{ {a,b,c,d,e} \right\}.$$

Solution.

The partition $$P$$ includes $$3$$ subsets which correspond to $$3$$ equivalence classes of the relation $$R.$$ We can denote these classes by $$E_1,$$ $$E_2,$$ and $$E_3.$$ They contain the following pairs:

${{E_1} = \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {a,c} \right),}\right.}\kern0pt{\left.{\left( {b,a} \right),\left( {b,b} \right),}\right.}\kern0pt{\left.{\left( {b,c} \right),\left( {c,a} \right),}\right.}\kern0pt{\left.{\left( {c,b} \right),\left( {c,c} \right)} \right\}}$

${E_2} = \left\{ {d,d} \right\}$

${E_3} = \left\{ {e,e} \right\}$

So, the relation $$R$$ in roster form is given by

${R = \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {a,c} \right),}\right.}\kern0pt{\left.{\left( {b,a} \right),\left( {b,b} \right),}\right.}\kern0pt{\left.{\left( {b,c} \right),\left( {c,a} \right),}\right.}\kern0pt{\left.{\left( {c,b} \right),\left( {c,c} \right),}\right.}\kern0pt{\left.{\left( {d,d} \right),\left( {e,e} \right)} \right\}.}$

### Example 4.

A relation $$R$$ on the set $$A = \left\{ {a,b,c,d,e} \right\}$$ is defined as follows: $$R = \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {b,a} \right),\left( {b,b} \right),\left( {c,c} \right),}\right.$$ $$\kern-2pt\left.{\left( {c,d} \right),\left( {c,e} \right),}\right.$$ $$\kern-2pt\left.{\left( {d,c} \right),\left( {d,d} \right),}\right.$$ $$\kern-2pt\left.{\left( {d,e} \right),\left( {e,c} \right),}\right.$$ $$\kern-2pt\left.{\left( {e,d} \right),\left( {e,e} \right)} \right\}.$$
Determine the equivalence classes of $$R.$$

Solution.

First we check that $$R$$ is an equivalence relation.

$$R$$ is reflexive since it contains all identity elements $$\left( {a,a} \right),\left( {b,b} \right), \ldots ,\left( {e,e} \right).$$

$$R$$ is symmetric. For each non-reflexive element its reverse also belongs to $$R:$$

${\left( {a,b} \right),\left( {b,a} \right) \in R,\;\;}\kern0pt{\left( {c,d} \right),\left( {d,c} \right) \in R,\;\; \ldots }$

$$R$$ is transitive. For example, the relation contains the overlapping pairs $$\left( {a,b} \right),\left( {b,a} \right)$$ and the element $$\left( {a,a} \right).$$ Thus, we conclude that $$R$$ is an equivalence relation.

Consider the elements related to $$a.$$ The relation $$R$$ contains the pairs $$\left( {a,a} \right)$$ and $$\left( {a,b} \right).$$ Hence $$a$$ and $$b$$ are related to $$a.$$ Similarly we find that $$a$$ and $$b$$ related to $$b.$$ There are no other pairs in $$R$$ containing $$a$$ or $$b.$$ So these items form the equivalence class $$\left\{ {a,b} \right\}.$$ Notice that the relation $$R$$ has $$2^2=4$$ ordered pairs within this class.

Take the next element $$c$$ and find all elements related to it. There are $$3$$ pairs with the first element $$c:$$ $${\left( {c,c} \right),}$$ $${\left( {c,d} \right),}$$ $${\left( {c,e} \right).}$$ Similarly, we find pairs with the elements related to $$d$$ and $$e:$$ $${\left( {d,c} \right),}$$ $${\left( {d,d} \right),}$$ $${\left( {d,e} \right),}$$ $${\left( {e,c} \right),}$$ $${\left( {e,d} \right),}$$ and $${\left( {e,e} \right).}$$ This set of $$3^2 = 9$$ pairs corresponds to the equivalence class $$\left\{ {c,d,e} \right\}$$ of $$3$$ elements.

Thus, the relation $$R$$ has $$2$$ equivalence classes $$\left\{ {a,b} \right\}$$ and $$\left\{ {c,d,e} \right\}.$$

### Example 5.

The relation $$R = \left\{ {\left( {a,b} \right) \mid \left| {a + 1} \right| = \left| {b + 1} \right|} \right\}$$ is defined on the set of integers $$\mathbb{Z}.$$ Find the equivalence classes for $$R.$$

Solution.

It’s easy to make sure that $$R$$ is an equivalence relation. The equivalence classes of $$R$$ are defined by the expression $$\left\{ { – 1 – n, – 1 + n} \right\},$$ where $$n$$ is an integer.

Below are some examples of the classes $$E_n$$ for specific values of $$n$$ and the corresponding pairs of the relation $$R$$ for each of the classes:

${n = 0:\;{E_0} = \left[ { – 1} \right] = \left\{ { – 1} \right\},\;}\kern0pt{{R_0} = \left\{ {\left( { – 1, – 1} \right)} \right\}}$

${n = 1:\;{E_1} = \left[ { – 2} \right] = \left\{ { – 2,0} \right\},\;}\kern0pt{{R_1} = \left\{ {\left( { – 2, – 2} \right),\left( { – 2,0} \right),}\right.}\kern0pt{\left.{\left( {0, – 2} \right),\left( {0,0} \right)} \right\}}$

${n = 2:\;{E_2} = \left[{ – 3} \right] = \left\{ { – 3,1} \right\},\;}\kern0pt{{R_2} = \left\{ {\left( { – 3, – 3} \right),\left( { – 3,1} \right),}\right.}\kern0pt{\left.{\left( {1, – 3} \right),\left( {1,1} \right)} \right\}}$

${n = – 2:\;{E_{ – 2}} = \left[ 1 \right] = \left\{ {1, – 3} \right\},\;}\kern0pt{{R_{ – 2}} = \left\{ {\left( {1,1} \right),\left( {1, – 3} \right),}\right.}\kern0pt{\left.{\left( { – 3,1} \right),\left( { – 3, – 3} \right)} \right\}}$

${n = 10:\;{E_{10}} = \left[ { – 11} \right] = \left\{ { – 11,9} \right\},\;}\kern0pt{{R_{10}} = \left\{ {\left( { – 11, – 11} \right),\left( { – 11,9} \right),}\right.}\kern0pt{\left.{\left( {9, – 11} \right),\left( {9,9} \right)} \right\}}$

${n = – 10:\;{E_{ – 10}} = \left[ { – 11} \right] = \left\{ {9, – 11} \right\},\;}\kern0pt{{R_{ – 10}} = \left\{ {\left( {9,9} \right),\left( {9, – 11} \right),}\right.}\kern0pt{\left.{\left( { – 11,9} \right),\left( { – 11, – 11} \right)} \right\}}$

As it can be seen, $${E_{2}} = {E_{- 2}},$$ $${E_{10}} = {E_{ – 10}}.$$ It follows from here that we can list all equivalence classes for $$R$$ by using non-negative integers $$n.$$

### Example 6.

Suppose $$R$$ is an equivalence relation on a finite set $$A,$$ and every equivalence class has the same cardinality $$m.$$ Express the cardinality of the relation $$\left| R \right|$$ in terms of $$\left| A \right|$$ and $$m.$$

Solution.

Consider an equivalence class consisting of $$m$$ elements.

The relation $$R$$ is symmetric and transitive. Therefore each element of an equivalence class has a direct path of length $$1$$ to another element of the class. This gives us $$m\left( {m – 1} \right)$$ edges or ordered pairs within one equivalence class.

The relation $$R$$ is reflexive. This adds $$m$$ more pairs, so the total number of ordered pairs within one equivalence class is

$\require{cancel}{m\left( {m – 1} \right) + m }={ {m^2} – \cancel{m} + \cancel{m} }={ {m^2}.}$

Determine now the number of equivalence classes in the relation $$R.$$ Since the classes form a partition of $$A,$$ and they all have the same cardinality $$m,$$ the total number of elements in $$A$$ is equal to

$\left| A \right| = nm,$

where $$n$$ is the number of classes in $$R.$$

Hence, the number of pairs in the relation $$R$$ is given by

${\left| R \right| = n{m^2} }={ \frac{{\left| A \right|}}{\cancel{m}}{m^{\cancel{2}}} }={ \left| A \right|m.}$