39
$\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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – André Nicolas Oct 31 '11 at 23:16
  • $\begingroup$ This question has been asked before. $\endgroup$ – Asaf Karagila Oct 31 '11 at 23:19
  • 2
    $\begingroup$ 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) $\endgroup$ – Martin Thoma Apr 4 '12 at 9:53
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Aug 24 '16 at 18:36
60
+50
$\begingroup$

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

$\endgroup$
  • 8
    $\begingroup$ 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 $\endgroup$ – Martin Thoma Oct 31 '11 at 23:58
  • $\begingroup$ 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? $\endgroup$ – Martin Thoma Nov 8 '14 at 21:41
  • 6
    $\begingroup$ @moose: You're going to miss every subset of $\mathbb N$ that is not finite, such as the set of all even numbers. $\endgroup$ – Henning Makholm Nov 8 '14 at 21:45
  • $\begingroup$ 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. $\endgroup$ – Martin Thoma Nov 8 '14 at 21:47
  • 2
    $\begingroup$ @moose: Bonus hint: The binary representation of a natural number provides a nice enumeration of the finite subsets of $\mathbb N$. $\endgroup$ – Henning Makholm Nov 8 '14 at 21:50
12
$\begingroup$

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.

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

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.$$

$\endgroup$
  • $\begingroup$ This is just the usual proof, which was linked to in the other (six year old!) answers. $\endgroup$ – Noah Schweber Aug 1 '17 at 14:27
  • 2
    $\begingroup$ 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. $\endgroup$ – LRDPRDX Aug 1 '17 at 16:39
  • 1
    $\begingroup$ It is the usual proof - do you know of any basic set theory texts which introduce the theorem using a different argument? $\endgroup$ – Noah Schweber Aug 1 '17 at 16:40
  • 2
    $\begingroup$ I do not think it is the right place for this discussion. Keep calm:) $\endgroup$ – LRDPRDX Aug 1 '17 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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