Cantori diagonaalargument

Cantori diagonaalargument on matemaatiline meetod, millega tõestatakse, et kahel lõpmatul hulgal on sama kardinaalsus. Cantor avaldas selle kohta artikleid 1877., 1891. ja 1899. aastal. Tema esimene diagonaalargumendi tõestus avaldati 1890. aastal Saksa Matemaatikaühingu (Deutsche Mathematiker-Vereinigung) ajakirjas. Cantori järgi on kahel hulgal sama kardinaalsus, kui esimese hulga igale elemendile on võimalik seostada üks element teisest hulgast ja teise hulga igale elemendile üks element esimesest hulgast. See väide töötab hästi piiratud arvu elementidega hulkade puhul. See on vähem intuitiivne lõpmatu arvu elementidega hulkade puhul.

Cantori esimene diagonaalargument

Allpool esitatud näites kasutatakse kahte lihtsamat lõpmatut hulka, milleks on naturaalarvud ja positiivsed murdarvud. Idee on näidata, et mõlemad kogud, N {\displaystyle \mathbb {N} }{\displaystyle \mathbb {N} } ja Q + {\displaystyle \mathbb {Q^{+}} }{\displaystyle \mathbb {Q^{+}} } on sama kardinaalsusega.

Kõigepealt joondatakse fraktsioonid massiivi järgmiselt:

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 3 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 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccccccc}{\tfrac {1}{1}}&&{\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}}}&\cdots \\\&&&&&&&&&\\{\tfrac {5}{1}}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\\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}}}

Seejärel loetakse numbrid, nagu näidatud. Lihtsustatavad murdarvud jäetakse välja:

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 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclclclclc}{\tfrac {1}{1}}\ _{\color {Blue}(1)}&{\tfrac {1}{2}}\ _{\tfrac {1}{2}}\ _{\tfrac {Blue}(2)}&&{\tfrac {1}{3}}\ _{\tfrac {1}{3}}\ _{\tfrac {Blue}(5)}&{{\tfrac {1}{4}}\ _{\tfrac {1}{4}}\ _{\tfrac {1}{6)}&&{\tfrac {1}{5}}\ _{\tfrac {1}{11)}\ _{\tfrac {1}(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}}}

Sel viisil loetakse murdosaid:

1 2 3 4 5 6 7 8 9 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 3 1 3 1 4 2 3 3 2 4 5 1 5 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}& {\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 }&{\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}}}

Jätkuvalt lihtsustatavate murdude väljajätmise korral on olemas bijektsioon, mis seostab iga naturaalarvude elementi ühe murdude elemendiga:

Et näidata, et kõik naturaalarvud ja murdarvud on sama kardinaalsusega, tuleb lisada element 0; iga murdarvu järel lisatakse selle negatiiv;

 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}\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}}}

Nii on olemas täielik bihektoorsus, mis seostab igale naturaalarvule murdosa. Teisisõnu: mõlemal hulgal on sama kardinaalsus. Tänapäeval nimetatakse kogumeid, millel on sama palju elemente kui naturaalarvude hulgal, loendatavateks. Kogumeid, millel on vähem elemente kui loomulikel arvudel, nimetatakse maksimaalselt loendatavateks. Selle definitsiooni järgi on ratsionaalarvude / murdude hulk loendatav.

Lõpmatutel hulkadel on sageli omadusi, mis lähevad vastuollu intuitsiooniga: David Hilbert näitas seda eksperimendis, mida nimetatakse Hilberti Grand Hotel'i paradoksiks.

Reaalarvud

Reaalarvude hulk ei ole sama kardinaalsusega kui naturaalarvude hulk; reaalarvusid on rohkem kui naturaalarve. Eespool kirjeldatud idee mõjutas tema tõestust. Oma 1891. aasta artiklis käsitles Cantor kõigi lõpmatute binaarsete numbrite (st iga number on null või üks) jadade kogumit T.

Ta alustab järgmise teoreemi konstruktiivse tõestusega:

Kui s1 , s2 , ... , sn , ... on ükskõik milline T elementide loend, siis on alati olemas T element s, millele ei vasta loenduses ükski sn .

Selle tõestamiseks, kui on antud elementide loend T-st, näiteks

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,

...)

...

Jada s moodustatakse, valides 1. numbri komplementaarseks s1 1. numbrile (vahetades 0-d 1-dega ja vastupidi), 2. numbri komplementaarseks s2 2. numbrile, 3. numbri komplementaarseks s3 3. numbrile ja üldiselt iga n puhul nth numbri komplementaarseks sn nth numbrile. Näites annab see tulemuseks:

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,

...)

Konstruktsiooni järgi erineb s igast sn , kuna nende nth numbrid erinevad (näites esile tõstetud). Seega ei saa s loetelus esineda.

Selle teoreemi põhjal näitab Cantor seejärel vastuvaidlemistõendiga, et:

Kogum T on loendamatu.

Ta eeldab, et T oli loendatav. Sel juhul võiks kõik selle elemendid kirjutada loeteluna s1 , s2 , ... , sn , ... ... . Eelmise teoreemi rakendamine sellele loendusele annaks tulemuseks loendusse mittekuuluva jada s. Kuid s oli T element ja peaks seega kuuluma loendisse. See on vastuolus algse eeldusega, seega peab T olema loendamatu.

Küsimused ja vastused

K: Mis on Cantori diagonaalargument?


V: Cantori diagonaalargument on matemaatiline meetod, millega tõestatakse, et kahel lõpmatul hulgal on sama kardinaalsus.

K: Millal avaldas Cantor artikleid oma diagonaalargumendi kohta?


V: Cantor avaldas artikleid oma diagonaalargumendi kohta aastatel 1877, 1891 ja 1899.

K: Kus avaldati Cantori esimene tõestus diagonaalargumendi kohta?


V: Cantori esimene tõestus diagonaalargumendi kohta avaldati 1890. aastal Saksa Matemaatikaühingu (Deutsche Mathematiker-Vereinigung) ajakirjas.

K: Millal on Cantori järgi kahel hulgal sama kardinaalsus?


V: Cantori järgi on kahel hulgal sama kardinaalsus, kui esimese hulga igale elemendile on võimalik seostada üks element teisest hulgast ja teise hulga igale elemendile üks element esimesest hulgast.

Küsimus: Kas Cantori väide kardinaalsuse kohta töötab hästi piiratud arvu elementidega hulkade puhul?


V: Jah, Cantori väide töötab hästi piiratud arvu elementidega hulkade puhul.

K: Kas Cantori väide kardinaalsuse kohta on intuitiivne lõpmatu arvu elementidega hulkade puhul?


V: Ei, Cantori väide kardinaalsuse kohta on vähem intuitiivne lõpmatu arvu elementidega hulkade puhul.

K: Mitu korda avaldas Cantor artikleid oma diagonaalargumendi kohta?


V: Cantor avaldas artikleid oma diagonaalargumendi kohta kolm korda - 1877., 1891. ja 1899. aastal.

AlegsaOnline.com - 2020 / 2023 - License CC3