Another rendition of
Georg Cantor's proof with more modern notations.
Theorem
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)