What is $\mathcal P(\mathbb N)$?

• Let $A$ be a set.
• A power set of $A$ is the set of all the subsets of $A$.
• $\mathcal P(A)$ denotes the power set of $A$.
• $\mathcal P(\mathbb N)$ is the set of all the subsets of $\mathbb N$.

Theorem (Cantor)

1. Assume for contradiction that $\mathcal P(\mathbb N)$ is countable.
2. There exists an onto function $f: \mathbb N \to \mathcal P(\mathbb N)$. Since $f$ is onto, for every $X\in \mathcal P(\mathbb N)$, there exists $n \in \mathbb N$ such that $f(n)=X$.
3. Consider the set $S = \{ s\in\mathbb N: s\not\in f(s) \}$. Exercise: Argue that $S$ is well-defined.
4. Note that $S\subseteq \mathbb N$. This implies that $S\in \mathcal P(\mathbb N)$.
5. By (2), since $S\in \mathcal P(\mathbb N)$, then there exists $m \in \mathbb N$ such that $f(m)=S$.
6. $m \in S \iff m\not\in f(m) \iff m\not\in S$ is a contradiction.
7. Hence, $\mathcal P(\mathbb N)$ is uncountable.