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

  • 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

72

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

  • 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
2

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

  • 1
    I do not think it is the right place for this discussion. Keep calm:)2017-08-01