# Is the power set of the natural numbers countable?

Some explanations: A set S is countable if there exists an injective function $f$ from $S$ to the natural numbers ($f:S \rightarrow \mathbb{N}$).

$\{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 an injective function $f:S \rightarrow \mathbb{N}$ look like?

-
It isn't countable. To prove this, you can use diagonalization directly, or use the fact, which presumably has been proved by now, that the reals are uncountable. –  André Nicolas Oct 31 '11 at 23:16
This question has been asked before. –  Asaf Karagila Oct 31 '11 at 23:19
The cardinality of the power $\mathcal P (A)$ of any set A is always higher than the cardinality of a set A (Source: "Lineare Algebra", ISBN 978-3-528-66508-1, page 14) –  moose Apr 4 '12 at 9:53

Cantor's Theorem states that for any 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?)

-
Those nice explanations of countability and power sets were written by myself. Thanks for the compliment ;-) I just wanted to make sure that everybody who reads this question knows what I'm talking about –  moose Oct 31 '11 at 23:58