Skip to main content

Section 2.4 Cardinalities of finite sets

Definition 2.4.1.

Let \(X\) and \(Y\) be two sets. We will say that \(X\) and \(Y\) are equinumerous if and only if there exists a bijection \(X \to Y \text{.}\) In this case we shall write \(|X|=|Y|\text{.}\)

We've done something sort of funny here. Rather than actually define the cardinality or size of a set \(X\) as a number \(|X|\text{,}\) we've instead identified the situation in which the cardinalities of different sets should be equal.

For a finite set \(X\text{,}\) it is possible to describe the size of \(X\) as a natural number. In order to explain this, we first need to show that equinumerous natural numbers are in fact equal.

Recall that we've defined the natural numbers so that if \(n \in \NN_0\text{,}\) then \(n=\{0,1,\dots,n-1\}\text{.}\) Now let us relate our discussion of injections and surjections to these particular sets.

Warning 2.4.3.
This proof is a little technical. It's not critical that you understand this proof entirely, but it is important to understand the significance of the result!

  1. Let us prove the first claim by induction on \(m\text{.}\) If \(m=0\text{,}\) then no matter what \(n\) is, \(m \leq n\text{.}\) Now let \(m\in\NN_0\text{,}\) and assume that for any \(n \in \NN_0\text{,}\) if there exists an injective map \(f \colon m \to n\text{,}\) then \(m \leq n\text{.}\) We now aim to show that for any \(n\in \NN_0\text{,}\) if there exists an injective map \(f \colon m+1 \to n\text{,}\) then \(m+1 \leq n\text{.}\) So let \(n \NN_0\text{,}\) and let \(f \colon m+1 \to n\) be an injective map. Note that \(n\neq 0\text{;}\) indeed, if \(n=0\text{,}\) then \(m+1 = 0 \text{,}\) which is impossible since \(0\) is not a successor of any natural number. Thus \(n \in \NN\text{.}\) Now let \(k = f(m) \in n\text{.}\) Note that since \(f \) is an injection, it follows that there is no element \(i \in m-1\) such that \(f(i)=k\text{.}\) Hence we may define a map \(g \colon m \to n-1\) as follows: for any \(i \in m\text{,}\) let

    \begin{equation*} g(i) = \begin{cases} f(i) \amp \text{ if } f(i)\lt k;\\ f(i)-1 \amp \text{ if } f(i)\gt k. \end{cases} \end{equation*}

    The map \(g\) is again an injection. (Confirm this!) Now by our induction hypothesis, it follows that \(m \leq n-1\text{,}\) whence it follows that \(m+1 \leq n\text{,}\) as desired.

  2. For the second statement, we'll again proceed by induction, but this time on \(n\text{.}\) If \(n=0\text{,}\) then no matter what \(m\) is, \(m \geq n\text{.}\) Now let \(n\in\NN_0\text{,}\) and assume that for any \(m \in \NN_0\text{,}\) if there exists a surjective map \(f \colon m \to n\text{,}\) then \(m \geq n\text{.}\) We now aim to show that for any \(m\in \NN_0\text{,}\) if there exists an injective map \(f \colon m \to n+1\text{,}\) then \(m \geq n+1\text{.}\) So let \(m \NN_0\text{,}\) and let \(f \colon m \to n+1\) be an surjective map. Note that \(m\neq 0\text{;}\) indeed, if \(m=0\text{,}\) then since \(f\) is surjective, it follows that \(n+1 = 0 \text{,}\) which is impossible since \(0\) is not a successor of any natural number. Thus \(m \in \NN\text{.}\) Now let \(k \in m\) be an element such that \(f(k)=n\text{;}\) such an element exists since \(f\) is surjective. Now we may define a map \(g \colon m-1 \to n\) as follows: for any \(i \in m-1\text{,}\) let

    \begin{equation*} g(i) = \begin{cases} f(i) \amp \text{ if } i\lt k \text{ and }f(i)\neq n;\\ f(i+1) \amp \text{ if } i\gt k \text{ and }f(i)\neq n;\\ f(k+1) \amp \text{ if } f(i)=n. \end{cases} \end{equation*}

    The map \(f\) is again a surjection. (Again, confirm this!) Now by our induction hypothesis, it follows that \(m \leq n-1\text{,}\) whence it follows that \(m+1 \leq n\text{,}\) as desired.

  3. This is immediate from the first two parts.

An immediate consequence of this is that natural numbers \(m\) and \(n\) are equinumerous if and only if they are equal. That goes some way to justifying the term “equinumerous”.

Definition 2.4.4.

Let \(S\) be a set, and let \(n\) be a natural number. We will say that \(S\) has cardinality \(n\) if and only if \(S\) and \(n\) are equinumerous; in this case, we will write (somewhat sloppily) \(|S|=n\text{.}\) We say that \(S\) is finite if and only if there exist a natural number \(n\) such that \(S\) has cardinality \(n\text{.}\)

This is the mathematically precise version of counting. If \(X\) is a finite set of cardinality \(n\text{,}\) then a choice of bijection \(x\colon n \to X\) permits us to write

\begin{equation*} X = \{x(0), x(1), \dots, x(n-1)\}\text{,} \end{equation*}

or, reindexing by writing \(x_i = x(i-1)\text{,}\)

\begin{equation*} X = \{x_1, x_2, \dots, x_n\} \end{equation*}

Now we can state with confidence some quite natural facts about cardinality. For instance, let \(X\) and \(Y\) be two finite sets that are disjoint — that is, such that \(X \cap Y = \varnothing\text{.}\) Then we have a formula: \(|X \cup Y| = |X|+|Y|\text{.}\) In words,

The cardinality of a disjoint union of two sets is the sum of the cardinalities of these sets.

Note that maps between sets can help us count: let \(f \colon X \to Y\) be a map between finite sets. If \(f\) is an injection, then \(|X| \leq |Y|\text{,}\) and if \(f\) is a surjection, then \(|X|\geq |Y|\text{.}\) In the next section we will prove a more precise version of this fact.