Set Partitions

# Set Partitions

Another important definition to look at is a partition of a set into a collection of subsets which we define below.

 Definition: If $A$ is a set then a Partition of $A$ is a collection of nonempty subsets $A_1, A_2, ..., A_n$ of $A$ such that $A = \bigcup_{i=1}^{n} A_i$ and such that each of these subsets are pairwise disjoint, that is for $j \neq k$ we have that $A_j \cap A_k = \emptyset$ for each $j, k = 1, 2, ..., n$.

In essence, a partition of a set $A$ is a collection of subsets $A_1, A_2, ..., A_n$ for which each element in $A$ appears in only one of these subsets.

For example, consider finite set $A = \{ 1, 2, 3 \}$. This set can be partitioned in many different ways. For example, if we let $A_1 = \{ 1 \}$ and $A_2 = \{ 2, 3 \}$ then the subsets $A_1$ and $A_2$ form a partition of $A$ since clearly $A = A_1 \cup A_2$ and $A_1 \cap A_2 \neq \emptyset$.

It should be noted that we can also form a partition of an infinite set. For example, consider the set of integers:

(1)
\begin{align} \quad \mathbb{Z} = \{ 0, +1, -1, +2, -2, ... \} \end{align}

If we let $E \subset \mathbb{Z}$ be defined by:

(2)
\begin{align} \quad E = \{ x : x \in \mathbb{Z} \: \mathrm{and} \: x \: \mathrm{is \: even.} \} \end{align}

and if we let $O \subset \mathbb{Z}$ be defined by:

(3)
\begin{align} \quad O = \{ x : x \in \mathbb{Z} \: \mathrm{and} \: x \: \mathrm{is \: odd.} \} \end{align}

Clearly ever integer is either even or odd (including $0$ being even) so $\mathbb{Z} = E \cup O$, and no integer is both even and odd so every $x \in \mathbb{Z}$ belongs to only one of $E$ or $O$, i.e., $E \cap 0 = \emptyset$ so $E$ and $O$ form a partition of $\mathbb{Z}$.

It the examples above, the partitions of $A$ and $\mathbb{Z}$ were formed from two sets. If we form a partition of a collection of more than two sets then we MUST ensure that each set is pairwise disjoint. For small finite sets, this is a simple process. For example, consider the set $B = \{ 1, 2, 3, 4, 5 \}$. Let $B_1 = \{ 1, 2 \}$, $B_2 = \{3, 4 \}$ and $B_5 = \{ 5 \}$. It should be clear that $B = B_1 \cup B_2 \cup B_3$ and that $B_1 \cap B_2 = \emptyset$ and $B_1 \cap B_3 = \emptyset$ so $B_1, B_2, B_3$ form a partition of $B$.