Difference between revisions of "Diagonalization"
| Line 6: | Line 6: | ||
We will now use [[proof by contradiction]] to show that the numbers in <math>[0,1]</math> are uncountable. | We will now use [[proof by contradiction]] to show that the numbers in <math>[0,1]</math> are uncountable. | ||
| − | Assume | + | Assume the numbers in [0,1], are countable. Then we can list them (without use of the [[Axiom of Choice]]) as such, |
<math> | <math> | ||
Revision as of 02:26, June 15, 2008
Diagonalization is a technique first used by George Cantor, a German mathematician. He used it to show that the cardinality of the real numbers is not equal to the cardinality of 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 <math>f:[0,1]\rightarrow\mathbb{R}</math> (in fact all infinitly supported probability distribution does this). Therefor there are as many number in <math>[0,1]</math> as <math>\mathbb{R}</math>.
We will now use proof by contradiction to show that the numbers in <math>[0,1]</math> are uncountable.
Assume the numbers in [0,1], are countable. Then we can list them (without use of the Axiom of Choice) as such,
<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>.
Therefor <math>a</math> is not in the list, so we have a contradition and our assumption is false, the number <math>[0,1]</math> are not countable. Therefor <math>\mathbb{R}</math> is uncountable.[1]
Diagonalization and the Existence of God
Some have cited diagonalization as a formal challenge to Saint Anselm's 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] This seeming disproof of the existence of God has cast doubt on the validity of Cantor's diagonalization.
References
- ↑ Komolgorov, Introduction to Real Analysis. (You can find it inalmost any book store).
- ↑ http://www.ephilosopher.com/e107_plugins/forum/forum_viewtopic.php?104130
- ↑ 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.