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.

${\displaystyle \mathbb {N} =\{1,2,3....\}}$ (De naturlige tal)

${\displaystyle \mathbb {Z} =\{...-2,-1,0,1,2,...\}}$ (De hele tal)

${\displaystyle \mathbb {P} =\{2,3,5,7,...\}}$ (Primtallene)

${\displaystyle \{0,1\}*=\{0,1,00,01,10,11,000,001,010,...\}}$ (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

${\displaystyle \mathbb {N} \subseteq \mathbb {Z} }$

hvilket betyder, at de naturlige tal er en delmængde af de hele tal. Alle naturlige tal er også hele tal. Men

${\displaystyle \mathbb {Z} \nsubseteq \mathbb {N} }$

idet 0 og alle de negative tal ikke er med i de naturlige tal. Bruger vi symbolet ${\displaystyle \sharp M}$ som betegnelse for kardinaltallet for mængden ${\displaystyle M}$ så gælder altså

${\displaystyle \sharp \mathbb {Z} =\sharp \mathbb {N} }$

${\displaystyle \sharp \mathbb {P} =\sharp \mathbb {N} }$

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 ${\displaystyle S=(s_{1},s_{2},s_{3},...)}$, 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:

${\displaystyle s_{1}=\mathbf {0} \;0\;0\;0\;0\;0\;0\;...}$

${\displaystyle s_{2}=1\;\mathbf {1} \;1\;1\;1\;1\;1\;...}$

${\displaystyle s_{3}=0\;1\;\mathbf {0} \;1\;0\;1\;0\;...}$

${\displaystyle s_{4}=1\;0\;1\;\mathbf {0} \;1\;0\;1\;...}$

${\displaystyle s_{5}=1\;1\;0\;1\;\mathbf {1} \;0\;1\;...}$

${\displaystyle s_{6}=0\;0\;1\;1\;0\;\mathbf {0} \;1\;...}$

${\displaystyle s_{7}=1\;0\;0\;1\;0\;0\;\mathbf {1} \;...}$

${\displaystyle ...}$

(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 ${\displaystyle s_{m,n}}$, hvor ${\displaystyle m,n}$ betegner den n'te bit i den m'te streng. Altså er ${\displaystyle s_{6,4}}$ den 4. bit i den 6. streng. Her er altså ${\displaystyle s_{6,4}=1}$ og ${\displaystyle s_{6,5}=0}$.

Det er nu muligt at opbygge en bitstreng ${\displaystyle s_{0}}$ på en sådan måde, at den bliver forskellig fra alle bitstrengene i ${\displaystyle S}$: Den første bit i ${\displaystyle s_{0}}$ 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 ${\displaystyle s_{n,n}=1}$ indsættes et ${\displaystyle 0}$ i ${\displaystyle s_{0,n}}$ og omvendt. Altså bliver ${\displaystyle s_{0,n}\neq s_{n,n}}$ for alle ${\displaystyle n}$.

Med den givne liste bliver ${\displaystyle s_{0}=1011010...}$.
Da dette altså gøres for alle strenge i ${\displaystyle S}$ vil ${\displaystyle s_{0}}$ blive forskellig fra alle strenge i S. Thi hvis ${\displaystyle s_{0}}$ fx tænkes at være lig med ${\displaystyle s_{10}}$, så skulle ${\displaystyle s_{10,10}}$ være lig med ${\displaystyle s_{0,10}}$ i modstrid med konstruktionen af ${\displaystyle s_{0}}$.

Kort sagt er ${\displaystyle s_{0}}$ ikke med i den tællelige liste ${\displaystyle S}$.

Dette argument gælder for alle mulige tællelige lister af uendelige bitstrenge!

Ikke-tællelige mængder

Vi definerer nu en mængde ${\displaystyle T}$ som består af alle uendelige bitstrenge. ${\displaystyle T}$ må altså indeholde både ${\displaystyle S}$ og ${\displaystyle s_{0}}$, og da ${\displaystyle s_{0}}$ ikke optræder i den tællelige liste ${\displaystyle S}$, må ${\displaystyle T}$ være ikke-tællelig og der kan derfor ikke oprettes en én-til-én korrespondance mellem alle elementerne i ${\displaystyle T}$ 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 ${\displaystyle T}$ er større end kardinaltallet for ${\displaystyle \mathbb {N} }$ (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:

1. Opbygning af en én-til-én korrespondance mellem ${\displaystyle T}$ og en uendelig delmængde af de reelle tal ${\displaystyle \mathbb {R} }$.
   Her det åbne interval ${\displaystyle (0,1)}$.
   Da ${\displaystyle T}$ er ikke-tællelig, vil denne delmængde af ${\displaystyle \mathbb {R} }$ heller ikke være tællelig, og det må da også gælde for hele ${\displaystyle \mathbb {R} }$!
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 ${\displaystyle (0,1)}$

Til opbygning af denne én-til-én korrespondance skal vi finde en bijektiv afbildning fra T til ${\displaystyle (0,1)}$. Det kan startes med at omforme bitstrengene i ${\displaystyle T}$ til tal ved at sætte ${\displaystyle 0,}$ (nul komma) foran hver streng. Ex foran strengen ${\displaystyle t=0111...}$ til tallet ${\displaystyle 0,t=0,0111...}$. Dette kan altså opfattes som en afbildning ${\displaystyle f:t\rightarrow (0,t)}$ 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 ${\displaystyle T}$ indeholder alle mulige uendelige strenge vil det være muligt at ramme alle de binære tal i det åbne interval ${\displaystyle (0,1)}$, men som vi skal se kan to forskellige strenge godt give det samme tal. Det problem må løses.

Eksempler

${\displaystyle {\begin{aligned}0,11100...&={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+{\frac {0}{16}}+...={\frac {7}{8}}\\0,01010...&={\frac {1}{4}}+{\frac {1}{16}}+{\frac {0}{32}}+...={\frac {5}{16}}\end{aligned}}}$

hvor ${\displaystyle +...}$ 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:

${\displaystyle {\begin{aligned}n=0,111...&={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+...=\sum \limits _{i=1}^{\infty }\left({\frac {1}{2}}\right)^{i}=1{\text{ !!!}}\end{aligned}}}$

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)

${\displaystyle {\begin{aligned}n&=0,111...\\2\cdot 0,111...&=1,111...=2\cdot n\\4\cdot 0,111...&=11,111...=4\cdot n\\4n-2n&=11,111...-1,11...=10,000...=2\\\Downarrow \\n&=1\end{aligned}}}$

Altså er ${\displaystyle 0,111...=1,00...}$

(Faktorerne er skrevet med decimaltal for at gøre det tydelige, hvad der sker.)

Andre eksempler

${\displaystyle {\begin{aligned}0,0111...&={\frac {1}{4}}+{\frac {1}{8}}+{\frac {1}{16}}+...=1-{\frac {1}{2}}={\frac {1}{2}}=0,100...\\0,1011...&={\frac {1}{2}}+{\frac {1}{8}}+{\frac {1}{16}}+...=1-{\frac {1}{4}}={\frac {1}{2}}+{\frac {1}{4}}=0,1100...\end{aligned}}}$

Altså er ${\displaystyle 0,0111...=0,100...}$ og ${\displaystyle 0,1011...=0,1100...}$

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 ${\displaystyle T}$ 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:

${\displaystyle 1,{\frac {1}{2}},{\frac {1}{4}},{\frac {3}{4}},{\frac {1}{8}},{\frac {3}{8}},{\frac {5}{8}},{\frac {7}{8}},{\frac {1}{16}},{\frac {3}{16}},...}$

Alt efter hvordan listen er skrevet op kan det være, at man ved hvor disse tal er :).
Fjerner så endeligt også ${\displaystyle 0=0,00...}$ og ${\displaystyle 1=0,111..}$ for at få et åbent interval ${\displaystyle (0,1)}$ (Begrundes senere.)
Med dette har vi nu i princippet oprettet en bijektiv afbildning: ${\displaystyle g:T\rightarrow (0,1)}$

Bijektiv afbilning: ${\displaystyle (0,1)\rightarrow \mathbb {R} }$

Her bruges ${\displaystyle \tan(x)}$ der umiddelbart afbilder det åbne interval ${\displaystyle (-{\frac {\pi }{2}},{\frac {\pi }{2}})}$ ind i ${\displaystyle \mathbb {R} }$.
Derefter kombineres dette med den bijektive afbildning ${\displaystyle h:(0,1)\rightarrow (-{\frac {\pi }{2}},{\frac {\pi }{2}})}$
givet ved
${\displaystyle h(x)=\pi \cdot x-{\frac {\pi }{2}}}$ hvor ${\displaystyle x\in (0,1)}$.

Den sammensatte funktion

${\displaystyle {\begin{aligned}\tan(h(x))&=\tan \left(\pi \cdot x-{\frac {\pi }{2}}\right)\end{aligned}}}$

giver så den bijektive afbildning ${\displaystyle (0,1)\rightarrow \mathbb {R} }$.
(Derfor valgtes det åbne interval.)

Den samlede bijektive afbildning

${\displaystyle T\rightarrow \mathbb {R} }$ fås så ved at bruge funktionen ${\displaystyle g}$ med ${\displaystyle x=g(t)}$ til

${\displaystyle {\begin{aligned}\tan(h(g(t)))&=\tan \left(\pi \cdot g(t)-{\frac {\pi }{2}}\right)\end{aligned}}}$

Det betyder at ${\displaystyle T}$ og ${\displaystyle \mathbb {R} }$ har samme kardinaltal og dette kaldes kontinuum-kardinaltallet.

Eksterne links

Hovedreference 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

Se også

• Tællelig mængde
• Ikke-tællelig