Cantors diagonalteorem

 

Anta vi skär en linje på två godtyckliga ställen    som i nedanstående figur.

 

Figur A1  Ett godtyckligt linjesegment

 

 

Vi skär sedan detta godtyckliga linjesegment exakt i mitten och kallar det vänstra linjesegmentet 0 och det högra 1. Proceduren kan upprepas inom varje nytt segment med konventionen att lägga till en nolla i varje block till vänster och en etta i varje till höger. Vi får då ett antal boxar enligt figurerna på nästa sida.

 

 

 

 

 

Figur A2-4  Kortare och kortare linjesegment ges benämningar

 

 

Även om det är uppenbart att vi inte kan fortsätta rita fler och fler figurer i all oändlighet är det lika uppenbart att vi kan göra det som ett tankeexperiment. Reglerna för benämning av de allt kortare segmenten på linjen är klara. De första tre upprepningarna av proceduren ger åtta segment unikt benämnda med nollor och ettor. Skulle vi fortsätta göra om proceduren ett oändligt antal gånger skulle segmenten bli oändligt små och med oändligt långa serier av ettor och nollor som "namn". Tanken är förstås att man kan ge all punkter på linjen en unik benämning så att de går att räkna. Cantors diagonalteorem visar att detta är omöjligt. Antalet punkter på ett godtyckligt linjesegment är fler än ett oändligt antal!

Vi tänker oss att vi listar hela den oändliga raden av oändliga serier av nollor och ettor. De motsvarar alla ett oändligt litet unikt segment på linjen. Vi kan lista alla möjliga kombinationer av ettor och nollor som i figuren.

 

                      Figur A5

1 0 0 0 0 0 0 . . 0 . . .        mot oändligheten

1 0 1 0 1 0 1 . . 1 . . .

1 0 1 1 0 1 1 . . 1 . . .

0 1 0 0 1 0 0 . . 0 . . .

0 1 0 1 0 1 0 . . 1 . . .

.

.

.

1 1 1 1 1 0 0 . . 1. . .

.

.                                  

0 1 0 1 1 . .  . 0 . . .

vi bildar en ny oändlig serie

                                              genom att byta varje understruken nolla mot en etta och tvärtom

mot oändligheten

Det intressanta med den nya serie ettor och nollor som vi bildar genom att omkasta hela serien i diagonalen är att trots att den unikt motsvarar en punkt (eller snarare ett oändligt litet segment) på linjen så finns denna serie inte med i den oändliga listan av alla möjliga serier, eftersom den skiljer sig på åtminstone ett ställe från alla serier i listan. Antalet unikt identifierbara ställen på linjesegmentet är alltså fler än vad som går att räkna; vilket skulle bevisas.