Cantorin diagonaaliargumentti

Wikipedia

Cantorin diagonaaliargumentti on Georg Cantorin esittämä matemaattinen todistus sille, että reaalilukujen joukko ei ole numeroituvasti ääretön vaan 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 jossain mielessä "suurempi" kuin rationaalilukujen joukko johtaa kysymykseen, onko olemassa joukkoa, jonka mahtavuus olisi näiden joukkojen mahtavuuksien välissä. Tämä ongelma tunnetaan myös kontinuumihypoteesina.

Cantor käytti diagonaaliargumentin yleistettyä muotoa todistaakseen Cantorin teoreeman: kaikkien joukkojen S potenssijoukko $\mathcal{P}(S)$ eli kaikkien joukon S osajoukkojen 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ösongelmia on ylinumeroituva määrä. Koska minkä tahansa ohjelmointikielen ohjelmia on vain numeroituva määrä, on siis olemassa ratkeamattomia ongelmia (esimerkiksi pysähtymisongelma).

[muokkaa] Reaaliluvut

Cantorin alkuperäinen todistus osoittaa, ettei väli [0,1] ole numeroituvasti ääretön. Todistus perustuu vastaoletukselle ja etenee seuraavasti:

Väite: välin [0,1] reaalilukujen joukko on ylinumeroituva.

Vastaoletus: Oletetaan, että välillä [0,1] olevien reaalilukujen joukko on numeroituvasti ääretön.
Koska joukko on numeroituvasti ääretön, voimme luetella kaikki välin reaaliluvut seuraavasti: (r₁, r₂, r₃, ...)
Kukin näistä luvuista voidaan esittää desimaalikehitelmänä.
Järjestämme luvut listaksi (niiden ei tarvitse olla suuruusjärjestyksessä). Luvuille, joilla on useita desimaalikehitelmiä (kuten 0,499 ... = 0,500 ...) valitsemme yhdeksiköistä koostuvan esityksen. Oletetaan esimerkin vuoksi, että laadittu lista alkaa seuraavasti:

r₁ = 0 , 5 1 0 5 1 1 0 ...

r₂ = 0 , 4 1 3 2 0 4 3 ...

r₃ = 0 , 8 2 4 5 0 2 6 ...

r₄ = 0 , 2 3 3 0 1 2 6 ...

r₅ = 0 , 4 1 0 7 2 4 6 ...

r₆ = 0 , 9 9 3 7 8 3 8 ...

r₇ = 0 , 0 1 0 5 1 3 5 ...

...
Konstruoimme nyt reaaliluvun x väliltä [0,1] poimimalla siihen kunkin reaaliluvun r_k k:nnen numeron desimaalipilkun jälkeen laskettuna. Poimittavat numerot on alleviivattu ja lihavoitu. Ne sijaitsevat taulukon diagonaalilla, mistä todistuksen nimi.

r₁ = 0 , 5 1 0 5 1 1 0 ...

r₂ = 0 , 4 1 3 2 0 4 3 ...

r₃ = 0 , 8 2 4 5 0 2 6 ...

r₄ = 0 , 2 3 3 0 1 2 6 ...

r₅ = 0 , 4 1 0 7 2 4 6 ...

r₆ = 0 , 9 9 3 7 8 3 8 ...

r₇ = 0 , 0 1 0 5 1 3 5 ...

...
Näistä luvuista määrittelemme luvun x desimaalit seuraavasti:
- jos r_k:n k:s luku on 5, on x:n desimaalikehitelmän k:s numero 4
- jos r_k:n k:s luku on erisuuri kuin 5, on x:n desimaalikehitelmän k:s numero 5
Saatu luku x on selvästi reaaliluku välillä [0,1] (koska kaikki luvut sen desimaalikehitelmässä ovat reaalilukuja). Yllä olevan esimerkin mukaisesti saamme

x = 0,4555554 ...
Koska listassamme (r₁, r₂, r₃, ...) on lueteltu kaikki reaaliluvut välillä [0, 1], täytyy olla myös x = r_n jollakin n.
Valitsimme kuitenkin kohdassa 6 x:n desimaalikehitelmän numerot (nelosia ja vitosia) siten, että x eroaa n:nnessä desimaalissaan jokaisesta luvusta r_n. Tämän vuoksi x ei ole jonossa (r₁, r₂, r₃, ...).
Jono (r₁, r₂, r₃, ...) 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.