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 
Man 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 
Cantor indførte begrebet kardinaltal til beskrivelse af størrelsen/mægtigheden
af mængder, specielt med henblik på uendelige mængder.

Definition 
To 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 
I 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 
Vi 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 
Med 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  
Til 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 

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:  
Her 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 
Hovedreference til denne artikel:
Cantor's Diagonal Argument: Proof and Paradox 

En kort, virkelig god og letforståelig gennemgang af emnet:
Infinity: Cardinal Numbers af Bjorn Poonen

Se også 
 Tællelig mængde
 Ikke-tællelig

Mængdelære