Diagonalization

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 1-1 correspondence to the natural numbers, thereby demonstrating the real numbers are not countable. This method can be applied to any infinite set to construct an even larger infinite set.

Proof of the non-countability of real numbers

There exists a map $f:\mathbb {R} \rightarrow [0,1]$ (in fact all infinitly supported probability distribution does this). Therefore there are as many number in $[0,1]$ as $\mathbb {R}$.

We will now use proof by contradiction to show that the numbers in $[0,1]$ are uncountable.

Assume the numbers in [0,1], are countable. Then we can list them as such,

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

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

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.a_{31}a_{32}a_{33}a_{34}a_{35}\dots }

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.a_{41}a_{42}a_{43}a_{44}a_{45}\dots }

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 \vdots }

Where 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 a_{ij}\in\{0,1,2,3,4,5,6,7,8,9\}}

Construct the number,

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 a=0.a_{1}a_{2}a_{3}a_{4}\dots} , where

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 a_{i}=1} when 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 a_{ii}\neq1} and 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 a_{i}=2} when 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 a_{ii}=1} .

Therefore 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 a} is not in the list, so we have a contradiction and our assumption is false, the numbers in 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]} are not countable. Therefore 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 \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. This seeming disproof of the existence of God has cast doubt on the validity of Cantor's diagonalization.