Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 34 down vote accepted

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?)

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.