# Diagonalization

 $\frac{d}{dx} \sin x=?\,$ This article/section deals with mathematical concepts appropriate for a student in late high school or early university.

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 $(0, 1)\,$. Its inverse:

$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

ai = 1 when $a_{ii}\neq1$ and ai = 2 when aii = 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.[1]

## 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.[2]

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.[3]

## References

1. A. N. Kolmogorov, Introductory Real Analysis. ISBN 978-0486612263.
2. http://www.ephilosopher.com/e107_plugins/forum/forum_viewtopic.php?104130
3. Topo-philosophies: Plato's Diagonals, Hegel's Spirals, and Irigaray's Multifolds, Arkady Plotnitsky. In After Poststructuralism: Writing the Intellectual History of Theory Tilottama Rajan, Michael James.