Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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) –  moose Apr 4 '12 at 9:53

2 Answers 2

up vote 22 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|improve this answer
4  
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

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|improve this answer
3  
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

 
discard

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.