|
'''Cantorin diagonaaliargumentti''' on [[Georg Cantor]]in esittämä [[matemaattinen todistus]] sille, että [[reaaliluvut|reaalilukujen]] joukko ei ole [[numeroituva joukko|numeroituvasti ääretön]] vaan [[ylinumeroituva joukko|ylinumeroituva]].
Diagonaaliargumentti ei ollut Cantorin ensimmäinen todistus reaalilukujen ylinumeroituvuudelle, vaan se julkaistiin kolme vuotta hänen ensimmäisen todistuksensa jälkeen. Osoitus siitä, että reaalilukujen joukko on "suurempi" kuin [[rationaaliluvut|rationaalilukujenrationaaliluku]]jen joukko johtaa kysymykseen, onko olemassa joukkoa jonka mahtavuus olisi näiden joukkojen mahtavuuksien välissä eli ns. [[kontinuumihypoteesi]]in.
Cantor käytti diagonaaliargumentin yleistettyä muotoa todistaakseen [[Cantorin teoreema]]n: kaikkien joukkojen S [[potenssijoukko]] <math>\mathcal{P}(S)</math> eli kaikkien joukon S [[osajoukko]]jen joukko on suurempi kuin S itse. Samankaltaisia todistustekniikoita on myöhemmin käytetty useita kertoja monien ongelmien ratkaisussa. Diagonaaliargumentin avulla voidaan esimerkiksi osoittaa, että [[päätösongelma|päätösongelmia]] on ylinumeroituva määrä. Koska minkä tahansa [[ohjelmointikieli|ohjelmointikielen]] [[tietokoneohjelma|ohjelmia]] on vain numeroituva määrä, on siis olemassa ratkeamattomia ongelmia (esimerkiksi [[pysähtymisongelma]]).
==Reaaliluvut==
# Jono (''r''<sub>1</sub>, ''r''<sub>2</sub>, ''r''<sub>3</sub>, ...) ei siis sisällä kaikkia reaalilukuja väliltä [0,1], mikä on ristiriita. (Voimme toki lisätä x:n jonoon, mutta diagonalisoinnin voi suorittaa mielivaltaisen monta kertaa.)
# Siis vastaoletus on väärä ja väite oikea.
<!--== General sets ==
A generalized form of the diagonal argument was used by Cantor to prove [[Cantor's theorem]]: for every [[set]] ''S'' the [[power set]] of ''S'', i.e., the set of all [[subset]]s of ''S'' (here written as '''P'''(''S'')), is larger than ''S'' itself. This proof proceeds as follows:
Let ''f'' be any one-to-one function from ''S'' to '''P'''(''S''). It suffices to prove ''f'' cannot be [[surjective]]. That means that some member of '''P'''(''S''), i.e., some subset of ''S'', is not in the image of ''f''. That set is
:<math>T=\{\,s\in S: s\not\in f(s)\,\}.</math>
If ''T'' is in the range of ''f'', then for some ''t'' in ''S'' we have ''T'' = ''f''(''t''). Either ''t'' is in ''T'' or not.
If ''t'' is in ''T'', then ''t'' is in ''f''(''t''), but, by definition of ''T'', that implies ''t'' is not in ''T''. On the other hand, if ''t'' is not in ''T'', then ''t'' is not in ''f''(''t''), and by definition of ''T'', that implies ''t'' is in ''T''. Either way, we have a contradiction.
Note the similarity between the construction of ''T'' and the set in [[Russell's paradox]]. Its result can be used to show that the notion of the [[set of all sets]] is an inconsistent notion in normal [[set theory]]; if '''''S''''' would be the set of all sets then '''P'''('''''S''''') would at the same time be bigger than '''''S''''' and a subset of '''''S'''''.
The above proof fails for [[W. V. Quine]]'s "New Foundations" set theory, which has a different version of the [[axiom of separation]] in which <math>\{\,s\in S: s\not\in f(s)\,\}</math> cannot be expressed.
For a more concrete account of this proof that is possibly easier to understand see [[Cantor's theorem]].
Analogues of the diagonal argument are widely used in mathematics to prove the existence or nonexistence of certain objects. For example, the conventional proof of the unsolvability of the [[halting problem]] is essentially a diagonal argument.
The diagonal argument shows that the set of real numbers is "bigger" than the set of integers. Therefore, we can ask if there is a set whose [[cardinality]] is "between" that of the integers and that of the reals. This question leads to the famous [[continuum hypothesis]]. Similarly, the question of whether there exists a set whose cardinality is between ''s'' and '''P'''(''s'') for some ''s'', leads to the [[generalized continuum hypothesis]].-->
== Aiheesta muualla ==
| 