Cantors diagonalbevis
Cantors Diagonalbevis er det første bevis på, at de reelle tal er ikke-tællelige blev publiceret allerede i 1874. Beviset viser, at der er uendeligt store mængder, der ikke kan sættes i en en-til-en korrespondance til mængden af de naturlige tal. Sådanne mængder kaldes derfor ikke-tællelige mængder.
Først i 1891 publicerede Cantor det såkaldte diagonalbevis for påstanden om, at der findes tællelige og ikke-tællelige uendeligt store mængder. Diagonalbeviset illustrerer en meget kraftig og generel teknik, som siden er blevet brugt i en bred vifte af beviser.
Sammenligning af mængder
redigérMan kan naturligvis sammenligne endelige mængder ved at tælle dem. Men
man kan også sammenligne mængder uden at tælle elementerne i mængderne,
ved simpelthen at forsøge at parre elementerne i den ene med elementerne
i den anden. Dette giver også en mulighed for at sammenligne uendelige
mængder. Følgelig skulle man ifølge Cantor kunne bestemme, at to uen-
delige mængder ikke er lige store, hvis det beviseligt ikke kan lade sig gøre
at oprette en én-til-én parring af alle elementer i den ene med alle elementer
i den anden. Altså matematisk udtrykt: Hvis der ikke findes en bijektiv
afbildning fra den ene mængde til den anden.
Bemærk, at vi ofte bruger den metode i det daglige til at sammenligne
mængder. Fx ved spørgsmålet om der er ligeså mange kaffekopper på et
kaffebord, som der er pladser ved bordet? Her tæller vi ikke alle kopperne
og pladserne, men nøjes med at se efter om der evt. mangler kopper ved
nogle pladser.
Kardinaltal
redigérCantor indførte begrebet kardinaltal til beskrivelse af størrelsen/mægtigheden af mængder, specielt med henblik på uendelige mængder.
Definition
redigérTo mængder har samme kardinaltal, hvis der findes en bijektiv afbildning fra den ene mængde til den anden.
Følgende viser et eksempel på fire uendelige mængder med samme kardinaltal.
- (De naturlige tal)
- (De hele tal)
- (Primtallene)
- (Mængden af alle endelige bitstrenge, hvor en bit er enten 0 eller 1)
Disse kan alle parres én-til-én med de naturlige tal, simpelthen fordi de kan
opskrives i en rækkefølge. (De hele tal skrives i rækkefølgen: 0, 1, -1, 2, -2, ...)
Det betyder altså også, at der er 'lige så mange' primtal som der er naturlige tal.
Eller mere generelt, at enhver uendelig delmængde af de naturlige tal har
samme kardinaltal som de naturlige tal.
Udtrykket 'lige så mange' skal altså her forstås sådan, at det er muligt at
oprette en én-til-én parring mellem elementerne i mængderne. Tager vi fx
kvadrattallene, så er der jo netop ét kvadrattal til hvert af de naturlige
tal. Begrebet kardinaltal er altså knyttet til metoden med én-til-én parring
mellem elementerne i forskellige mængder.
Men der er naturligvis forskel på ovenstående mængder. Vi kan skrive
hvilket betyder, at de naturlige tal er en delmængde af de hele tal. Alle naturlige tal er også hele tal. Men
idet 0 og alle de negative tal ikke er med i de naturlige tal. Bruger vi
symbolet som betegnelse for kardinaltallet for mængden så gælder
altså
Diagonalbeviset
redigérI sine beviser fra 1874 og 1891 brugte Cantor mængder af bitstrenge og viste at mængden af alle mulige uendelige bitstrenge er ikke-tællelig.
Cantor betragter i sit bevis en uendelig numereret liste , hvor hvert element i listen er en uendelig bitstreng, altså en uendelig streng af 0 og 1.
Denne liste er tællelig, da den jo netop er skrevet op som en nummereret liste, hvorfor der er en én-til-én korrespondance med de naturlige tal:
(Af hensyn til det følgende er bit'ene i diagonalen fremhævet med fed!)
Cantor viste derefter på følgende måde, at sådan en ordnet liste ikke kan indeholde alle mulige kombinationener af 0 og 1.
Hver bit i denne mængde kan identificeres som , hvor betegner den n'te bit i den m'te streng. Altså er den 4. bit i den 6. streng. Her er altså og .
Det er nu muligt at opbygge en bitstreng på en sådan måde, at den bliver forskellig fra alle bitstrengene i : Den første bit i sættes forskellig fra den første bit i den første streng i S, den anden bit forskellig fra den anden bit i den anden streng, og generelt den n'te bit forskellig fra den n'te bit i den n'te streng. Det vil sige, at hvis indsættes et i og omvendt. Altså bliver for alle .
Med den givne liste bliver .
Da dette altså gøres for alle strenge i vil blive forskellig fra alle strenge i S. Thi hvis fx tænkes at være lig med ,
så skulle være lig med i modstrid med konstruktionen af .
Kort sagt er ikke med i den tællelige liste .
Dette argument gælder for alle mulige tællelige lister af uendelige bitstrenge!
Ikke-tællelige mængder
redigérVi definerer nu en mængde som består af alle uendelige bitstrenge. må altså indeholde både og , og da ikke optræder i den tællelige liste , må være ikke-tællelig og der kan derfor ikke oprettes en én-til-én korrespondance mellem alle elementerne i og de naturlige tal.
En fortolkning må være (Overvej!), at der er flere mulige uendelige bitstrenge end der er naturlige tal! Eller sagt på en anden og mere korrekt måde: Kardinaltallet for er større end kardinaltallet for (de naturlige tal).
Reelle tal
redigérMed udgangspunkt i dette gik Cantor nu videre for at vise, at heller ikke de reelle tal er tællelige. Beviset kommer til at bestå af to trin:
- Opbygning af en én-til-én korrespondance mellem og en uendelig delmængde af de reelle tal .
Her det åbne interval .
Da er ikke-tællelig, vil denne delmængde af heller ikke være tællelig, og det må da også gælde for hele ! - Afbildning af delmængden på hele det reelle tallegeme. (For at underbygge sidste påstand.)
Opbygning af én-til-én korrespondence mellem T og
redigérTil opbygning af denne én-til-én korrespondance skal vi finde en bijektiv afbildning fra T til .
Det kan startes med at omforme bitstrengene i til tal ved at sætte (nul komma) foran hver streng.
Ex foran strengen til tallet . Dette kan altså opfattes som en afbildning
der afbilder T ind på de binære reelle tal mellem nul og én.
For at få en bijektiv afbildning skal vi være sikre på, at alle tal mellem nul og én kan rammes og at der ikke er flere forskellige strenge,
der giver det samme tal. Da indeholder alle mulige uendelige strenge vil det være muligt at ramme alle de binære tal i det åbne interval
, men som vi skal se kan to forskellige strenge godt give det samme tal. Det problem må løses.
Eksempler
redigér
hvor betyder, at der nu blot følger uendeligt mange nuller.
Og der kan tænkes andre med tilfældige uendeligt varierende bitstrenge.
Men bitstrenge der ender på uendeligt mange 1-taller giver problemer:
Dette kan bl.a. vises på en følgende måde: (NB: At gange med 2 i det binære talsystem gøres ved at flytte kommaet en plads til højre)
Altså er
(Faktorerne er skrevet med decimaltal for at gøre det tydelige, hvad der sker.)
Andre eksempler
Altså er og
Dvs. at alle tal der ender på uendeligt mange 1-taller kan omskrives ved at ændre et foranstående 0 til 1 og alle de efterfølgende 1-taller til 0.
Men da allerede indeholder de strenge der ender på uendligt mange nuller, kan dem der ender på uendeligt mange ettaller blot fjernes.
(Dette er princippet. Der angives ikke nogen praktisk metode til at gøre dette. For hvordan finder man ud af, at et binært tal ender på uendeligt mange ettaller?)
I denne sammenhæng er det dog princippet der er det vigtigste! Man kan dog overbevise sig om, at det er følgende tal, der alle har to binære repræsentationer, én der ender på uendeligt mange nuller og én der ender på uendeligt mange ettaller:
Alt efter hvordan listen er skrevet op kan det være, at man ved hvor disse tal er :).
Fjerner så endeligt også og for at få et åbent interval (Begrundes senere.)
Med dette har vi nu i princippet oprettet en bijektiv afbildning:
Bijektiv afbilning:
redigérHer bruges der umiddelbart afbilder det åbne interval ind i .
Derefter kombineres dette med den bijektive afbildning
givet ved
hvor .
Den sammensatte funktion
giver så den bijektive afbildning .
(Derfor valgtes det åbne interval.)
Den samlede bijektive afbildning
fås så ved at bruge funktionen med til
Det betyder at og har samme kardinaltal og dette kaldes kontinuum-kardinaltallet.
Eksterne links
redigérHovedreference til denne artikel:
Cantor's Diagonal Argument: Proof and Paradox Arkiveret 28. marts 2014 hos Wayback Machine
En kort, virkelig god og letforståelig gennemgang af emnet:
Infinity: Cardinal Numbers af Bjorn Poonen Arkiveret 4. marts 2016 hos Wayback Machine