Diagonalisation and Cantor's Theorem

Cantor’s Theorem

Statement

Theorem (Cantor, 1891): For any set $A$, there is no surjection $A \twoheadrightarrow \mathcal{P}(A)$.

Corollary

$|\mathcal{P}(A)| > |A|$ for every set $A$.

In particular, there are different sizes of infinity.

Examinable Proof (Diagonalisation)

Setup

Suppose $e : A \twoheadrightarrow \mathcal{P}(A)$ is surjective.

The Diagonal Set

Define $U \subseteq A$ by:

$U = \{x \in A : x \notin e(x)\}$

This is the set of all elements that are not members of the set they’re mapped to.

Contradiction

Since $e$ is surjective, there exists $a \in A$ with $e(a) = U$.

Question: Is $a \in U$?

• If $a \in U$: Then $a \notin e(a) = U$. Contradiction.
• If $a \notin U$: Then $a \in e(a) = U$ (by definition of $U$). Contradiction.

Either way, contradiction. Therefore no such surjection exists.

Visualisation

Consider $A = \mathbb{N}$. If $e : \mathbb{N} \to \mathcal{P}(\mathbb{N})$ enumerated all subsets:

$n$	$e(n) \subseteq \mathbb{N}$	$n \in e(n)$?
0	$\{1, 2, 3, \ldots\}$	No
1	$\{0, 2, 4, \ldots\}$	No
2	$\{0, 1, 3, \ldots\}$	Yes
3	$\{3\}$	Yes
$\vdots$	$\vdots$	$\vdots$

The diagonal $U$ “flips” the membership on the diagonal. $U$ differs from every row, so cannot appear.

Immediate Consequences

Uncountability of $\mathbb{R}$

$\mathbb{R} \cong \mathcal{P}(\mathbb{N})$ via binary expansions.

Since $\mathcal{P}(\mathbb{N})$ is uncountable, $\mathbb{R}$ is uncountable.

No Largest Cardinality

Given any set $A$, the set $\mathcal{P}(A)$ is strictly larger.

Iterating: $|A| < |\mathcal{P}(A)| < |\mathcal{P}(\mathcal{P}(A))| < \ldots$

$\mathbb{N} \subsetneq \mathbb{R}$

$\mathbb{N}$ is countable, $\mathbb{R}$ is not.

Lawvere’s Fixed Point Theorem

Statement

If there exists a surjection $e : A \twoheadrightarrow (A \to X)$, then every function $f : X \to X$ has a fixed point.

Proof

Define $\varphi : A \to X$ by $\varphi(a) = f(e(a)(a))$.

Since $e$ is surjective, there exists $a_0$ with $e(a_0) = \varphi$.

Then: $e(a_0)(a_0) = \varphi(a_0) = f(e(a_0)(a_0))$.

So $e(a_0)(a_0)$ is a fixed point of $f$.

Deriving Cantor’s Theorem

Take $X = \{0, 1\}$.

A surjection $A \twoheadrightarrow (A \to \{0, 1\})$ would imply every $f : \{0, 1\} \to \{0, 1\}$ has a fixed point.

But the swap map $f(0) = 1$, $f(1) = 0$ has no fixed point. Contradiction.

Therefore $(A \to \{0, 1\}) \cong \mathcal{P}(A)$ has no surjection from $A$.

---

Summary

• Cantor’s Theorem: No surjection $A \twoheadrightarrow \mathcal{P}(A)$
• Proof uses diagonal argument: construct $U = \{x : x \notin e(x)\}$
• $\mathbb{R}$ is uncountable; there is no largest set
• Lawvere’s theorem generalises Cantor: surjections to function spaces force fixed points