Cantor's Theorem

Prove Cantor's theorem completely: for every set $X$ , $\lvert X \rvert < \lvert\mathcal{P}(X) \rvert$ . Get $\le$ from the injection $x \mapsto \{x\}$ , and rule out any surjection with the diagonal set $D = \{x : x \notin f(x)\}$ .

D = \{x \in X : x \notin f(x)\}, \qquad y \in D \iff y \notin f(y)

\lvert X \rvert \le \lvert\mathcal{P}(X)\rvert \ \text{ via } \ x \mapsto \{x\}, \qquad \lvert X \rvert \ne \lvert\mathcal{P}(X)\rvert \ \text{(no surjection)}

n = 5

: the flipped row

11111

sits below the 5 listed rows and differs from row

i

at column

i

— the finite version of the proof below.

Show proof

$\lvert X \rvert \le \lvert\mathcal{P}(X)\rvert$ comes from the injection $\iota: X \to \mathcal{P}(X)$ , $\iota(x) = \{x\}$ : if $\{x\} = \{y\}$ then $x = y$ , so $\iota$ is injective. (For $X = \varnothing$ the empty map is injective.)
Now we show no $f: X \to \mathcal{P}(X)$ is surjective. Form the diagonal set $D = \{x \in X : x \notin f(x)\}$ ( $D \subseteq X$ , so $D \in \mathcal{P}(X)$ ). If $f$ were surjective, some $y \in X$ would satisfy $D = f(y)$ .
For that $y$ : $y \in D$ is equivalent by definition to $y \notin f(y)$ , and since $f(y) = D$ , this is equivalent to $y \notin D$ . So $y \in D \iff y \notin D$ — a contradiction. Hence no such $y$ exists, $D$ is not in the range of $f$ , and $f$ is not surjective.
If $\lvert X \rvert = \lvert\mathcal{P}(X)\rvert$ there would be a bijection, hence in particular a surjection — contradicting the above. So $\lvert X \rvert \ne \lvert\mathcal{P}(X)\rvert$ , and together with $\le$ from the first step, $\lvert X \rvert < \lvert\mathcal{P}(X)\rvert$ . QED.

Prove $(0,1)$ is uncountable, completely: assume an enumeration, write out decimal expansions, and build a diagonal number $y$ whose $n$ -th digit differs from the $n$ -th digit of the $n$ -th number while avoiding the digits $0$ and $9$ (to dodge the $0.0999\ldots = 0.1000\ldots$ ambiguity).

y = 0.e_1 e_2 \cdots, \qquad e_n = \begin{cases} 4 & d_{nn} = 5 \\ 5 & d_{nn} \ne 5 \end{cases}

e_n \ne d_{nn}, \quad e_n \notin \{0, 9\}, \quad y \in (0,1), \quad y \ne x_n \ \forall n

n = 5

: just as 5 rows cannot exhaust the

2^5 = 32

possible rows, no enumeration of

(0,1)

can catch the diagonal number.

Show proof

Assume $(0,1)$ is countable and fix an enumeration $x_1, x_2, \ldots$ . Write each $x_n$ in decimal as $x_n = 0.d_{n1}d_{n2}\cdots$ ( $d_{nk} \in \{0,\ldots,9\}$ ).
Define the diagonal number $y = 0.e_1 e_2 \cdots$ by $e_n = 4$ if $d_{nn} = 5$ , else $e_n = 5$ . Then $e_n \ne d_{nn}$ for every $n$ , and $e_n \in \{4, 5\}$ , so the digits $0$ and $9$ never occur.
$y \in (0,1)$ : $0.444\ldots \le y \le 0.555\ldots$ . If $y = x_n$ , then since the decimal expansion of $y$ contains no $0$ or $9$ , it cannot have an alternative expansion — two decimal expansions of the same number can differ only when one ends in infinite $0$ s and the other in infinite $9$ s — so the expansion of $y$ is unique. Hence the $n$ -th digit of $x_n$ must be $e_n$ , contradicting $e_n \ne d_{nn}$ .
So $y$ differs from every $x_n$ , contradicting the claim that the enumeration covers $(0,1)$ . Hence $(0,1)$ is not countable: it is uncountable. QED.

For finite $\lvert X \rvert = n$ , prove $\lvert\mathcal{P}(X)\rvert = 2^n > n$ completely by induction. Connect it to the picture above: only $n$ of the $2^n$ possible rows are listed in the $n \times n$ table.

\mathcal{P}(X) = \mathcal{P}(X') \;\sqcup\; \{A \cup \{x_0\} : A \in \mathcal{P}(X')\}, \qquad \lvert\mathcal{P}(X)\rvert = 2\,\lvert\mathcal{P}(X')\rvert

\lvert\mathcal{P}(X)\rvert = 2^n > n \qquad (n \ge 0)

n = 5

: there are

2^5 = 32

possible 0/1 rows but only 5 are listed — the flipped row being off the list is inevitable.

Show proof

We prove $\lvert\mathcal{P}(X)\rvert = 2^n$ for $\lvert X \rvert = n$ by induction on $n$ . Base $n = 0$ : $X = \varnothing$ and $\mathcal{P}(\varnothing) = \{\varnothing\}$ , so $\lvert\mathcal{P}(X)\rvert = 1 = 2^0$ .
Inductive step: let $\lvert X \rvert = n+1$ , pick $x_0 \in X$ and put $X' = X \setminus \{x_0\}$ . Subsets of $X$ either contain $x_0$ or not, so $\mathcal{P}(X) = \mathcal{P}(X') \;\sqcup\; \{A \cup \{x_0\} : A \in \mathcal{P}(X')\}$ (disjoint union). Hence $\lvert\mathcal{P}(X)\rvert = 2\,\lvert\mathcal{P}(X')\rvert = 2 \cdot 2^n = 2^{n+1}$ by the induction hypothesis.
Also $2^n > n$ ( $n \ge 0$ ) by induction: $1 > 0$ at $n = 0$ ; if $2^n > n$ then $2^{n+1} = 2 \cdot 2^n > 2n \ge n+1$ (for $n \ge 1$ ; check $n = 0$ directly). So $\lvert\mathcal{P}(X)\rvert = 2^n > n = \lvert X \rvert$ .
Connection to the picture: subsets of $X = \{0,\ldots,n-1\}$ correspond bijectively to the $2^n$ binary rows. The $n \times n$ table lists only $n$ of them, and since $2^n > n$ some row is necessarily missing — flipping the diagonal explicitly constructs one. This is the finite version of Cantor's theorem.

Examples & Exercises