# 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) – Martin Thoma 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 – Martin Thoma Oct 31 '11 at 23:58
Today I thought about this again and I am a little bit confused. The powerset $\mathcal{P}(A_n)$ with $A_n := \{1, ..., n\}$ is finite for every $n$. So can't I simply count up for every $A_n$ (so first $\mathcal{P}(A_1)$, then $\mathcal{P}(A_2)$, $\mathcal{P}(A_3)$, ...? Where does it break? – Martin Thoma Nov 8 '14 at 21:41
@moose: You're going to miss every subset of $\mathbb N$ that is not finite, such as the set of all even numbers. – Henning Makholm Nov 8 '14 at 21:45
Thank you! It's so obvious when you read it ... I ask because I have an application where I need (theoretically; it is a generator) every finite subset of $\mathbb{N}$ and this is something that bothered me. – Martin Thoma Nov 8 '14 at 21:47
@moose: Bonus hint: The binary representation of a natural number provides a nice enumeration of the finite subsets of $\mathbb N$. – Henning Makholm Nov 8 '14 at 21:50

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.

-
It might be useful to include a proof of this fact, or cite a source for it at least. – Zev Chonoles Nov 1 '11 at 2:09