Theorem·T21
The power set of the naturals is uncountable
There is no injection from the sets of naturals into the naturals.
In words
There is no injection from the power set of omega into omega: the collection of all sets of natural numbers cannot be labelled by the naturals.
Never needed: F05 · F10 · F11 · F12 · F13 · A02 · A03 · A05 · A07 · A08 (computed from the citation graph, not asserted).
Proof
- 1
- 2Define by This is single-valued: if then because is injective, so at most one triggers the first clause; with excluded middle deciding which clause applies, is a function ( is a set by Power set).
- 3is surjective onto : given , set ; then witnesses the first clause, so .
- 4Thus is surjective. But Cantor's theorem says no function is surjective onto . This contradiction (F03) refutes the assumption: has no injection into , so it is not countable.
∎
Remarks
Uncountability enters the library:
is infinite like
yet strictly larger, the first rung of Cantor's hierarchy of infinities. The argument is Cantor's theorem transported across the domination order: an injection
would invert to a surjection
, which Cantor forbids. Once the real numbers are constructed,
, so this is the uncountability of the continuum.