Axiomatic WikiWWikiTTheoremsCantor's theorem
Theorem·T03
No set maps onto its own power set: there are ever-bigger infinities.
For every set
and every function
into the power set,
is not surjective: some subset of
is missed,
In words
No function f from a set A to its power set is surjective: there is a set D such that D is a member of the power set of A and, for every x, if x is a member of A then f applied to x is not D.
Never needed: F05 · F10 · F11 · F12 · F13 · A02 · A03 · A05 · A07 · A08 · A09 (computed from the citation graph, not asserted).
Proof
- 1Let be any function. By Separation, form the diagonal set which is well defined because is a set for each (D013).
- 2
- 3Suppose, for contradiction (negation introduction), that is surjective. Then there is with .
- 4Ask whether . By the defining property of : , using and substitutivity.
- 5As in T02, a proposition equivalent to its own negation is contradictory: either case of excluded middle refutes itself. This is absurd (falsum), so no such exists and is not surjective.
∎
Remarks
The first theorem of the theory of the infinite (Cantor, 1891). Combined with the observation that
is an injection of
into
, it says the power set is strictly larger: in the language of equinumerosity,
. Iterating gives an endless ladder of infinities, starting from the naturals:
,
,
, and so on. The diagonal set
is the same self-reference engine that powers Russell's paradox and, decades later, Godel's incompleteness theorem and Turing's halting problem.