Cantor's Theorem and the Cardinal Hierarchy

Cantor's theorem shows that there is no largest cardinal, establishing an infinite hierarchy of infinities.

Statement

Theorem5.6Cantor's theorem

For every set $A$ , there is no surjection $f: A \twoheadrightarrow \mathcal{P}(A)$ . Consequently, $|A| < |\mathcal{P}(A)| = 2^{|A|}$ .

Proof

Let $f: A \to \mathcal{P}(A)$ be any function. We show $f$ is not surjective by constructing a subset of $A$ not in the range of $f$ .

Define the diagonal set:

$D = \{a \in A : a \notin f(a)\}.$

Then $D \subseteq A$ , so $D \in \mathcal{P}(A)$ . We claim $D \notin \mathrm{ran}(f)$ .

Suppose for contradiction that $D = f(d)$ for some $d \in A$ . There are two cases:

If $d \in D$ : by definition of $D$ , $d \notin f(d) = D$ , a contradiction.
If $d \notin D$ : by definition of $D$ , $d \in f(d) = D$ , a contradiction.

In either case we reach a contradiction, so no such $d$ exists, and $f$ is not surjective.

The injection $A \hookrightarrow \mathcal{P}(A)$ given by $a \mapsto \{a\}$ shows $|A| \leq |\mathcal{P}(A)|$ , and the non-surjectivity shows $|A| \neq |\mathcal{P}(A)|$ . Therefore $|A| < |\mathcal{P}(A)|$ . $\blacksquare$

■

The Cardinal Hierarchy

RemarkIterating the power set

Starting from $\mathbb{N}$ , Cantor's theorem produces a strictly increasing sequence of cardinalities:

$|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots$

i.e., $\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < \cdots$ . These are the beth numbers: $\beth_0, \beth_1, \beth_2, \ldots$ . The process continues transfinitely.

ExampleVariations of the diagonal argument

Uncountability of $\mathbb{R}$ : Specializing to $A = \mathbb{N}$ and identifying $\mathcal{P}(\mathbb{N})$ with $\{0,1\}^{\mathbb{N}}$ (binary sequences), Cantor's theorem gives $|\mathbb{N}| < |\{0,1\}^{\mathbb{N}}| = |\mathbb{R}|$ .
No universal set: If a "universal set" $U$ with $U \in U$ existed, then $\mathrm{id}: U \to \mathcal{P}(U)$ (treating elements as subsets) would be a surjection, contradicting Cantor.
Russell's paradox: The diagonal set $D = \{a : a \notin f(a)\}$ with $f = \mathrm{id}$ becomes $R = \{x : x \notin x\}$ , recovering Russell's paradox from Cantor's argument.

Theorem5.7No set of all cardinals

There is no set containing all cardinal numbers. The collection of all cardinals is a proper class.

RemarkEaston's theorem

While Cantor's theorem shows $2^\kappa > \kappa$ , and Konig's theorem gives $\mathrm{cf}(2^\kappa) > \kappa$ , Easton's theorem (1970) shows that these are essentially the only ZFC restrictions on the exponential function for regular cardinals. That is, any function $F$ on regular cardinals satisfying $\kappa < F(\kappa)$ and $\kappa \leq \lambda \implies F(\kappa) \leq F(\lambda)$ and $\mathrm{cf}(F(\kappa)) > \kappa$ can be realized as $\kappa \mapsto 2^\kappa$ in some model of ZFC.