Set Partitions
Why
We divide a set into disjoint subsets whose union is the whole set. In this way we can handle each subset of the main set individually, and so handle the entire set piece by piece.
Decomposing a set
Two sets $A$ and $B$ divide a set $X$ if $A \cup B = X$ and $A \cap B = \varnothing$. Although every element is in either $A$ or $B$, no element is in both.
Definition
Suppose $X$ is a set.
A set $F$ of subsets of $X$ is a
partition (or
decomposition,
set partition) of $X$ if
In other words, $F$ is a set of
nonempty pairwise disjoint subsets of
$X$ covering $X$.
Other terminology used to describe condition (2)
is mutually exclusive and
nonoverlapping.
Other terminology used to describe condition (1)
is that the sets are
collectively exhaustive.
We call the elements of a partition the
parts (or
pieces,
blocks,
cells) of the partition.
Other terminology
Occasionally, the term unlabeled partition is used, and the term partition is reserved for a separate concept. In this case, the term allocation is sometimes used as an abbreviation for unlabeled partition.