|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 and the open interval . This function:
maps the entire real line to the open interval . Its inverse:
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 is in correspondence.
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:
Construct the number,
when and when .
Therefore is not in the list, so we have a contradiction and our assumption is false, the numbers in are not countable. Therefore 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.
- A. N. Kolmogorov, Introductory Real Analysis. ISBN 978-0486612263.
- 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.