Another rendition of Georg Cantor's proof with more modern notations.


For any set A, the power set P(A) is larger than A. This holds since there exists an obvious injection from A to P(A), and not so obvious, there does not exist a surjection from A to P(A).

Proof by contradiction

Suppose there exists surjective f: A → P(A).
Let B = {a ∈ A : a !∈ f(a)}. ("!∈" meaning "not in," for browsers that don't support ∉)
Since B ∈ P(A) and f surjective, ∃ b ∈ A : f(b) = B.
But b exists neither in B nor not in B! Contradiction. ∴ Surjective f cannot exist.

Russell was one of the people who asked about the case where A contained everything. This line of thought lead to the celebrated Russell's Paradox. To resolve this paradox, modern axiomatic set theory was developed. (see: ZF, Axiom of Choice)