Diagonalization

<math>\frac{d}{dx} \sin x=?\,</math>

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 <math>\mathbb{R}\,</math> and the open interval <math>(0, 1)\,</math>. This function:

<math>y = \frac{\tan^{-1}(x)}{\pi} + \frac{1}{2}</math>

maps the entire real line to the open interval <math>(0, 1)\,</math>. Its inverse:

<math>x = \tan(\pi(y - 1/2))\,</math>

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 <math>(0, 1)\,</math> 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:

<math> 0.a_{11}a_{12}a_{13}a_{14}a_{15}\dots </math>

<math> 0.a_{21}a_{22}a_{23}a_{24}a_{25}\dots </math>

<math> 0.a_{31}a_{32}a_{33}a_{34}a_{35}\dots </math>

<math> 0.a_{41}a_{42}a_{43}a_{44}a_{45}\dots </math>

<math> \vdots </math>

Where <math>a_{ij}\in\{0,1,2,3,4,5,6,7,8,9\}</math>

Construct the number,

<math>a=0.a_{1}a_{2}a_{3}a_{4}\dots</math>, where

<math>a_{i}=1</math> when <math>a_{ii}\neq1</math> and <math>a_{i}=2</math> when <math>a_{ii}=1</math>.

Therefore, <math>a</math> is not in the list, so we have a contradiction and our assumption is false, the numbers in <math>[0,1]</math> are not countable. Therefore, <math>\mathbb{R}</math> 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.