2.12: Partitions

Last updated
Save as PDF

Page ID: 95474

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Finally, there’s a special variation on the subset concept called a partition. A partition is a group of subsets of another set that together are both collectively exhaustive and mutually exclusive. This means that every element of the original set is in one and only one of the sets in the partition. Formally, a partition of $X$ is a group of sets $X_1, X_2, \dots, X_n$ such that:

\[X_1 \cup X_2 \cup \cdots \cup X_n = X,\] \[X_i \cap X_j = \varnothing \quad \text{for all $i$, $j$}.\]

So let’s say we’ve got a group of subsets that are supposedly a partition of $X$. The first line, above, says that if we combine the contents of all of them, we get everything that’s in $X$ (and nothing more). This is called being collectively exhaustive. The second line says that no two of the sets have anything in common: they are mutually exclusive.

As usual, an example is worth a thousand words. Suppose the set $D$ is { Dad, Mom, Lizzy, T.J., Johnny. } A partition is any way of dividing $D$ up into subsets that meet the above conditions. One such partition is:

{ Lizzy, T.J. }, { Mom, Dad }, and { Johnny }.

Another one is:

{ Lizzy }, { T.J. }, { Mom }, and { Johnny, Dad }.

Yet another is:

$\varnothing$, $\varnothing$, { Lizzy, T.J., Johnny, Mom, Dad }, and $\varnothing$.

All of these are ways of dividing up the Davies family into groups so that no one is in more than one group, and everyone is in some group. The following is not a partition:

{ Mom, Lizzy, T.J. }, and { Dad }

because it leaves out Johnny. This, too, is not a partition:

{ Dad }, { Mom, T.J. }, and { Johnny, Lizzy, Dad }

because Dad appears in two of the subsets.

By the way, realize that every set ($S$) together with its (total) complement ($\overline{S}$) forms a partition of the entire domain of discourse $\Omega$. This is because every element either is, or is not, in any given set. The set of males and non-males are a partition of $\Omega$ because everything is either a male or a non-male, and never both (inanimate objects and other nouns are non-males, just as women are). The set of prime numbers and the set of everything-except-prime-numbers are a partition. The set of underdone cheeseburgers and the set of everything-except-underdone-cheeseburgers form a partition of $\Omega$. By pure logic, this is true no matter what the set is.

You might wonder why partitions are an important concept. The answer is that they come up quite a bit, and when they do, we can make some important simplifications. Take $S$, the set of all students at UMW. We can partition it in several different ways. If we divide $S$ into the set of males and the set of females, we have a partition: every student is either male or female, and no student is both. If we divide them into freshmen, sophomores, juniors, and seniors, we again have a partition. But dividing them into computer science majors and English majors does not give us a partition. For one thing, not everyone is majoring in one of those two subjects. For another, some students might be double-majoring in both. Hence this group of subsets is neither mutually exclusive nor collectively exhaustive.

Question: is the number of students $|S|$ equal to the number of male students plus the number of female students? Obviously yes. But why? The answer: because the males and the females form a partition. If we added up the number of freshmen, sophomores, juniors, and seniors, we would also get $|S|$. But adding up the number of computer science majors and English majors would almost certainly not be equal to $|S|$, because some students would be double-counted and others counted not at all. This is an example of the kind of beautiful simplicity that partitions provide.