Diagonalization

${\frac {d}{dx}}\sin x=?\,$

This article/section deals with mathematical concepts appropriate for late high school or early college.

Diagonalization is a technique first used by Georg Cantor, a German mathematician. He used it to show that the real numbers can not be put into one-to-one correspondence with the natural numbers, thereby demonstrating the real numbers are not countable. This method can also be applied in other contexts, to show that two sets can't have a correspondence. For example, it can be used to show that no set can be in 1-1 correspondence with the set of all of its subsets.

Proof of the non-countability of real numbers

First, we create a 1-1 correspondence between the entire real line $\mathbb {R} \,$ and the open interval $(0,1)\,$. This function:

$y={\frac {\tan ^{-1}(x)}{\pi }}+{\frac {1}{2}}$

maps the entire real line to the open interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (0, 1)\,} . Its inverse:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = \tan(\pi(y - 1/2))\,}

maps the open interval to the entire real line.

This means that the real numbers are in 1-1 correspondence with the natural numbers if and only if the open interval $(0,1)\,$ is in correspondence.

We will now use proof by contradiction to show that this open interval has no such correspondence, and thus it, and the real line as a whole, are uncountable.

Assume the numbers in this open interval are in a 1-1 correspondence with the natural numbers. Then we can make an (infinite) sequential list of them, like this:

$0.a_{11}a_{12}a_{13}a_{14}a_{15}\dots$

$0.a_{21}a_{22}a_{23}a_{24}a_{25}\dots$

$0.a_{31}a_{32}a_{33}a_{34}a_{35}\dots$

$0.a_{41}a_{42}a_{43}a_{44}a_{45}\dots$

$\vdots$

Where $a_{ij}\in \{0,1,2,3,4,5,6,7,8,9\}$

Construct the number,

$a=0.a_{1}a_{2}a_{3}a_{4}\dots$, where

$a_{i}=1$ when $a_{ii}\neq 1$ and $a_{i}=2$ when $a_{ii}=1$.

Therefore, $a$ is not in the list, so we have a contradiction and our assumption is false, the numbers in $[0,1]$ are not countable. Therefore, $\mathbb {R}$ is uncountable.

Diagonalization and the Existence of God

Some have cited diagonalization as a formal challenge to Saint Anselm's ontological argument for the existence of God. In summary, Anselm argued that there must be a greatest idea and what could be greater than God? Therefore, God exists.

However, diagonalization argues that no greatest idea can exist: quite bluntly, God is infinite, therefore He can be diagonalized to produce an even greater infinite.