Partition of a Set

Partition of a set

The partition of a set $A$ is a collection of subsets of $A$ such that none of the subsets are empty that is no two subsets in the collection have common elements, and the union of all the subsets in the collection is equal to $A$. If we denote a partition of a set $A$ by $\cal{P}$, then by definition, we can derive the following facts:

• $B \in {\cal P} \Rightarrow B \ne \emptyset$

• $(B\in {\cal P} \land C \in {\cal P}) \Rightarrow B\cap C = \emptyset$

• $\bigcup \limits_{B\in {\cal P}}B = A$

Here, the notation $\bigcup \limits_{B\in {\cal P}}B$ refers to the union of all the sets in the partition ${\cal P}$. Let’s look at a few examples to further understand how to partition a set.

Examples

Let’s take a set $D =\{0,1,2,3,4,5,6,7,8,9\}$ as a first example. We’ll carefully verify that each of the following is a partition of the set $D$:

$\cal P_1 = \{\{0,2,4,6,8\},\{1,3,5,7,9\} \}$

$\cal P_2 = \{\{0\}, \{1,2,3,4,5,\},\{6,7,8,9\} \}$

$\cal P_3 = \{\{0,1,3,6,9\},\{2,4,5,7,8\} \}$

$\cal P_4 = \{\{0,3,6,9\},\{1,4,7\},\{2,5,8\} \}$

It’s important to note that ${\cal C}_D = \{\{0,3,6,9\},\{1,5,7\},\{0,2,4,8\} \}$ is not a partition of $D$ because $0$ belongs to two subsets in ${\cal C}_D$.

Let’s understand another example by analyzing the following set:

$E =\{\text{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}\}$

We can carefully verify that the following two sets are the partitions of $E$:

${\cal P_v} = \{\{\text{a, e, i, o, u}\}, \{\text{b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z}\} \}$

${\cal P_h} = \{\{\text{a, c, e, i, m, n, o, r, s, u, v, w, x, z}\}, \{\text{b, d, f, h, k, l, t}\}, \{\text{g, j, p, q, y}\}\}$

Note that ${\cal C}_E = \{\{\text{a, e, i, o, u}\}, \{\text{b, d, f, h, k, l, t}\}, \{\text{g, j, p, q, y}\}\}$ is not a partition of $E$ because the union of all the subsets in ${\cal C}_E$ is not the set $E$.

Equivalence classes

Let’s consider a set $S$ and an equivalence relation, $R$ on $S$. Two elements $a$ and $b$ of the set $S$ are equivalent to each other if $aRb$. Therefore, an equivalence relation $R$ defined on the set $S$ divides it into mutually disjoint subsets, each having elements equivalent to each other. We call each such subset an equivalence class. The equivalence classes are disjoint, and the union of all the classes that are equal to $S$. Because all the elements of an equivalence class are equivalent to each other, we usually nominate one element from each equivalence class, calling it the representative of that class.

Example

Let’s look at the congruence modulo $5$ relation defined on a set of integers. Because a congruence relation is an equivalence relation, it divides the set of integers into equivalence classes. For the congruence modulo $5$ relation, there are five equivalence classes because any integer divided by $5$ can have one of the five possible remainders. All integers with the same remainder when divided by $5$ belong to the same equivalence class. The set of integers is divided into the following five equivalence classes for the congruence modulo $5$ relation: