Cantorin diagonaaliargumentti

Wikipedia
Loikkaa: valikkoon, hakuun

Cantorin diagonaaliargumentti on Georg Cantorin ilmeisesti jo vuonna 1877 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 lauseen: 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).

Reaaliluvut[muokkaa | muokkaa wikitekstiä]

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.

  1. Vastaoletus: Oletetaan, että välillä [0,1] olevien reaalilukujen joukko on numeroituvasti ääretön.
  2. Koska joukko on numeroituvasti ääretön, voimme luetella kaikki välin reaaliluvut seuraavasti: (r1, r2, r3, ...)
  3. Kukin näistä luvuista voidaan esittää desimaalikehitelmänä.
  4. 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:
    r1 = 0 , 5 1 0 5 1 1 0 ...
    r2 = 0 , 4 1 3 2 0 4 3 ...
    r3 = 0 , 8 2 4 5 0 2 6 ...
    r4 = 0 , 2 3 3 0 1 2 6 ...
    r5 = 0 , 4 1 0 7 2 4 6 ...
    r6 = 0 , 9 9 3 7 8 3 8 ...
    r7 = 0 , 0 1 0 5 1 3 5 ...
    ...
  5. Konstruoimme nyt reaaliluvun x väliltä [0,1] poimimalla siihen kunkin reaaliluvun rk k:nnen numeron desimaalipilkun jälkeen laskettuna. Poimittavat numerot on lihavoitu. Ne sijaitsevat taulukon diagonaalilla, mistä todistuksen nimi.
    r1 = 0 , 5 1 0 5 1 1 0 ...
    r2 = 0 , 4 1 3 2 0 4 3 ...
    r3 = 0 , 8 2 4 5 0 2 6 ...
    r4 = 0 , 2 3 3 0 1 2 6 ...
    r5 = 0 , 4 1 0 7 2 4 6 ...
    r6 = 0 , 9 9 3 7 8 3 8 ...
    r7 = 0 , 0 1 0 5 1 3 5 ...
    ...
  6. Näistä luvuista määrittelemme luvun x desimaalit seuraavasti:
    • jos rk:n k:s luku on 5, on x:n desimaalikehitelmän k:s numero 4
    • jos rk:n k:s luku on erisuuri kuin 5, on x:n desimaalikehitelmän k:s numero 5
  7. 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 ...
  8. Koska listassamme (r1, r2, r3, ...) on lueteltu kaikki reaaliluvut välillä [0, 1], täytyy olla myös x = rn jollakin n.
  9. Valitsimme kuitenkin kohdassa 6 x:n desimaalikehitelmän numerot (nelosia ja vitosia) siten, että x eroaa n:nnessä desimaalissaan jokaisesta luvusta rn. Tämän vuoksi x ei ole jonossa (r1, r2, r3, ...).
  10. Jono (r1, r2, r3, ...) 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.)
  11. Siis vastaoletus on väärä ja väite oikea.

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]