Cantors diagonalbevis

(Omdirigeret fra Cantor's 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ængderRediger

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.

KardinaltalRediger

Cantor indførte begrebet kardinaltal til beskrivelse af størrelsen/mægtigheden af mængder, specielt med henblik på uendelige mængder.

DefinitionRediger

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å

 
 

DiagonalbevisetRediger

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ængderRediger

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 talRediger

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:

  1. 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  !
  2. Afbildning af delmængden på hele det reelle tallegeme. (For at underbygge sidste påstand.)

Opbygning af én-til-én korrespondence mellem T og  Rediger

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.

EksemplerRediger

 

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:  Rediger

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 linksRediger

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åRediger