Cantor's diagonal argument

Cantor's diagonal method provides a convenient proof that the set $2^{\mathbb {N} }$ of subsets of the natural numbers (also known as its power set is not countable. More generally, it is a recurring theme in computability theory.

The Argument

To any set $S\subset 2^{\mathbb {N} }$ we may associate a function $\phi :S\rightarrow \{0,1\}$ by setting $\phi (n)=1$ if $n\in S$ and $\phi (n)=0$, otherwise. Conversely, every such function defines a subset.

If power set is countable, there is a bijective map $\Psi :\mathbb {N} \rightarrow 2^{\mathbb {N} }$, that allows us to assign an index $i=\Psi ^{-1}(S)$ to every subset S. Assuming this has been done, we proceed to construct a function $\psi :\mathbb {N} \rightarrow \{0,1\}$ such that the corresponding set, $T$ cannot be in the range of $\Psi$.

For each $i$, either $\phi _{i}(i)=0$ or $\phi _{i}(i)=1$, and so we may simply $\psi (i)$ such that $\psi (i)\not =\phi _{i}(i)$.

It follows that $\psi \not =\phi _{i}$ for any $i$, and it must therefore correspond to a set not in the range of $\Psi$. This contradiction shows that $2^{\mathbb {N} }$ cannot be countable.