In the course I am currently teaching, we discussed cardinalities of sets today in class. In this short post, I want to present the proofs that some sets of functions \(\mathbb{N} \rightarrow \mathbb{N}\) are uncountable.

The main ingredient for the proofs is the following theorem.

Theorem 1 (Cantor's theorem).

The set \([2]^{\mathbb{N}}\) is uncountable (here \([2] = \{0, 1\}\)).

We will now use this to prove that the sets of injective, surjective and bijective functions from \(\mathbb{N}\) to \(\mathbb{N}\) are uncountable. The idea in all three cases is to find an injection from \([2]^{\mathbb{N}}\) to the set of functions we are considering. The proof for injective functions I learned from Niels Vooijs.

Proposition 2.

The set of injective functions \(\mathbb{N} \rightarrow \mathbb{N}\) is uncountable.

Proof.

We will in fact prove that the set of strictly monotonically increasing functions from \(\mathbb{N}\) to \(\mathbb{N}\) is uncountable. The idea is the following: Given \(\chi \in [2]^{\mathbb{N}}\), if \(\chi(k) = 0\) then we increase the value of the associated injection by \(1\) compared to the previous value and if \(\chi(k) = 1\), then we increase the value by 2 compared to the previous value.

Define \(F\colon [2]^{\mathbb{N}} \rightarrow \mathrm{Inj}(\mathbb{N}, \mathbb{N})\) by

\begin{equation*} F(\chi) = k \mapsto k + \sum_{i = 0}^k \chi(k). \end{equation*}

We claim that \(F(\chi)\) is an injection. Let \(a, b \in \mathbb{N}\) and suppose \(F(\chi)(a) = F(\chi)(b)\). Without loss of generality, we may assume that \(a \le b\). Then we have

\begin{equation*} 0 = (b - a) + \sum_{i = a + 1}^b \chi(i). \end{equation*}

Since \(b - a \ge 0\) and \(\chi(i) \ge 0\) for all \(i \in \mathbb{N}\), it follows that \(b - a = 0\), hence \(a = b\). So \(F(\chi)\) is injective, and hence \(F\) is well-defined.

Now we claim that \(F\) is injective.1 Let \(\chi, \eta \in [2]^{\mathbb{N}}\) and suppose \(F(\chi) = F(\eta)\). Note that

\begin{equation*} F(\chi)(k + 1) - F(\chi)(k) - 1 = \left( k + 1 + \sum_{i = 0}^{k + 1} \chi(i) \right) - \left( k + 1 + \sum_{i = 0}^{k + 1} \chi(i) \right) - 1 = \chi(k + 1), \end{equation*}

so for \(k \ge 1\) it follows that

\begin{equation*} \chi(k) = F(\chi)(k) - F(\chi)(k - 1) - 1 = F(\eta)(k) - F(\eta)(k - 1) - 1 = \eta(k). \end{equation*}

For \(k = 0\) we have

\begin{equation*} \chi(0) = F(\chi)(0) = F(\eta)(0) = \eta(0). \end{equation*}

So indeed \(\chi = \eta\) and so \(F\) is injective.

Hence it follows that the set of injective functions \(\mathbb{N} \rightarrow \mathbb{N}\) is uncountable.

Next, we will tackle surjective functions, which is an alteration of the proof for injective functions. For this we cannot use all of \([2]^{\mathbb{N}}\) but only the uncountable subset \(U\) of those functions with \(\chi^{-1}[\{1\}]\) infinite.2

Proposition 3.

The set of surjective functions \(\mathbb{N} \rightarrow \mathbb{N}\) is uncountable.

Proof.

The idea is now to stay at the same value if \(\chi(k) = 0\) and to make a step forward if \(\chi(k) = 1\).

Define a function \(F\colon U \rightarrow \mathrm{Surj}(\mathbb{N}, \mathbb{N})\) by

\begin{equation*} F(\chi) = k \mapsto \sum_{i = 0}^{k - 1} \chi(i). \end{equation*}

We claim that \(F(\chi)\) is surjective for all \(\chi \in U\). Let \(n \in \mathbb{N}\). If \(n = 0\), then we have \(F(\chi)(0) = 0\), so in this case \(n\) is a value. Otherwise there is a \(k \in \mathbb{N}\) such that \(\sum_{i = 0}^{k - 1} \chi(i) = n\), since \(\chi^{-1}[\{1\}]\) is infinite.3 So in that case \(F(\chi)(k) = n\). So also if \(n \ge 1\), it is a value. So \(F(\chi)\) is indeed surjective.

Next, we show that \(F\) is injective. In this case we have for all \(k \in \mathbb{N}\) that

\begin{equation*} F(\chi)(k + 1) - F(\chi)(k) = \chi(k), \end{equation*}

so given \(\chi, \eta \in U\) such that \(F(\chi) = F(\eta)\), we see that for all \(k \in \mathbb{N}\)

\begin{equation*} \chi(k) = F(\chi)(k + 1) - F(\chi)(k) = F(\eta)(k + 1) - F(\eta)(k) = \eta(k). \end{equation*}

So \(\chi = \eta\), and so \(F\) is injective.

So we see that the set of all surjective functions \(\mathbb{N} \rightarrow \mathbb{N}\) is also uncountable.

Finally, we will show that the bijections \(\mathbb{N} \rightarrow \mathbb{N}\) is uncountable. The idea in this case is to use the function \(\chi\) to index swaps between even and odd numbers. In fact, in this case it is more natural to actually consider subsets of \(\mathbb{N}\), so this is what we will do.

Theorem 4.

The set of bijections \(\mathbb{N} \rightarrow \mathbb{N}\) is uncountable.

Proof.

Define a function \(F\colon \mathcal{P}(\mathbb{N}) \rightarrow \mathrm{Aut}(\mathbb{N})\) by

\begin{equation*} F(U)(x) = \begin{cases} 2k + 1 \quad & x = 2k \text{ and } k \in U \\ 2k \quad & x = 2k + 1 \text{ and } k \in U \\ x \quad & \text{otherwise} \end{cases}. \end{equation*}

The idea is to look at pairs of sequentially even and odd numbers and if \(k \in U\), then we swap the two numbers in the kth pair.

We claim that \(F(U)\) is a bijection. We will show that \(F(U)^2 = \mathrm{id}\). Let \(x \in \mathbb{N}\). Then either \(x = 2k\) or \(x = 2k + 1\) for some \(k \in \mathbb{N}\).

  • Case 1: Suppose \(x = 2k\). If \(k \not\in U\), then we have \(F(U)(x) = x\), hence \(F(U)^2(x) = x\). If \(k \in U\), then we have \(F(U)(x) = 2k + 1\) and we have \(F(U)(2k + 1) = 2k = x\).
  • Case 2: Suppose \(x = 2k + 1\). If \(k \not\in U\), then we have \(F(U)(x) = x\), hence \(F(U)^2(x) = x\). If \(k \in U\), then we have \(F(U)(x) = 2k\) and we have \(F(U)(2k) = 2k + 1 = x\).

So in all cases we have \(F(U)^2(x) = x\) and so \(F(U)\) is indeed a bijection.

We now show that \(F\) is injective. Let \(U, V \in \mathcal{P}(\mathbb{N})\) and suppose that \(F(U) = F(V)\). Let \(k \in U\). Then we have \(F(U)(2k) = 2k + 1\), hence \(F(V)(k) = 2k + 1\), but then we see from the definition that we must have \(k \in V\). So \(U \subset V\). The reverse inclusion follows by the same argument with the roles of \(U\) and \(V\) swapped. So \(U = V\) and therefore \(F\) is an injection.

So we conclude that the set of bijections \(\mathbb{N} \rightarrow \mathbb{N}\) is uncountable.

Footnotes:

1

Note that this is different from the previous injectivity claim. In the previous paragraph we were looking at one value of \(F\), which was again a function, and we showed that this function was injective. We are now going to prove that \(F\) as a function is injective.

2

That this is an uncountable set follows from the following facts: There is a bijection between the power set \(\mathcal{P}(\mathbb{N})\) and \([2]^{\mathbb{N}}\) under which this subset corresponds to the infinite subsets; and the set of all finite subsets of \(\mathbb{N}\) is countable.

3

In fact, we can explicitly describe this \(k\). This is precisely one plus the \(k\)th value \(\chi^{-1}[\{1\}]\) when ordered with the standard ordering from \(\mathbb{N}\).