Cantorin diagonaaliargumentti

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ä.

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.

AlegsaOnline.com - 2020 / 2023 - License CC3