Cantor's Diagonal Argument

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set such that $\card S > 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 = \set {f: \N \to S}$

Then $\mathbb F$ is uncountably infinite.


Proof

First we note that as $\card S > 1$, there are at least two elements of $S$ which are distinct.

Call these distinct elements $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:

$\map {\phi_m} n = \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 = \map {\phi_{m_1} } {m_1} \ne \map {\phi_{m_2} } {m_1} = a$

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

$\map \Psi n = \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 $\map \Phi n$.

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

$\map g n = \begin{cases} a & : \map {f_n} n \ne a \\ b & : \map {f_n} n = a \end{cases}$

Then $g \in \mathbb F$, but:

$\forall n \in \N: \map g n \ne \map {f_n} n$

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.


Historical Note

Georg Cantor was the first on record to have used the technique of what is now referred to as Cantor's Diagonal Argument when proving the Real Numbers are Uncountable.


Sources