Cantor's Diagonal Argument

From ProofWiki
Jump to: navigation, search

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


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.