# Power Set of Natural Numbers is not Countable

Jump to navigation
Jump to search

## Theorem

The power set $\powerset \N$ 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 \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 not countable.

$\blacksquare$

## Sources

- 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $1$: Mappings: $\S 15$