Partitions and Counting

Section 1.4 Partitions and Counting

Two sets are called disjoint if their intersection is empty. A collection of sets is called pairwise disjoint if every pair of distinct sets in the collection is disjoint. A partition of a set \(S\) is a collection of pairwise disjoint nonempty subsets of \(S\) whose union is all of \(S\text{.}\)

🔗

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.

🔗

🔗

Prev Top Next