Power Set of Natural Numbers Not Countable

Theorem

The power set $\mathcal P \left({\N}\right)$ of the natural numbers $\N $ is not countable.

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 \mathcal P \left({\N}\right)$.

From the Cantor-Bernstein-Schroeder Theorem, there can be no injection $g: \mathcal P \left({\N}\right) \to \N$.

So, by definition, $\mathcal P \left({\N}\right)$ is not countable.

$\blacksquare$

Sources

• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 15$