TheoremProved

Cantor's theorem

Statement

For every set $A$ , $|A| < |\mathcal{P}(A)|$ : there is no surjection from $A$ onto its power set $\mathcal{P}(A)$ , so the power set is strictly larger.

Why is it true?

This shows there is no single "biggest infinity" — from any set, however large, you can always build a strictly larger one just by taking its power set. It is the theorem that makes an infinite hierarchy of infinities unavoidable, and its diagonal-argument proof technique is the direct ancestor of the arguments used to show some problems are uncomputable.

Proof sketch

Suppose, for contradiction, that there is a surjection $f : A \to \mathcal{P}(A)$ ; we will derive a contradiction, which shows no such surjection can exist.

Define the "diagonal" set $D = \{x \in A : x \notin f(x)\}$ : it collects every element of $A$ that is not a member of its own image under $f$ . Since $D$ is a subset of $A$ , it is an element of $\mathcal{P}(A)$ .

Because $f$ is assumed surjective, there must be some $a_0 \in A$ with $f(a_0) = D$ . Now ask the deciding question: is $a_0 \in D$ ?

If $a_0 \in D$ , then by the definition of $D$ , $a_0 \notin f(a_0)$ ; but $f(a_0) = D$ , so this says $a_0 \notin D$ — a contradiction. If instead $a_0 \notin D$ , then by the definition of $D$ (which excludes exactly the elements with $a_0 \in f(a_0)$ ), this forces $a_0 \in f(a_0) = D$ — again a contradiction.

Either way we reach a contradiction, so no surjection $f : A \to \mathcal{P}(A)$ can exist. Combined with the injection $x \mapsto \{x\}$ from $A$ into $\mathcal{P}(A)$ , this gives exactly $|A| < |\mathcal{P}(A)|$ .

Topics that use this theorem

Functions and cardinality

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Paul R. Halmos (1960). Naive Set Theory
Karel Hrbacek, Thomas Jech (1999). Introduction to Set Theory