# 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
• As a footnote to the answers already given, you should also see a useful result known variously as the Schroeder-Bernstein, Cantor-Bernstein, or Cantor-Schroeder-Bernstein theorem. Some books present the easy proof; some others have the hard proof of it. – DanielWainfleet Aug 24 '16 at 18:36

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. – hmakholm left over Monica 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$. – hmakholm left over Monica 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

Here is my favorite proof that $$|\mathcal{P}(M)| > |M|, \quad\forall M.$$

## Proof

$$\big[\exists\phi:M \stackrel{\mathrm{on}}{\to}\mathcal{P}(M)\big]$$ $$\Downarrow$$ $$\Big[\big[A_{\not\phi} := \{m|m\in M, m\notin\phi(m)\}\big]\Rightarrow A_{\not\phi}\in\mathcal{P}(M)\Rightarrow\exists p\in M:\phi(p) = A_{\not\phi}\Big]$$ $$\Downarrow$$ $$\Big[\big[p\in A_{\not\phi}\Rightarrow p\notin A_{\not\phi}\big]\quad \mathrm{and}\quad\big[p\notin A_{\not\phi}\Rightarrow p\in A_{\not\phi}\big]\Big]$$ $$Q.E.D.$$

• This is just the usual proof, which was linked to in the other (six year old!) answers. – Noah Schweber Aug 1 '17 at 14:27
• Sorry for repeating. By the way, may be it is well known proof, but it does not imply it is usual. Rather the opposite. Sorry for not mathematical discussion. – LRDPRDX Aug 1 '17 at 16:39
• It is the usual proof - do you know of any basic set theory texts which introduce the theorem using a different argument? – Noah Schweber Aug 1 '17 at 16:40
• I do not think it is the right place for this discussion. Keep calm:) – LRDPRDX Aug 1 '17 at 17:07