Cantor's Theorem¶

Theorem¶

Cantor's theorem states that for every set $A$ ,

\operatorname{card}(A)<\operatorname{card}(2^A),

where $2^A$ is the power set of $A$ .

Interpretation¶

Cantor's theorem says that a set always has more subsets than elements: no function from $A$ to its power set $2^A$ , also written $\mathcal{P}(A)$ , can reach every subset. This holds for infinite sets too.

A set A = {a, b} mapped into its power set, which has four elements; the empty set and {a, b} are never hit by the map that sends x to {x}.

For $A=\{a,b\}$ the power set has $2^2=4$ elements. The map $x\mapsto\{x\}$ is injective, which shows $\operatorname{card}(A)\le\operatorname{card}(2^A)$ $card (2^{A})$ , but it hits only $\{a\}$ and $\{b\}$ , never $\varnothing$ or $\{a,b\}$ . For a finite set with $n$ elements the theorem is just $n<2^n$ $2^{n}$ ; its content is that no other map does better, even for infinite sets.

The reason is a diagonal construction. Given any $f\colon A\to2^A$ $2^{A}$ , form $D=\{x\in A\colon x\notin f(x)\}$ $f (x)}$ . If $D=f(d)$ for some $d\in A$ $A$ , then $d\in D$ exactly when $d\notin f(d)=D$ $D$ , which is impossible. So $D$ is missed and no $f$ is surjective, in particular no $f$ is a bijection. In the figure every $x$ lies in $\{x\}$ , so $D=\varnothing$ $\emptyset$ , one of the two missed subsets.

Applied to $\mathbb{N}$ , the theorem gives the uncountable set $2^{\mathbb{N}}$ , whose cardinality is the cardinality of the continuum. Applied again and again it gives $\aleph_0<2^{\aleph_0}<2^{2^{\aleph_0}}<\cdots$ $\dots$ , so there is no largest infinite size. The argument has the same shape as Cantor's diagonal argument for the real numbers.

Key Results¶

For every infinite set $A$ , the sets $A,2^A,2^{2^A},\ldots$ represent an infinite staircase of larger and larger infinite cardinalities.
A bijection is the main tool for proving that two sets have the same cardinality.

Examples¶

For $A=\mathbb{N}$ $N$ , the power set $2^{\mathbb{N}}$ has larger cardinality than $\mathbb{N}$ .

Prerequisites¶

Sources¶

Math II: Linear Algebra · Week 1

Aliases: Cantor theorem, Cantor's power set theorem Symbols: element of, natural numbers

Last updated: 27 October 2026 11:52