12.2: Properties of finite sets and their cardinality

Finite sets versus finite sequences

Recall that a function \(f: \mathbb{N}_{<n} \rightarrow A\) defines a finite sequence of elements from the set \(A\text{,}\) by setting

\begin{align*} a_0 & = f(0), & a_1 & = f(1), & a_2 & = f(2), & & \ldots, & a_{n-1} & = 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.

Fact \(\PageIndex{1}\): Characterization of finiteness using sequences

A set \(A\) is finite if and only if there exists a finite sequence from \(A\) in which each element of \(A\) appears exactly once.

Remark \(\PageIndex{1}\)

1. The above fact makes an important connection between functions and counting. If \(A\) is a finite set, \(f: \mathbb{N}_{<n} \rightarrow 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, \ldots, 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 \(\mathbb{N}_{<m}\) for some \(m\) and codomain \(A\text{.}\)

Corollary \(\PageIndex{1}\)

A set \(A\) is finite if and only if there exists a finite sequence from \(A\) which contains each element of \(A\) at least once.

Proof Idea

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.

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.

Fact \(\PageIndex{2}\): Bijection implies same cardinality.

If one of \(A,B\) is finite and there exists a bijection \(f: A\rightarrow B\text{,}\) then both are finite and \(\vert A \vert = \vert B \vert\text{.}\)

Proof Idea.

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 \(\vert A \vert = n\text{,}\) so that there exists a bijection \(g: \mathbb{N}_{<n}\rightarrow A\text{.}\) Then \(f\circ g: \mathbb{N}_{<n} \rightarrow B\) is also a bijection, so \(\vert B \vert = n\text{.}\)

Assume \(B\) is finite.
Suppose \(\vert B \vert = n\text{.}\) Repeat the argument from the previous case, swapping roles of \(A\) and \(B\) and using the bijection \(f^{-1} : B \rightarrow A\) in place of \(f\text{.}\)

Fact \(\PageIndex{3}\): Subset of finite is finite

Assume \(B\) is a finite set.

1. Every subset \(A \subseteq B\) is finite, with \(\vert A \vert \le \vert B \vert\text{.}\)
2. If \(f: C \rightarrow B\) is an injection, then \(C\) is finite with \(\vert C \vert \le \vert B \vert\text{.}\)

Proof Idea.

1. This is left to you as Exercise 12.6.1.
2. Let \(A\) represent the image \(f(C)\text{.}\) Then \(A \subseteq B\text{,}\) so we can apply Statement 1 and Fact \(\PageIndex{2}\).

​​​​​We may also relate cardinality of finite sets to the union operation.

Fact \(\PageIndex{4}\): Cardinality of Unions

Suppose \(A\) and \(B\) are finite subsets of a universal set \(U\text{.}\)

If \(A\) and \(B\) are disjoint, then \(\vert A \sqcup B \vert = \vert A \vert + \vert B \vert\text{.}\)

\(\vert A \cup B \vert = \vert A \vert + \vert B \vert - \vert A \cap B \vert\text{.}\)

Proof Idea.

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.

Cardinality of power sets of finite sets

Example \(\PageIndex{1}\)

What is the cardinality of \(\mathscr{P}(\{1,2,3,\ldots,k\})\text{?}\)

Solution

We can solve this using recursion! In Example 11.2.4, we defined the following sequence of subsets of \(\mathbb{N}\text{,}\)

\begin{gather*} A_0 = \varnothing, \quad A_1 = \{1\}, \quad A_2 = \{1,2\}, \quad A_3 = \{1,2,3\},\\ \ldots, \quad A_k = \{1, 2, \ldots, k \}, \quad \ldots\text{,} \end{gather*}
recursively. We can also express the sequence \(N_k = \vert \mathscr{P}(A_k) \vert\) recursively. First, \(N_0 = 1\text{.}\) Then, since

\begin{equation*} A_{k-1} = \{ 1, 2, \ldots, k-1 \} \subsetneqq \{1,2,\ldots,k-1,k\} = A_k, \end{equation*}
we can consider \(\mathscr{P}(A_{k-1}) \subseteq \mathscr{P}(A_k)\text{.}\) (See Exercise 9.9.13.) In doing so, we can break \(\mathscr{P}(A_k)\) into the disjoint union

\begin{equation*} \mathscr{P}(A_k) = \mathscr{P}(A_{k-1}) \sqcup \mathscr{P}(A_{k-1})^c. \end{equation*}
Notice that the elements of \(\mathscr{P}(A_{k-1})\) are precisely those subsets of \(A_k\) that do not contain the element \(k\text{,}\) and therefore the elements of \(\mathscr{P}(A_{k-1})^c\) are precisely those subsets of \(A_k\) that do contain the element \(k\text{.}\) So

\begin{equation*} B \in \mathscr{P}(A_{k-1}) \quad \Rightarrow \quad B \cup \{k\} \in \mathscr{P}(A_{k-1})^c \text{.} \end{equation*}
This correspondence actually gives us a bijection

\begin{align*} \mathscr{P}(A_{k-1}) & \to \mathscr{P}(A_{k-1})^c, \\ B & \mapsto B \cup \{k\}. \end{align*}
(Check!)

Now we have

\begin{equation*} N_{k-1} = \vert \mathscr{P}(A_{k-1}) \vert = \vert \mathscr{P}(A_{k-1})^c \vert \text{.} \end{equation*}
Since

\begin{equation*} \mathscr{P}(A_k) = \mathscr{P}(A_{k-1}) \sqcup \mathscr{P}(A_{k-1})^c \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 \(\PageIndex{1}\)

Verify that the map

\begin{align*} \mathscr{P}(A_{k-1}) & \to \mathscr{P}(A_{k-1})^c, \\ B & \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 \(\PageIndex{1}\) to prove a similar but more general fact.

Theorem \(\PageIndex{1}\): Cardinality of a power set.

If \(\vert A \vert = n\text{,}\) then \(\vert \mathscr{P}(A) \vert = 2^n\text{.}\)

Proof Idea.

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 \(\PageIndex{1}\), we have

\begin{equation*} \vert \mathscr{P}(A) \vert = \vert \mathscr{P}(\{1,2,3,\dots,n\}) \vert = 2^n \text{.} \end{equation*}

Infinite sets

 

Definition: Infinite Set

a set that is not finite

Definition: \(\vert A \vert = \infty\)

set \(A\) is infinite

Definition: \(\vert A \vert \lt \infty\)

set \(A\) is finite

To demonstrate that a set \(A\) is infinite using the technical definition, we must demonstrate that no bijection \(\mathbb{N}_{<m} \to A\) can exist, for every cardinality value \(m\text{.}\) But if \(A\) is infinite, there will be many injective functions \(\mathbb{N}_{<m} \hookrightarrow A\) for each \(m\text{.}\) Therefore, one must demonstrate that no surjection \(\mathbb{N}_{<m} \twoheadrightarrow A\) can exist, for every \(m\text{.}\)

Example \(\PageIndex{2}\): Demonstrating that a set is infinite from the definition.

Suppose we have an alphabet consisting of a single letter \(\Sigma = \{\text{x}\}\text{.}\) Then the set of words

\begin{equation*} \Sigma^{\ast} = \{x,\, xx,\, xxx,\, \ldots \} \end{equation*}
is infinite.

To verify this, we will argue that no function \(\mathbb{N}_{<m} \to \Sigma^{\ast}\) can be surjective, no matter the cardinality value \(m\text{.}\) So suppose \(m \in \mathbb{N}\) is fixed but arbitrary, and \(f: \mathbb{N}_{<m} \rightarrow \Sigma^{\ast}\) 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 \(\Sigma^{\ast}\) that is not the image under \(f\) of any domain element in \(\mathbb{N}_{<m}\text{.}\)

Function \(f\) defines a finite sequence of words from \(\Sigma^{\ast}\text{:}\)

\begin{equation*} w_0, w_1, w_2, \ldots, 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, \ldots, w_{m-1}\) together twice over:

\begin{equation*} w = w_0 w_1 w_2 \cdots w_{m-1} w_0 w_1 w_2 \cdots 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 \(\PageIndex{2}\)

While we have no hope of demonstrating that a set \(A\) is infinite by demonstrating that functions \(\mathbb{N}_{<m} \to A\) cannot be injective, if we wish we can argue using injectivity by just turning things around. If a bijection \(\mathbb{N}_{<m} \to A\) were possible, its inverse \(A \to \mathbb{N}_{<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 \mathbb{N}_{<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.

Fact \(\PageIndex{5}\): Contains infinite subset implies infinite.

Assume \(A\) is an infinite set.

1. Every set \(B\) that contains \(A\) as a subset (i.e. \(B \supseteq A\)) is infinite.
2. If \(f: A\rightarrow B\) is an injection, then \(B\) is also infinite.

Proof.

1. This is left to you as Exercise 12.6.4.
2. This is just the contrapositive of Statement 2 of Fact \(\PageIndex{3}\).

Example \(\PageIndex{3}\)

Show that if \(\Sigma \ne \varnothing\text{,}\) then \(\vert \Sigma^{\ast} \vert = \infty\text{,}\) regardless of whether \(\vert \Sigma \vert \lt \infty\) or \(\vert \Sigma \vert = \infty\text{.}\)

Solution

If \(\Sigma \ne \varnothing\text{,}\) then there exists some \(x \in \Sigma\text{.}\) Consider the restricted alphabet \(\Xi = \{x\}\text{.}\) In Example \(\PageIndex{2}\), we demonstrated that \(\Xi^{\ast}\) was infinite. Clearly \(\Xi \subseteq \Sigma\) implies \(\Xi^{\ast} \subseteq \Sigma^{\ast}\text{,}\) so applying Statement 1 of Fact \(\PageIndex{5}\) we may conclude that \(\Sigma^{\ast}\) is also infinite.