Cantorin diagonaalimenetelmä — määritelmä ja todistus

Cantorin diagonaalimenetelmä: selkeä määritelmä ja vaiheittainen todistus, joka paljastaa äärettömien joukkojen kardinaalisuuden ja havainnollistaa diagonaaliargumentin voiman.

Tekijä: Leandro Alegsa

Cantorin diagonaaliväite on matemaattinen menetelmä, jolla voidaan todistaa, että kahdella äärettömällä joukolla on sama kardinaalisuus. Cantor julkaisi siitä artikkeleita vuosina 1877, 1891 ja 1899. Hänen ensimmäinen todistuksensa diagonaaliargumentista julkaistiin vuonna 1890 Saksan matemaattisen yhdistyksen (Deutsche Mathematiker-Vereinigung) lehdessä. Cantorin mukaan kahdella joukolla on sama kardinaalisuus, jos on mahdollista liittää toisen joukon alkio jokaiseen ensimmäisen joukon alkioon ja ensimmäisen joukon alkio jokaiseen toisen joukon alkioon. Tämä väite toimii hyvin joukoille, joilla on äärellinen määrä alkioita. Se ei ole yhtä intuitiivinen joukoille, joissa on ääretön määrä elementtejä.

Määritelmä ja idea

Cantorin diagonaalimenetelmä on konstruktio, jonka avulla näytetään, että tiettyä joukkoa ei voi luetella eli asettaa yhden–yhteen-yhteyteen luonnollisten lukujen joukon kanssa. Yleisimmin sitä käytetään osoittamaan, että reaaliluvut (esimerkiksi väli [0,1]) ovat luettelamattomia eli ei-laskettavia (uncountable). Menetelmä rakentaa listasta aina uuden alkion, joka eroaa listan ensimmäisen alkion ensimmäisessä paikassa, toisen alkion toisessa paikassa, kolmannen alkion kolmannessa paikassa jne. Tällä tavalla saadaan alkio, joka ei voi esiintyä missään listan rivillä.

Todistus: reaalilukujen ei-laskettavuus (diagonaaliargumentti)

Oletetaan vasta väitteelle, että reaaliluvut välin [0,1] välillä olisivat laskettavissa. Silloin voisimme luetella ne peräkkäin r1, r2, r3, ... ja kirjoittaa jokaisen desimaalikehitelmänä:

r1 = 0.a11 a12 a13 a14 ...
r2 = 0.a21 a22 a23 a24 ...
r3 = 0.a31 a32 a33 a34 ...
...

Missä aij on j:nnessä desimaalipaikassa luvussa ri. Nyt muodostetaan luku s = 0.b1 b2 b3 b4 ... siten, että jokaista n:ää varten bn ≠ ann. Esimerkiksi valitaan

bn = 1 jos ann ≠ 1, muuten bn = 2.

Tällöin s eroaa luvusta rn ainakin n:nnellä desimaalipaikalla, joten s ei voi olla mikään luettelon riveistä. Tämä on ristiriita, koska oletimme kaikkien reaalilukujen olevan listassa. Siispä reaalilukuja ei voi luetella — ne ovat ei-laskettavia.

Huomio desimaaliesityksen epätarkkuudesta: jotkut reaaliluvut, kuten 0.4999... = 0.5, omaavat kahdenlaisia desimaaliesityksiä, mikä voisi vaikeuttaa argumenttia, jos sattuu vertaamaan lukuja juuri noilla rajatapauksilla. Tämä kiistely vältetään helposti valitsemalla bn niin, että se ei koskaan ole 9 (tai muuten käyttämällä vain kahta eri numeroa, kuten 1 ja 2). Näin vältytään toisteisilta loppujaksoilta ja epäselvyyksiltä.

Yleisempi muoto: Cantorin lause (teoria potenssijoukosta)

Diagonaalimenetelmä toimii myös aivan yleisessä muodossa ja johtaa Cantorin kuuluiseen lauseeseen: jokaisen joukon X potenssijoukon P(X) kardinaalisuus on suurempi kuin X:n kardinaalisuus. Todistus on yksinkertainen ja analoginen edelliseen:

Oletetaan kontradiktion vuoksi, että f : X → P(X) olisi surjektio. Määritellään joukko S = { x ∈ X | x ∉ f(x) }. Koska f oletetaan surjektioksi, on olemassa y ∈ X siten, että f(y) = S. Nyt on ristiriita: y ∈ S täsmälleen silloin kun y ∉ f(y) = S. Tämä mahdottomuus osoittaa, ettei surjektiota voi olla ja siten |P(X)| > |X|.

Esimerkki ja seuraukset

  • Esimerkki: jos listaisit mahdolliset binaariset jonoja (esim. 0.01011..., 0.11100..., ...), diagonaalimenetelmällä voit aina rakentaa binaariluvun, joka poikkeaa n:nnellä bitillä n:nnä rivinä — sitä ei siis ole listassa.
  • Seuraukset: Cantorin diagonaalimenetelmä osoittaa muun muassa, että reaalilukujen joukko on suurempi kuin luonnollisten lukujen joukko (eli reaalit ovat ei-laskettava joukko). Yleisemmin se näyttää, että ei ole ”suurinta” äärettömyyttä: jokaiselle joukolle on aina joukko, jolla on suurempi kardinaalisuus (potenssijoukko).
  • Menetelmä on myös keskeinen peruskäsite laskennassa ja logiikassa — diagonaalointi-ajatusta käytetään mm. Gödelin epätäydellisyyslauseissa ja Turingin pysähtymisongelman todistuksissa.

Diagonaalimenetelmä on siis yksinkertainen mutta voimakas idea: rakentamalla järjestelmällisesti poikkeavan rivin (tai joukon) osoitetaan, ettei mikään luettelo voi kattaa kaikkia alkioita. Tämä periaate on yksi modernin matematiikan ja teorian peruspilareista.

Cantorin ensimmäinen diagonaaliargumentti

Alla olevassa esimerkissä käytetään kahta yksinkertaisinta ääretöntä joukkoa, luonnollisten lukujen joukkoa ja positiivisten murtolukujen joukkoa. Ideana on osoittaa, että molemmat näistä joukoista, N {\displaystyle \mathbb {N} }{\displaystyle \mathbb {N} } ja Q + {\displaystyle \mathbb {Q^{+}} }{\displaystyle \mathbb {Q^{+}} } on sama kardinaliteetti.

Ensin murtoluvut kohdistetaan joukkoon seuraavasti:

1 1 1 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 2 2 3 2 4 2 5 ⋯ 3 1 3 2 2 3 3 3 3 3 4 3 5 ⋯ 4 1 4 2 4 3 4 4 4 4 5 ⋯ 5 1 5 2 5 3 5 4 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&\cdots \\\&&&&&&&&&\\\{\tfrac {2}{1}}&&{\tfrac {2}{2}}&&&{\tfrac {2}{3}}&&{\tfrac {2}{4}}&&{\tfrac {2}{5}}&\cdots \\\&&&&&&&&&\\{\tfrac {3}{1}}&&{\tfrac {3}{2}}&&{\tfrac {3}{3}}}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\\\&&&&&&&&&&\\\{\tfrac {4}{1}}&&{\tfrac {4}{2}}&&&{\tfrac {4}{3}}&&&{\tfrac {4}{4}}}&&{\tfrac {4}{5}}&&{\tfrac {4}{5}}&\cdots \\\&&&&&&&&&\\\{\tfrac {5}{1}}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\\vdots &\\\\end{array}}}} {\displaystyle {\begin{array}{cccccccccc}{\tfrac {1}{1}}&&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {2}{1}}&&{\tfrac {2}{2}}&&{\tfrac {2}{3}}&&{\tfrac {2}{4}}&&{\tfrac {2}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {3}{1}}&&{\tfrac {3}{2}}&&{\tfrac {3}{3}}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {4}{1}}&&{\tfrac {4}{2}}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {5}{1}}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}}

Seuraavaksi numerot lasketaan kuvan mukaisesti. Murtoluvut, jotka voidaan yksinkertaistaa, jätetään pois:

1 1 ( 1 ) → 1 2 ( 2 ) 1 3 ( 5 ) → 1 4 ( 6 ) 1 5 ( 11 ) → ↙ ↙ 2 1 ( 3 ) 2 2 ( ⋅ ) 2 3 ( 7 ) 2 4 ( ⋅ ) 2 5 ⋯ ↓ ↙ 3 1 ( 4 ) 3 2 ( 8 ) 3 3 ( ⋅ ) 3 4 3 5 ⋯ ↙ 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclclclclc}{\tfrac {1}{1}{1}}\ _{\color {Blue}(1)}&{\tfrac {1}{4}}\ _{\color {Blue}(6)}&&{\tfrac {1}{5}}\ _{\color {Blue}(11)}&&{\tfrac {1}{5}}\ _{\color {Blue}(11)}&{{\color {MidnightBlue}\rightarrow }\\&{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&\\{\tfrac {2}{1}}\ _{\color {Blue}(3)}&&&{\tfrac {2}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{3}}}\ _{\color {Blue}(7)}&&&{\tfrac {2}{4}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {2}{5}}&\cdots \\\\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&\\{\tfrac {3}{1}}\ _{\color {Blue}(4)}&&&{\tfrac {3}{2}}\ _{\color {Blue}(8)}&&{\tfrac {3}{3}}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {3}{4}}&&&{\tfrac {3}{5}}&\cdots \\\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&&&\\\{\tfrac {4}{1}}\ _{\color {Blue}(9)}&&{\tfrac {4}{2}}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {4}{3}}}&&&{\tfrac {4}{4}{4}}&&{\tfrac {4}{5}}&\cdots \\\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&&&&&\\\{\tfrac {5}{1}}\ _{\color {Blue}(10)}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{4}}&&{\\tfrac {5}{5}}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\\\end{array}}} {\displaystyle {\begin{array}{lclclclclc}{\tfrac {1}{1}}\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{2}}\ _{\color {Blue}(2)}&&{\tfrac {1}{3}}\ _{\color {Blue}(5)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{4}}\ _{\color {Blue}(6)}&&{\tfrac {1}{5}}\ _{\color {Blue}(11)}&{\color {MidnightBlue}\rightarrow }\\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&\\{\tfrac {2}{1}}\ _{\color {Blue}(3)}&&{\tfrac {2}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{3}}\ _{\color {Blue}(7)}&&{\tfrac {2}{4}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{5}}&\cdots \\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&\\{\tfrac {3}{1}}\ _{\color {Blue}(4)}&&{\tfrac {3}{2}}\ _{\color {Blue}(8)}&&{\tfrac {3}{3}}\ _{\color {Blue}(\cdot )}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&&&\\{\tfrac {4}{1}}\ _{\color {Blue}(9)}&&{\tfrac {4}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&&&&&\\{\tfrac {5}{1}}\ _{\color {Blue}(10)}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}}

Näin murtoluvut lasketaan:

1 2 3 4 5 6 7 8 9 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 3 1 3 1 3 1 4 2 3 3 2 4 5 1 5 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}11}&{\color {Blue}\cdots }\\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\\[3pt]1&{\tfrac {1}{2}}&2&3&&{\tfrac {1}{3}}&{\tfrac {1}{4}}&{\tfrac {2}{3}}&{\tfrac {3}{2}}&4&5&{\tfrac {1}{5}}&\cdots \\\\\\end{array}}}} {\displaystyle {\begin{array}{cccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}\cdots }\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\[3pt]1&{\tfrac {1}{2}}&2&3&{\tfrac {1}{3}}&{\tfrac {1}{4}}&{\tfrac {2}{3}}&{\tfrac {3}{2}}&4&5&{\tfrac {1}{5}}&\cdots \\\end{array}}}

Kun jätetään pois murtoluvut, joita voidaan vielä yksinkertaistaa, saadaan bijektio, joka yhdistää jokaisen luonnollisten lukujen alkion yhteen murtolukujen alkioon:

Jotta voidaan osoittaa, että kaikilla luonnollisilla luvuilla ja murtoluvuilla on sama kardinaliteetti, on lisättävä alkio 0; jokaisen murtoluvun jälkeen lisätään sen negatiivinen luku;

 2 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 2 3 - 2 3 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}12}&{\color {Blue}13}&{\color {Blue}14}&{\color {Blue}15}& {\color {Blue}15}&{\color {Blue}\cdots }\\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\\[3pt]0&1&-1&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&&2&-2&3&-3&{\tfrac {1}{3}}&-{\tfrac {1}{3}}&{\tfrac {1}{4}}&-{\tfrac {1}{4}}&{\tfrac {2}{3}}&-{\tfrac {2}{3}}}&\cdots \\\\\\end{array}}}} {\displaystyle {\begin{array}{cccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}12}&{\color {Blue}13}&{\color {Blue}14}&{\color {Blue}15}&{\color {Blue}\cdots }\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\[3pt]0&1&-1&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&2&-2&3&-3&{\tfrac {1}{3}}&-{\tfrac {1}{3}}&{\tfrac {1}{4}}&-{\tfrac {1}{4}}&{\tfrac {2}{3}}&-{\tfrac {2}{3}}&\cdots \\\end{array}}}

Näin saadaan täydellinen bijektio, joka yhdistää murtoluvun jokaiseen luonnolliseen lukuun. Toisin sanoen: molemmilla joukoilla on sama kardinaalisuus. Nykyään joukkoja, joilla on yhtä monta elementtiä kuin luonnollisten lukujen joukolla, kutsutaan laskettaviksi. Joukkoja, joilla on vähemmän alkioita kuin luonnollisten lukujen joukolla, kutsutaan korkeintaan laskettaviksi. Tällä määritelmällä rationaalilukujen / murtolukujen joukko on laskettavissa.

Äärettömillä joukoilla on usein intuition vastaisia ominaisuuksia: David Hilbert osoitti tämän kokeessa, jota kutsutaan Hilbertin Grand Hotel -paradoksiksi.

Reaaliluvut

Reaalilukujen joukolla ei ole samaa kardinaalisuutta kuin luonnollisten lukujen joukolla; reaalilukuja on enemmän kuin luonnollisia lukuja. Edellä esitetty ajatus vaikutti hänen todistukseensa. Vuonna 1891 julkaistussa artikkelissaan Cantor tarkasteli kaikkien binäärilukujen äärettömien sarjojen joukkoa T (eli jokainen luku on nolla tai yksi).

Hän aloittaa rakentavalla todistuksella seuraavasta lauseesta:

Jos s1 , s2 , ... , sn , ... on mikä tahansa T:n elementtien luettelo, niin T:ssä on aina elementti s, jota ei vastaa mikään sn luettelossa.

Todistetaan tämä antamalla T:n elementtien luettelo, kuten esim.

s1 =

(0,

0,

0,

0,

0,

0,

0,

...)

s2 =

(1,

1,

1,

1,

1,

1,

1,

...)

s3 =

(0,

1,

0,

1,

0,

1,

0,

...)

s4 =

(1,

0,

1,

0,

1,

0,

1,

...)

s5 =

(1,

1,

0,

1,

0,

1,

1,

...)

s6 =

(0,

0,

1,

1,

0,

1,

1,

...)

s7 =

(1,

0,

0,

0,

1,

0,

0,

...)

...

Jakso s muodostetaan valitsemalla 1. numero täydentämään s1 :n 1. numeroa (vaihtamalla 0:t 1:iin ja päinvastoin), 2. numero täydentämään s2 :n 2. numeroa, 3. numero täydentämään s3 :n 3. numeroa ja yleensä jokaiselle n:lle nth -numero täydentämään sn :n nth -numeroa. Esimerkin tapauksessa tämä johtaa:

s1

=

(0,

0,

0,

0,

0,

0,

0,

...)

s2

=

(1,

1,

1,

1,

1,

1,

1,

...)

s3

=

(0,

1,

0,

1,

0,

1,

0,

...)

s4

=

(1,

0,

1,

0,

1,

0,

1,

...)

s5

=

(1,

1,

0,

1,

0,

1,

1,

...)

s6

=

(0,

0,

1,

1,

0,

1,

1,

...)

s7

=

(1,

0,

0,

0,

1,

0,

0,

...)

...

s

=

(1,

0,

1,

1,

1,

0,

1,

...)

Rakenteellisesti s eroaa jokaisesta sn , koska niiden nth numerot eroavat toisistaan (esimerkissä korostettu). Näin ollen s ei voi esiintyä luettelossa.

Tämän lauseen perusteella Cantor osoittaa sitten ristiriitatodistuksen avulla, että:

Joukko T on lukematon.

Hän olettaa, että T oli laskettavissa. Tällöin kaikki sen elementit voitaisiin kirjoittaa luettelona s1 , s2 , ... , sn , ... ... . Edellisen lauseen soveltaminen tähän luetteloon tuottaisi sarjan s, joka ei kuulu luetteloon. S oli kuitenkin T:n elementti, joten sen pitäisi olla luettelossa. Tämä on ristiriidassa alkuperäisen oletuksen kanssa, joten T:n on oltava luettelematon.

Kysymyksiä ja vastauksia

K: Mikä on Cantorin diagonaaliväite?


V: Cantorin diagonaaliväite on matemaattinen menetelmä, jolla todistetaan, että kahdella äärettömällä joukolla on sama kardinaalisuus.

K: Milloin Cantor julkaisi artikkeleita diagonaaliväitteestään?


V: Cantor julkaisi diagonaaliargumenttiaan käsitteleviä artikkeleita vuosina 1877, 1891 ja 1899.

K: Missä julkaistiin Cantorin ensimmäinen todistus diagonaaliargumentista?


V: Cantorin ensimmäinen todistus diagonaaliargumentista julkaistiin vuonna 1890 Saksan matemaattisen yhdistyksen (Deutsche Mathematiker-Vereinigung) lehdessä.

K: Milloin kahdella joukolla on Cantorin mukaan sama kardinaalisuus?


V: Cantorin mukaan kahdella joukolla on sama kardinaalisuus, jos on mahdollista liittää toisen joukon alkio jokaiseen ensimmäisen joukon alkioon ja ensimmäisen joukon alkio jokaiseen toisen joukon alkioon.

Kysymys: Toimiiko Cantorin väite kardinaalisuudesta hyvin joukoille, joissa on äärellinen määrä alkioita?


V: Kyllä, Cantorin väite toimii hyvin joukoille, joissa on äärellinen määrä elementtejä.

K: Onko Cantorin lausuma kardinaalisuudesta intuitiivinen joukoille, joissa on ääretön määrä alkioita?


V: Ei, Cantorin lausuma kardinaalisuudesta ei ole yhtä intuitiivinen joukoille, joissa on ääretön määrä elementtejä.

K: Kuinka monta kertaa Cantor julkaisi artikkeleita diagonaaliväitteestään?


V: Cantor julkaisi artikkeleita diagonaaliväitteestään kolme kertaa - vuosina 1877, 1891 ja 1899.


Etsiä
AlegsaOnline.com - 2020 / 2025 - License CC3