Cantor's Theorem

Cantor's theorem is one of the most fundamental results in set theory, establishing that there is no largest cardinal number. This theorem reveals the richness of infinity and shows that the power set operation always produces a strictly larger set.

TheoremCantor's Theorem

For any set $A$ , there is no surjection from $A$ onto its power set $\mathcal{P}(A)$ . Equivalently, $|A| < |\mathcal{P}(A)|$ .

Proof

Let $f: A \to \mathcal{P}(A)$ be any function. We will construct a subset $D \subseteq A$ that is not in the range of $f$ , proving that $f$ cannot be surjective.

Define the diagonal set:

D = \{x \in A : x \notin f(x)\}

This set is well-defined by the axiom schema of comprehension. We claim that $D$ is not in the range of $f$ . Suppose for contradiction that $D = f(a)$ for some $a \in A$ . Then:

If $a \in D$ , then by definition of $D$ , we have $a \notin f(a) = D$ . Contradiction.
If $a \notin D$ , then $a$ satisfies the condition $a \notin f(a)$ , so by definition of $D$ , we have $a \in D$ . Contradiction.

Both cases lead to contradiction, so $D \notin \text{range}(f)$ . Therefore, $f$ is not surjective.

■

This elegant diagonal argument is fundamental to set theory and appears in many other contexts, including:

Gödel's incompleteness theorems
The undecidability of the halting problem
Turing's proof that certain functions are not computable

Remark

The diagonal set $D$ is constructed so that it differs from $f(a)$ at position $a$ for every $a \in A$ . This is reminiscent of Cantor's original diagonal argument showing that $\mathbb{R}$ is uncountable: constructing a real number that differs from the $n$ -th number in any enumeration at the $n$ -th decimal place.

Cantor's theorem has profound implications for the structure of infinity:

TheoremInfinite Hierarchy of Infinities

There exists an infinite strictly increasing sequence of cardinal numbers:

|\omega| < |\mathcal{P}(\omega)| < |\mathcal{P}(\mathcal{P}(\omega))| < |\mathcal{P}(\mathcal{P}(\mathcal{P}(\omega)))| < \cdots

More generally, defining $\mathcal{P}^0(A) = A$ and $\mathcal{P}^{n+1}(A) = \mathcal{P}(\mathcal{P}^n(A))$ , we have:

|A| < |\mathcal{P}(A)| < |\mathcal{P}^2(A)| < |\mathcal{P}^3(A)| < \cdots

ExampleComputing Cardinalities

Starting from the natural numbers:

$|\omega| = \aleph_0$ (the smallest infinite cardinal)
$|\mathcal{P}(\omega)| = 2^{\aleph_0} = \mathfrak{c}$ (the cardinality of the continuum)
$|\mathcal{P}(\mathcal{P}(\omega))| = 2^\mathfrak{c}$ (the cardinality of the set of all functions $\mathbb{R} \to \mathbb{R}$ )

Each step produces a strictly larger infinity. The continuum hypothesis asks whether $2^{\aleph_0} = \aleph_1$ , i.e., whether there are any cardinals between $\aleph_0$ and $\mathfrak{c}$ .

Cantor's theorem also shows that certain collections cannot be sets:

TheoremNo Universal Set

There is no set $U$ such that every set is a member of $U$ . In other words, the class of all sets is not a set.

Proof

Suppose $U$ is a set containing all sets. Then $\mathcal{P}(U) \subseteq U$ since every subset of $U$ is a set, hence a member of $U$ . This gives an injection $\mathcal{P}(U) \to U$ , contradicting Cantor's theorem which requires $|\mathcal{P}(U)| > |U|$ .

■

This result reinforces the distinction between sets and proper classes in ZFC. The universe $V$ of all sets, the class of all ordinals $\text{Ord}$ , and the class of all cardinals $\text{Card}$ are all proper classes—they are too large to be sets.

ExampleApplications to Function Spaces

Cantor's theorem applies to function spaces. For any sets $A$ and $B$ , the set of all functions from $A$ to $B$ has cardinality $|B|^{|A|}$ . Since $\mathcal{P}(A)$ can be identified with $2^A = \{f : A \to \{0,1\}\}$ , Cantor's theorem states:

|A| < |2^A| = 2^{|A|}

This shows that the exponential function on cardinals is strictly increasing: $\kappa < 2^\kappa$ for all cardinals $\kappa$ .

Remark

Cantor's theorem holds in all models of ZFC and even in weaker systems. It does not depend on the axiom of choice, although determining the exact cardinal arithmetic of infinite power sets often does. The theorem represents a fundamental limitation: no matter how large a set we construct, we can always construct a strictly larger one by taking its power set.

The philosophical implications are striking: there is no "largest" infinity, no ultimate collection that contains everything. The universe of sets is necessarily stratified into an endless hierarchy of ever-larger infinities, each transcending all that came before. This vision of the infinite, pioneered by Cantor, revolutionized mathematics and philosophy.