Cantor's Theorem

set-theory

Definition

Cantor's Theorem

Every infinite set contains a countable subset and is thus, so to speak, “at least countable”.

Cantor showed, however, that the converse does not hold: not every infinite set is countable. There exists infinite sets that cannot be “exhausted” by a counting process.

Examples

Power Set of Natural Numbers

Goal: Show that the power set of the natural numbers $\mathcal{P}(\mathbb{N})$ is not countable. Equivalently: there is no surjective function $f:\mathbb{N}\to \mathcal{P}(\mathbb{N})$.

Proof: Let $f:\mathbb{N}\to \mathcal{P}(N)$ be a function that attempts to list all subsets of $\mathbb{N}$:

$$f(1),f(2),f(3),\dots$$

with $\forall n\in \mathbb{N}:f(n)\subseteq \mathbb{N}$.

Let $A:=\{n\in \mathbb{N}\mid n\notin f(n)\}$. This is a well-defined and clearly a subset of $\mathbb{N}$, therefore $A\in \mathcal{P}(\mathbb{N})$.

Intuition

$A$ is built by “flipping the diagonal” decision for each $n$:

• If $n$ lies in the $n$-th listed set $f(n)$, then we exclude it from $A$.
• If it does not lie in $f(n)$, we include it in $A$.

In other words, $A$ is the set of all natural numbers than cannot generate a set containing themselves using themselves.

Suppose $A$ appears as an image for an $n_0\in \mathbb{N}$. Is $n_0\in A$?

By definition of $A$:

$$n_0\in A⟺n_0\notin f(n_0)$$

But if $A=f(n_0)$, a contradiction emerges:

$$n_0\in A⟺n_0\notin A$$

Therefore, there cannot be an $n_0\in \mathbb{N}$ s.t. $A=f(n_0)$.

Conclusion: Thus, $A$ is not in the image of $f$, i.e. $A\notin f[\mathbb{N}]$. Since $f$ was an arbitrary listing attempt, no function from $\mathbb{N}\to \mathcal{P}(\mathbb{N})$ can hit every subset. Therefore, $\mathcal{P}(\mathbb{N})$ is uncountable.

To illustrate, let’s pick a concrete $f$. Given that the set $A\notin f[\mathbb{N}]$, a diagonal emerges:

$$\begin{array}{rcllllllllllll}f(0)& =& \{& 0,& 1,& 2,& 3,& 4,& 5,& 6,& 7,& 8,& \dots & \}=\mathbb{N}\\ f(1)& =& \{& & \underline{},& & & & & & & & \dots & \}\\ f(2)& =& \{& & 1,& \underline{},& 3,& & 5,& & 7,& & \dots & \}\\ f(3)& =& \{& & & 2,& 3,& & 5,& & 7,& & \dots & \}\\ f(4)& =& \{& 0,& & 2,& & 4,& & 6,& & 8,& \dots & \}\\ ⋮& & & & & & & & & & & & & \end{array}$$

This diagonal, which is definitely not a subset of the co-domain of $f$, is $A$. Trivially, $A\ne f(0)$ since $0\in f(0)$, $A\ne f(1)$, etc.