Cantor - Uncountability of $\mathcal P(\mathbb N)$

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.