Cantor's diagonal argument

Cantor's diagonal method provides a convenient proof that the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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, where perhaps its most well known application is the negative solution halting problem.

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} , and it must therefore correspond to a set not in the range of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Psi} . This contradiction shows that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{\mathbb{N}}} cannot be countable.