Ero sivun ”Cantorin diagonaaliargumentti” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
huomautus pois |
|||
Rivi 1:
'''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]].
Rivi 7 ⟶ 5:
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 ==
Cantorin alkuperäinen todistus osoittaa, ettei [[väli (matematiikka)|väli]] [0,1] ole numeroituvasti ääretön. Todistus perustuu vastaoletukselle ja etenee seuraavasti:
| |||