Cantor's Theorem
Cantor's theorem is the fundamental result of set theory that establishes the existence of infinite hierarchies of infinity. Proved by Georg Cantor in 1891, it states that for any set A, the power set P(A) — the set of all subsets of A — has strictly greater cardinality than A itself. No surjective function from A to P(A) can exist. The theorem is the engine behind the endless tower of infinities: starting from the natural numbers ℕ, we obtain P(ℕ) with strictly more elements, then P(P(ℕ)) with still more, and so on without end.
The proof is a direct application of the diagonal argument. Assume a function f: A → P(A) exists. Consider the set B = {x ∈ A : x ∉ f(x)} — the set of all elements that are not members of their own image under f. If B = f(y) for some y ∈ A, then ask: is y ∈ B? If yes, then by definition y ∉ f(y) = B. If no, then y ∈ f(y) = B. Either way, contradiction. The set B is precisely the element that f misses, constructed from f itself. Every proposed enumeration of the power set refutes itself by generating its own missing subset.
The Hierarchy of Infinities
Cantor's theorem generates an unending hierarchy of cardinal numbers. Beginning with ℵ₀ = |ℕ|, the cardinality of the natural numbers, we define:
- ℵ₀ = |ℕ|
- 2^ℵ₀ = |P(ℕ)| = |ℝ| (the cardinality of the continuum)
- 2^(2^ℵ₀) = |P(P(ℕ))|
- And so on: ℵ₀ < 2^ℵ₀ < 2^(2^ℵ₀) < ⋯
The Continuum Hypothesis asks whether there exists any cardinality strictly between ℵ₀ and 2^ℵ₀. Cantor's theorem proves that the hierarchy is strictly increasing, but it does not settle whether the gaps between successive levels are empty or populated. This independence — proved by Gödel and Cohen — is not a failure of the theorem but a discovery that the set-theoretic universe admits multiple consistent configurations at the level of the continuum.
The power set operation, which Cantor's theorem shows is always expansive, is the same operation that generates the von Neumann hierarchy: V_{α+1} = P(V_α). The theorem guarantees that no stage of the cumulative hierarchy ever exhausts the possibilities of the next. The hierarchy is not merely tall; it is irreducibly branching, with each power set introducing combinatorial structures that cannot be predicted from below.
Generalizations and Connections
Cantor's theorem extends beyond sets. In type theory, the analogous result is that the type of propositions over a type A cannot be enumerated by A itself — a form of impredicativity. In category theory, the theorem appears as the statement that the subobject classifier of a topos is never isomorphic to any object in the topos. In computer science, it underlies the proof that the halting problem is undecidable: the set of all programs that halt on their own encoding is the diagonal set that any proposed enumeration must miss.
The theorem also connects to Gödel's incompleteness theorems through the same diagonal structure. In Gödel's proof, a formula asserts its own unprovability; in Cantor's proof, a set asserts its own non-membership in the image of a function. Both constructions exploit self-reference to demonstrate that no system can fully capture itself. The Barber Paradox and the Liar Paradox are the same pattern in natural language and semantics.
Cantor's Theorem and the Limits of Formal Systems
The deepest reading of Cantor's theorem is not about infinity but about self-reference. Any system rich enough to describe its own subsets contains the seed of its own transcendence. The power set operation is not merely combinatorial; it is epistemic — it represents everything the system can say about itself, and the theorem proves that this saying always exceeds the system itself.
This reading transforms Cantor's theorem from a result about infinite sets into a claim about any formal system whatsoever: completeness is impossible not because the system is too small but because self-description is structurally generative. The system cannot close over itself. This is not a bug. It is the feature that makes mathematics infinite.
Cantor's theorem is usually presented as a result about the size of infinite sets. This misses the point. The theorem is a result about the limits of any system that can refer to itself — and that includes every formal system worthy of the name. The hierarchy of infinities is not a curiosity of set theory. It is the mathematical trace of a structural law: no system can be its own power set. This law applies to logic, computation, language, and cognition. The infinite hierarchy is not a property of sets. It is a property of representation itself.