Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 12.2 Properties of finite sets and their cardinality

Subsection 12.2.1 Finite sets versus finite sequences

Recall that a function \(\funcdef{f}{\natnumlt{n}}{A}\) defines a finite sequence of elements from the set \(A\text{,}\) by setting
\begin{align*} a_0 \amp = f(0), \amp a_1 \amp = f(1), \amp a_2 \amp = f(2), \amp \amp \dotsc, \amp a_{n-1} \amp = f(n-1)\text{.} \end{align*}
If \(A\) is finite, then there exists such a function \(f\) that is bijective, which leads to the following.

Remark 12.2.2.

  1. The above fact makes an important connection between functions and counting. If \(A\) is a finite set, \(\funcdef{f}{\natnumlt{n}}{A}\) is a corresponding bijection, and we create sequence \(\{a_k\}_{k=0}^m\) with \(a_k = f(k)\) as above, then we are able to list the elements of \(A\) in sequence:
    \begin{equation*} A = \{a_0, a_1, \dotsc, a_{n-1} \} \text{.} \end{equation*}
    In turn, writing the elements of \(A\) in sequence is really just a way of counting them, in a manner that is roughly equivalent to counting on your fingers (if you had a lot of fingers). In fact, counting the elements of \(A\) totally orders the elements of \(A\) (a concept we will meet in a future chapter). In Chapter 13, we will adapt this connection between functions and counting to determine whether it is possible to “count” infinite sets.
  2. We should note, however, that the above fact is essentially trivial once we “unravel” the definitions of finite set and finite sequence, as both involve a function with domain \(\natnumlt{m}\) for some \(m\) and codomain \(A\text{.}\)
If we have a sequence that contains each element of \(A\) at least once, we could turn it into a sequence that contains each element of \(A\) exactly once by removing repeated terms.

Subsection 12.2.2 Finite sets versus bijections, subsets, and unions

Bijections compose to create bijections (see Exercise 10.7.13). This fact lets us relate finite sets to each other.
Reconsider “one of \(A,B\) finite” as a disjunction: “\(A\) is finite or \(B\) is finite”. Then break into cases.
Assume \(A\) is finite.
Suppose \(\card{A} = n\text{,}\) so that there exists a bijection \(\funcdef{g}{\natnumlt{n}}{A}\text{.}\) Then \(\funcdef{f\circ g}{\natnumlt{n}}{B}\) is also a bijection, so \(\card{B} = n\text{.}\)
Assume \(B\) is finite.
Suppose \(\card{B} = n\text{.}\) Repeat the argument from the previous case, swapping roles of \(A\) and \(B\) and using the bijection \(\funcdef{\inv{f}}{B}{A}\) in place of \(f\text{.}\)
We may also relate cardinality of finite sets to the union operation.
The idea behind these formulas should be obvious once you draw appropriate Venn diagrams, but formal proofs are left to you in Exercise 12.6.2.

Subsection 12.2.3 Cardinality of power sets of finite sets

Worked Example 12.2.7.

What is the cardinality of \(\powset{\{1,2,3,\dotsc,k\}}\text{?}\)
Solution.
We can solve this using recursion! In Example 11.2.4, we defined the following sequence of subsets of \(\N\text{,}\)
\begin{gather*} A_0 = \emptyset, \quad A_1 = \{1\}, \quad A_2 = \{1,2\}, \quad A_3 = \{1,2,3\},\\ \dotsc, \quad A_k = \{1, 2, \dotsc, k \}, \quad \dotsc\text{,} \end{gather*}
recursively. We can also express the sequence \(N_k = \card{\powset{A_k}}\) recursively. First, \(N_0 = 1\text{.}\) Then, since
\begin{equation*} A_{k-1} = \{ 1, 2, \dotsc, k-1 \} \subsetneqq \{1,2,\dotsc,k-1,k\} = A_k, \end{equation*}
we can consider \(\powset{A_{k-1}} \subseteq \powset{A_k}\text{.}\) (See Exercise 9.9.13.) In doing so, we can break \(\powset{A_k}\) into the disjoint union
\begin{equation*} \powset{A_k} = \powset{A_{k-1}} \sqcup \cmplmnt{\powset{A_{k-1}}}. \end{equation*}
Notice that the elements of \(\powset{A_{k-1}}\) are precisely those subsets of \(A_k\) that do not contain the element \(k\text{,}\) and therefore the elements of \(\cmplmnt{\powset{A_{k-1}}}\) are precisely those subsets of \(A_k\) that do contain the element \(k\text{.}\) So
\begin{equation*} B \in \powset{A_{k-1}} \quad \lgcimplies \quad B \cup \{k\} \in \cmplmnt{\powset{A_{k-1}}} \text{.} \end{equation*}
This correspondence actually gives us a bijection
\begin{align*} \powset{A_{k-1}} \amp \to \cmplmnt{\powset{A_{k-1}}}, \\ B \amp \mapsto B \cup \{k\}. \end{align*}
(Check!)
Now we have
\begin{equation*} N_{k-1} = \card{\powset{A_{k-1}}} = \card{\cmplmnt{\powset{A_{k-1}}}} \text{.} \end{equation*}
Since
\begin{equation*} \powset{A_k} = \powset{A_{k-1}} \sqcup \cmplmnt{\powset{A_{k-1}}} \text{,} \end{equation*}
we then have
\begin{equation*} N_k = N_{k-1} + N_{k-1} = 2 N_{k-1} \text{,} \end{equation*}
a recursively defined sequence. Solving this recurrence relation by iteration yields
\begin{equation*} N_k = 2^k \text{.} \end{equation*}

Checkpoint 12.2.8.

Verify that the map
\begin{align*} \powset{A_{k-1}} \amp \to \cmplmnt{\powset{A_{k-1}}}, \\ B \amp \mapsto B \cup \{k\}. \end{align*}
in the solution to the preceding Worked Example is a bijection.
We can use the idea of Worked Example 12.2.7 to prove a similar but more general fact.
Since \(A\) has the same cardinality as the set \(\{1,2,3,\dots,n\}\text{,}\) there exists a bijection between the two sets. In Exercise 12.6.8, you are asked to prove that two sets of the same cardinality also have power sets of the same cardinality. Using this fact and the result of Worked Example 12.2.7, we have
\begin{equation*} \card{\powset{A}} = \card{\powset{\{1,2,3,\dots,n\}}} = 2^n \text{.} \end{equation*}

Subsection 12.2.4 Infinite sets

infinite set
a set that is not finite
\(\card{A} = \infty\)
set \(A\) is infinite
\(\card{A} \lt \infty\)
set \(A\) is finite
To demonstrate that a set \(A\) is infinite using the technical definition, we must demonstrate that no bijection \(\natnumlt{m} \to A\) can exist, for every cardinality value \(m\text{.}\) But if \(A\) is infinite, there will be many injective functions \(\natnumlt{m} \ifuncto A\) for each \(m\text{.}\) Therefore, one must demonstrate that no surjection \(\natnumlt{m} \sfuncto A\) can exist, for every \(m\text{.}\)

Example 12.2.10. Demonstrating that a set is infinite from the definition.

Suppose we have an alphabet consisting of a single letter \(\Sigma = \{\mathrm{x}\}\text{.}\) Then the set of words
\begin{equation*} \words{\Sigma} = \{x,\, xx,\, xxx,\, \dotsc \} \end{equation*}
is infinite.
To verify this, we will argue that no function \(\natnumlt{m} \to \words{\Sigma}\) can be surjective, no matter the cardinality value \(m\text{.}\) So suppose \(m \in \N\) is fixed but arbitrary, and \(\funcdef{f}{\natnumlt{m}}{\words{\Sigma}}\) is an arbitrary function. Following the Test for Surjectivity (which also describes how to demonstrate that a function is not surjective), we must exhibit an example element in \(\words{\Sigma}\) that is not the image under \(f\) of any domain element in \(\natnumlt{m}\text{.}\)
Function \(f\) defines a finite sequence of words from \(\words{\Sigma}\text{:}\)
\begin{equation*} w_0, w_1, w_2, \dotsc, w_{m-1}, \end{equation*}
where each \(w_j\) is the image \(f(j)\text{.}\) We have two cases.
Each \(w_j\) is the empty word.
In this case, clearly \(f\) cannot be surjective since the word consisting of the single letter \(x\) is not in the sequence of outputs for \(f\text{.}\)
Otherwise.
In this case, consider the word we get by concatenating the words \(w_0, w_1, \dotsc, w_{m-1}\) together twice over:
\begin{equation*} w = w_0 w_1 w_2 \dotsm w_{m-1} w_0 w_1 w_2 \dotsm w_{m-1} \text{.} \end{equation*}
(Note that this is not multiplication, we are just writing the words one after the other to create one big word.) Then this word is certainly longer than any of the individual words \(w_j\text{,}\) and so cannot be equal to one of those words. (The reason we have concatenated all the \(w_j\) twice over is so that we don’t have to separately consider the case that all but one of the \(w_j\) is empty, since in that case concatenating all the \(w_j\) just once over wouldn’t actually produce a result that is longer than that one non-empty \(w_j\text{.}\)) Since this long word is not in the sequence of image elements for \(f\text{,}\) the function \(f\) cannot be surjective.

Remark 12.2.11.

While we have no hope of demonstrating that a set \(A\) is infinite by demonstrating that functions \(\natnumlt{m} \to A\) cannot be injective, if we wish we can argue using injectivity by just turning things around. If a bijection \(\natnumlt{m} \to A\) were possible, its inverse \(A \to \natnumlt{m}\) would also be a bijection. So another way to demonstrate that a set \(A\) is infinite is to demonstrate that no injection \(A \to \natnumlt{m}\) is possible, for every cardinality number \(m\text{.}\)
We can also demonstrate that a set is infinite by relating it to known infinite sets.

Worked Example 12.2.13.

Show that if \(\Sigma \ne \emptyset\text{,}\) then \(\card{\words{\Sigma}} = \infty\text{,}\) regardless of whether \(\card{\Sigma} \lt \infty\) or \(\card{\Sigma} = \infty\text{.}\)
Solution.
If \(\Sigma \ne \emptyset\text{,}\) then there exists some \(x \in \Sigma\text{.}\) Consider the restricted alphabet \(\Xi = \{x\}\text{.}\) In Example 12.2.10, we demonstrated that \(\words{\Xi}\) was infinite. Clearly \(\Xi \subseteq \Sigma\) implies \(\words{\Xi} \subseteq \words{\Sigma}\text{,}\) so applying Statement 1 of Fact 12.2.12 we may conclude that \(\words{\Sigma}\) is also infinite.
<Prev^TopNext>