Section 1.4 Partitions and Counting
A partition of a set \(S\) is a collection of nonempty subsets of \(S\) whose union is all of \(S\) and any two of which have empty intersection.
Checkpoint 1.4.1.
Let \(S=\{a,b,c\}\text{.}\)
Write out all possible partitions of \(S\text{.}\)
Give an example of a collection of subsets of \(S\) whose union is all of \(S\text{,}\) but some two of which have nonempty intersection.
Give an example of a collection of subsets of \(S\text{,}\) any two of which have empty intersection, but whose union is not all of \(S\text{.}\)
Proposition 1.4.2. Partitions from functions.
Let \(f\colon S \to T\) be a function. The collection
\begin{equation*}
\mathcal{U} = \{f^{-1}(t)\colon t\in f(S)\}
\end{equation*}
is a partition of \(S\text{.}\)
Checkpoint 1.4.3.
Let \(f\colon S\to T\) be a function. (Do not assume that \(f\) is invertible!)
Show that \(\bigcup_{t\in T}f^{-1}(t) = S\text{.}\)
Suppose that \(t,t'\in T\) with \(t\neq t'\text{.}\) Show that \(f^{-1}(t)\cap f^{-1}(t')=\emptyset\text{.}\)
The previous two parts show that \(\mathcal{U}=\{f^{-1}(t)\colon
t\in T\}\) is a collection of subsets of \(S\) whose union is all of \(S\) and any two of which have empty intersection. Does this guarantee that \(\mathcal{U}\) is a partition of \(S\text{?}\)
A set is called finite if it contains a finite number of elements. A set that is not finite is called infinite. The number of elements in a finite set \(S\) is called the size of \(S\text{,}\) denoted \(|S|\) . Formally, we say \(|S|=n\text{,}\) where \(n\) is a positive integer, if there exists a one-to-one correspondence \(\{1,2,\ldots,n\} \to S\text{.}\)
Proposition 1.4.4. Counting elements in a set using partitions.
Let \(\mathcal{U}\) be a partition of a finite set \(S\text{.}\) We have
\begin{equation*}
|S| = \sum_{U\in \mathcal{U}} |U|.
\end{equation*}
Corollary 1.4.5. Counting elements in a set using preimages.
Let \(f\colon S\to T\) be a function, where \(S,t\) are finite sets. We have
\begin{equation}
|S|=\sum_{t\in T} |f^{-1}(t)|.\tag{1.4.1}
\end{equation}
Proof.
Because every \(s\) in \(S\) is a preimage of its image \(f(s)\text{,}\) we have \(s\in f^{-1}(\{f(s)\})\text{.}\) If \(t\neq f(s)\text{,}\) we have \(s\not\in f^{-1}(t)\text{.}\) It follows that every \(s\) in \(S\) is an element of exactly one of the preimage sets \(\{f^{-1}(t)\colon t\in T\}\text{.}\)
Exercises Exercises
1.
Let \(S\) be the 5-element set \(S=\{a,b,c,d,e\}\text{.}\) Given a partition \(\mathcal{U}\) of \(S\text{,}\) let \(\text{SIZE_LIST}(\mathcal{U})\) be the list of sizes of the sets that are elements of \(\mathcal{U}\text{,}\) listed in descending order. For example, the partition \(\mathcal{U}=\{\{a,b\},\{c,d\},\{e\}\}\) has \(\text{SIZE_LIST}(\mathcal{U})=(2,2,1)\text{.}\)
Find all possible size lists for partitions of \(S\text{.}\) (Hint: there are 7 in all.)
For each of the size lists in part a, give an example of a function
\(f\colon S\to S\) for which the corresponding partition given by
Proposition 1.4.2 has that size list.
2.
Let
\(f\colon S\to T\) be a function, where
\(S,T\) are finite sets. Use
(1.4.1) to show the following.
Suppose that \(f\) is injective. Show that \(|S|\leq |T|\text{.}\)
Suppose that \(f\) is surjective. Show that \(|S|\geq |T|\text{.}\)
3.
Let \(f\colon S\to T\) be a function, where \(S,T\) are finite sets.
Show that if \(f\) is injective and \(|S|=|T|\text{,}\) then \(f\) is surjective.
Show that if \(f\) is surjective and \(|S|=|T|\text{,}\) then \(f\) is injective.
