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

- Assume for contradiction that $\mathcal P(\mathbb N)$ is countable.
- 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$.
- Consider the set $S = \{ s\in\mathbb N: s\not\in f(s) \}$.
*Exercise: Argue that $S$ is well-defined.* - Note that $S\subseteq \mathbb N$. This implies that $S\in \mathcal P(\mathbb N)$.
- By (2), since $S\in \mathcal P(\mathbb N)$, then there exists $m \in \mathbb N$ such that $f(m)=S$.
- $ m \in S \iff m\not\in f(m) \iff m\not\in S $ is a contradiction.
- Hence, $\mathcal P(\mathbb N)$ is uncountable.