Cantori diagonaalargument: selgitus ja tõestus lõpmatu hulga kardinaalsusest
Cantori diagonaalargument selgitatuna: samm-sammult tõestus lõpmatute hulkade kardinaalsusest, ajalooline kontekst ja selged näited õppijatele ning huvilistele matemaatikas.
Cantori diagonaalargument on matemaatiline meetod, mida kasutatakse eelkõige selleks, et näidata: mõned lõpmatud hulgad ei saa olla ühesuguse kardinaalsusega. 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 tähendab täpsemalt olemasolu bijektsioonist). See definitsioon töötab hästi piiratud arvu elementidega hulkade puhul, kuid käib ka lõpmate hulkade kohta ja selle intuitiivne mõistmine on sageli raskem.
Mida Cantori diagonaalargument näitab?
Diagonaalargument on lihtne ja võimas meetod, millega saab tõestada kaks põhilist väidet:
- Reaalarvude hulga (või bitijadade hulk) on mitteloetletav: ei saa koostada täielikku loendit kõigist reaalarvudest vahemikus (0,1), st neid ei saa panna bijektsiooni naturaalarvudega.
- Cantori teoreem: iga hulga A võimsus (kardinaalsus) on väiksem kui tema osa(hulkade) kogu P(A) ehk ei eksisteeri ülekattuvat (surjektiivset) kujutist A-st P(A)-sse.
Lihtne kirjeldus ja intuitsioon
Põhiidee on järgmine: oletame vastuoluna, et mingi lõpmatu hulk on täielikult loetletav (või et olemas on kujutis, mis katab kõik hulgad P(A)). Diagonaalargumendis ehitatakse konstrueeritult üks element, mis erineb iga loendis olevast elemendist vähemalt ühes kohas (diagonaalis) — seega pole seda elementi loendis ja väide kukub läbi. Nimelt „võetakse diagonaal” ja sellele vastupidise valiku abil saadakse uus element, mida loetelus ei ole.
Tõestus lihtsustatud kujul: binaarsekvensside näide
Kujuta ette, et meil on loend kõigist binaarsekvenssidest (iga element on lõpmatu jada nullidest ja ühtedest), kus rida n esindab n-ndat sekvenssi. Kui selline loend olemas oleks, koostame uue sekvenssi b järgmiselt:
- võta diagonaalelemendid a11, a22, a33, ... (kus aij on i-nda rea j-s element);
- määra b_n = 1, kui a_nn = 0, ja b_n = 0, kui a_nn = 1 (ehk b_n erineb a_nn-st);
- sellega on b erinev i-ndast reas kindlasti i-s kohas, seega pole b loendis leiduv;
- seevastu väidetakse, et loend siiski sisaldab kõiki sekvensse — vastuolu näitab, et algne oletus oli vale.
Sama idee rakendades reaalarvudele (0,1) esindatakse neid kahend- või kümnendarvuna ja ehitatakse reaal, mis erineb loetletud i-ndast reaalarvust i-ndal positsioonil. Tulemus: reaalarve ei saa loetleda.
Formaalne tõestus Cantori teoreemi kohta
Olgu A mistahes hulk ja oletame vastuväidete kujul, et eksisteerib funktsioon f: A → P(A), mis on surjektiivne (iga osa B ⊆ A on kujutis mõnest a ∈ A järgi). Defineeri hulk
D = { a ∈ A : a ∉ f(a) }.
Küsimus: kas leidub x ∈ A nii, et f(x) = D? Kui eeldame, et f(x) = D, siis vaatleme, kas x ∈ D kehtib:
- Kui x ∈ D, siis x ∉ f(x) = D — vastuolu.
- Kui x ∉ D, siis x ∈ f(x) = D — samuti vastuolu.
Seega ei saa ükski x ∈ A anda f(x) = D. See näitab, et f ei ole surjektsioon — P(A) sisaldab alati hulka, mida f ei kata. Järelikult |P(A)| > |A|. See on Cantori teoreem, mille tõestus kasutab täpselt diagonaalide ideed.
Rakendused ja tagajärjed
- Reaalarvude hulga kardinaalsus on 2^{ℵ0} (või tuntud kui kontinumm) ja see on rangelt suurem kui naturaalarvude hulk ℵ0.
- Existentsist, et iga hulk A-l on osa(hulkade) kogu P(A), mis on alati „suurem”, tekib hulgahierarhia — lõpmatusi on erinevaid suurusi.
- Cantori diagonaalargument on aluseks paljudele teoreetilistele tulemustele, sealhulgas küsimustele, mis puudutavad kontinuumi hüpoteesi (kas leidub kardinaalsus vahepeal ℵ0 ja 2^{ℵ0}?), mis kujutas endas olulist teemat 20. sajandi hulgateoorias.
Praktilised märkused
Reaalarvude puhul tuleb tähele panna kahend- või kümnendkujutiste dubleerimist (näiteks lõppnev lõpmatuse asemel korduv 9- või 1-jada: 0.0999... = 0.1000...). Diagonaalargumendi juures saab sellisest ambivalentsusest hoiduda, piirates esindusi (näiteks keelata lõppevad kõik nullijärgsed esitused või üldse hilisemaid pidevaid lõppevaid kujutisi), nii et iga reaal oleks loetletud üheselt.
Kokkuvõte: Cantori diagonaalargument on lihtne, kuid võimas konstruktsioon, mis näitab, et igal hulgal on alati „suurem” osa(hulkade) kogu ning et mõned lõpmatud hulgad (näiteks reaalarvud) on naturaalarvuliselt loendamatud. See argumendimeetod on hulgateooria ja fundamentaalse matemaatika oluline tööriist.
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} } ja 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}}}
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}}}
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}}}}
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}}}
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.