Show that enumerations of a finite set with more than one element are not unique. Find three different enumerations of the set \(X=\{a,b,c\}\text{.}\) How may enumerations of \(X\) are there in all?
Section 1.4 Enumeration and Partitions
Subsection 1.4.1 Finite Sets
A nonempty set \(S\) is called finite if there exists a one-to-one correspondence \(f\colon \{1,2,\ldots,n\} \to S\) for some positive whole number \(n\text{.}\) A one-to-one correspondence \(f\colon\{1,2,\ldots,n\} \to S\) is called an enumeration of \(S\) (or a counting, or an ordering of \(S\)). We often use the notation \(s_1,s_2,\ldots,s_n\) to denote \(f(1),f(2),\ldots,f(n)\text{.}\) We write \(|S|\) to denote the size of \(S\) (or the number of elements in \(S\)) for a finite set with an enumeration \(f\colon\{1,2,\ldots,n\} \to S\text{.}\) The empty set is defined to be finite, with size zero. A set that is not finite is called infinite.
Checkpoint 1.4.1.
Subsection 1.4.2 Indexing
An enumeration of a finite set is an example of indexing. When we refer to “the indexed set \(S=\{s_1,s_2,\ldots,s_n\}\)”, we mean that there exists a one-to-one correspondence \(f\colon
\{1,2,\ldots,n\}\to S\) with the values \(s_k=f(k)\text{.}\) This allows us to enjoy the benefits of the enumeration without having to explicitly mention \(f\text{.}\) We say that \(s_k=f(k)\) is the \(k\)th element of \(S\) and we refer to \(k\) as the index of the element \(s_k\text{.}\) More generally, we may refer to any one-to-one correspondence \(f\colon \Lambda \to A\text{,}\) between any two sets \(\Lambda,A\) (finite or not) as an idexing. In this context, we may write \(a_\lambda=f(\lambda)\) and refer to \(\lambda\) as the index of the element \(a_\lambda
\in A\text{.}\)
Indexing is used in notation for unions and intersections of sets, and for sums and products of sets of numbers. Given an indexed set of sets \(\mathcal{U}=\{U_1,U_2,\ldots,U_n\}\text{,}\) we write \(\bigcup_{k=1}^n U_k\) to denote the union
\begin{equation*}
\bigcup_{k=1}^n U_k = U_1\cup U_2\cup \cdots \cup U_n
\end{equation*}
of all the elements in \(\mathcal{U}\text{.}\) Similarly, we write \(\bigcap_{k=1}^n U_k\) to denote the intersection
\begin{equation*}
\bigcap_{k=1}^n U_k = U_1\cap U_2\cap \cdots \cap U_n
\end{equation*}
of all the elements in \(\mathcal{U}\text{.}\) Given an indexed set of real numbers \(A=\{a_1,a_2,\ldots,a_n\}\text{,}\) we write \(\sum_{k=1}^n a_n\) to denote the sum
\begin{equation*}
\sum_{k=1}^n a_k = a_1+a_2+ \cdots + a_n
\end{equation*}
of all the elements in \(A\text{.}\) Similarly, we write \(\prod_{k=1}^n a_n\) to denote the product
\begin{equation*}
\prod_{k=1}^n a_k = a_1\cdot a_2\cdot \cdots \cdot a_n
\end{equation*}
of the elements in \(A\text{.}\)
It is often the case that the indexing of a set plays no particular role. For this reason, it is common to write
\begin{equation*}
\bigcup_{U\in \mathcal{U}}U,\;\; \bigcap_{U\in \mathcal{U}}U,\;\; \sum_{a\in A}a,\;\; \prod_{a\in A} a
\end{equation*}
to denote the union of all the sets in \(\mathcal{U}\text{,}\) the intersection of all the sets in \(\mathcal{U}\text{,}\) the sum of all the numbers in \(A\text{,}\) and the product of all the numbers in \(A\text{,}\) respectively.
Checkpoint 1.4.2.
-
Write\begin{equation*} [0,1)\cap [1/2,1/3) \cap \cdots \cap [1/17,1/18) \end{equation*}using indexed intersection notation.
-
Write\begin{equation*} 1+(1-1/2) + (1-3/4) + \cdots + (1-255/256) \end{equation*}using indexed summation notation. Write
-
Write\begin{equation*} 1\cdot 4\cdot 7\cdot \cdots \cdot 104 \end{equation*}using indexed product notation.
Subsection 1.4.3 Partitions
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.3.
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.4. 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.5.
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{?}\)
Proposition 1.4.6. 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.7. 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 1.4.4 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.4 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.
