38
$\begingroup$

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?

  • 1
    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.2011-10-31
  • 0
    This question has been asked before.2011-10-31
  • 1
    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)2012-04-04
  • 0
    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.2016-08-24

3 Answers 3

57

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

  • 8
    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 about2011-10-31
  • 0
    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?2014-11-08
  • 6
    @moose: You're going to miss every subset of $\mathbb N$ that is not finite, such as the set of all even numbers.2014-11-08
  • 0
    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.2014-11-08
  • 2
    @moose: Bonus hint: The binary representation of a natural number provides a nice enumeration of the finite subsets of $\mathbb N$.2014-11-08
  • 0
    would this be true for the rationals and integers as well?2015-03-17
12

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.

  • 7
    It might be useful to include a proof of this fact, or cite a source for it at least.2011-11-01
1

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

Proof

$$\big[\exists\phi:M \stackrel{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.$$

  • 0
    This is just the usual proof, which was linked to in the other (six year old!) answers.2017-08-01
  • 1
    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.2017-08-01
  • 1
    It is the usual proof - do you know of any basic set theory texts which introduce the theorem using a different argument?2017-08-01
  • 1
    I do not think it is the right place for this discussion. Keep calm:)2017-08-01