Is the power set of the natural numbers countable?

Question

Some explanations: A set S is countable if there exists an injective function f from S to the natural numbers.

$\{1,2,3,4\}, \mathbb{N},\mathbb{Z}, \mathbb{Q}$ are all countable.

$\mathbb{R}$ is not countable.

The power set $\mathcal P(A) $ is defined as a set of all possible subsets of A, including the empty set and the whole set.

$\mathcal P (\{\}) = \{\{\}\}, \mathcal P ( \mathcal P (\{\})) = \{\{\}, \{\{\}\}\} $

$\mathcal P({1,2}) = \{\{\}, \{1\},\{2\},\{1,2\}\}$

My question is:

Is $\mathcal P (\mathbb{N})$ countable? How would a function f look like?

Answer 1

Cantor's Theorem states that for a nonempty set $A$ there is no surjective function $A\to\mathcal P(A)$. With $A=\mathbb N$ this implies that $\mathcal P(\mathbb N)$ is not countable.

(But where on earth did you find those nice explanations of countability and power sets that didn't also tell you this?)

Answer 2

Power set of natural numbers has the same cardinality with the real numbers. So, it is uncountable.

In order to be rigorous, here's a proof of this.