Power Set of Natural Numbers is Uncountable
Jump to navigation
Jump to search
Theorem
The power set $\powerset \N$ of the natural numbers $\N$ is uncountable.
Proof
There is no bijection from a set to its power set.
From Injection from Set to Power Set, we have that there exists an injection $f: \N \to \powerset \N$.
From the Cantor-Bernstein-Schröder Theorem, there can be no injection $g: \powerset \N \to \N$.
So, by definition, $\powerset \N$ is uncountable.
$\blacksquare$
Sources
- 1971: Allan Clark: Elements of Abstract Algebra ... (previous) ... (next): Chapter $1$: Mappings: $\S 15$