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