Cantor's Diagonal Argument

Theorem

Let $S$ be a set such that $\left|{S}\right| > 1$, that is, such that $S$ is not a singleton.

Let $\mathbb F$ be the set of all mappings from the natural numbers $\N$ to $S$:

$\mathbb F = \left\{{f: \N \to S}\right\}$

Then $\mathbb F$ is uncountably infinite.

Proof

First we note that as $\left|{S}\right| > 1$, there are at least two elements of $S$ which are unequal. Call them $a$ and $b$.

That is, $\exists a, b \in S: a \ne b$.

First we show that $\mathbb F$ is infinite, as follows.

For each $m \in \N$, let $\phi_m$ be the mapping defined as:

$\phi_m \left({n}\right) = \begin{cases} a & : n \ne m \\ b & : n = m \end{cases}$

Then $\forall m_1, m_2 \in \N: m_1 \ne m_2 \implies \phi_{m_1} \ne \phi_{m_2}$ as $b = \phi_{m_1} \left({m_1}\right) \ne \phi_{m_2} \left({m_1}\right) = a$.

So the mapping $\Psi: \N \to \mathbb F$ defined as:

$\Psi \left({n}\right) = \phi_{n}$

is an injection.

Thus $\mathbb F$ is infinite from Infinite if Injection from Natural Numbers.

Next we show that $\mathbb F$ is uncountable.

Let $\Phi: \N \to \mathbb F$ be a mapping.

For each $n \in \N$ let $f_n: \N \to S$ be the function $\Phi \left({n}\right)$.

Let us define $g: \N \to \N$ by:

$g \left({n}\right) = \begin{cases} a & : f_n \left({n}\right) \ne a \\ b & : f_n \left({n}\right) = a \end{cases}$

Then $g \in \mathbb F$, but $\forall n \in \N$, $g \left({n}\right) \ne f_n \left({n}\right)$ and so $g \ne f_n$.

Since $g$ is an element of $\mathbb F$ which is different from all the values taken by $\Phi$, it follows that $\Phi$ is not a surjection and hence not a bijection.

Thus no bijection exists between $\mathbb F$ and $\N$ and so $\mathbb F$ is not equivalent to $\N$.

Thus from Countably Infinite Iff Equivalent to Natural Numbers, $\mathbb F$ is uncountable.

$\blacksquare$

Also see

• Set of Infinite Sequences is Uncountable, which is a basic application of this technique.

Source of Name

This entry was named for Georg Cantor.

He was the first on record to have used this technique when proving the Real Numbers are Uncountable.