Cantors diagonalargument

Cantors første diagonalargument

I eksemplet nedenfor bruges to af de enkleste uendelige mængder, nemlig de naturlige tal og de positive brøker. Ideen er at vise, at begge disse mængder, N {\displaystyle \mathbb {N} } og Q + {\displaystyle \mathbb {Q^{+}} } har den samme kardinalitet.

Først tilpasses brøkerne i et array på følgende måde:

1 1 1 1 1 2 1 2 1 3 1 1 4 1 5 ⋯ 2 1 2 2 2 2 2 2 3 2 2 2 2 4 2 5 ⋯ 3 1 1 3 2 2 3 3 3 3 3 3 3 4 3 3 3 4 3 5 ⋯ 4 1 4 1 4 2 4 3 4 4 4 4 4 5 ⋯ 5 1 5 2 5 3 5 3 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccccc}{\tfrac {1}{1}{1}}}&&{\tfrac {1}{2}}}&&&{\tfrac {1}{3}}}&&&{\tfrac {1}{4}}}&&&{\tfrac {1}{4}}}&{\tfrac {1}{5}}}&\cdots \\&&&&&&&&&\\\\{\tfrac {2}{1}}}&&{\tfrac {2}{2}{2}}}&&&{\tfrac {2}{3}}}&&&{\tfrac {2}{4}}}&&&{\tfrac {2}{5}}}&\cdots \\&&&&&&&&&\\{\tfrac {3}{1}}}&&&{\tfrac {3}{2}}}&&{\tfrac {3}{3}{3}}}&&&{\tfrac {3}{4}}}&&&{\tfrac {3}{5}}}&\cdots \\&&&&&&&&&&&\\\{\tfrac {4}{1}}}&&{\tfrac {4}{2}}}&&{\tfrac {4}{3}}}&&{\tfrac {4}{4}{4}}}&&{\tfrac {4}{5}}}&&\cdots \\&&&&&&&&&\\\\{\tfrac {5}{1}}}&&{\tfrac {5}{2}}}&&{\tfrac {5}{3}}}&&&&{\tfrac {5}{4}}}&&{\tfrac {5}{5}{5}}}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\end{array}}}}

Derefter tælles tallene som vist. Brøker, som kan forenkles, udelades:

1 1 ( 1 ) → 1 2 ( 2 ) 1 3 ( 5 ) → 1 4 ( 6 ) 1 5 ( 11 ) → ↙ ↙ 2 1 ( 3 ) 2 2 ( ⋅ ) 2 3 ( 7 ) 2 4 ( ⋅ ) 2 5 ⋯ ↓ ↙ 3 1 ( 4 ) 3 2 ( 8 ) 3 3 ( ⋅ ) 3 4 3 3 5 ⋯ ↙ 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 4 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 3 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclclclclc}{\tfrac {1}{1}}}}\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{2}}}\ _{\color {Blue}(2)}&&&{\tfrac {1}{3}}}\ _{\color {Blue}(5)}&&{\tfrac {1}{3}}\ _{\color {Blue}(5)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{4}}}}\ _{\color {Blue}(6)}&&&{\tfrac {1}{5}}}\ _{\color {Blue}(11)}&&{\tfrac {1}{5}}}{\color {MidnightBlue}\rightarrow }\&&{{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&&{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&&\\\\{\tfrac {2}{1}}}}\ _{\color {Blue}(3)}&&&{\tfrac {2}{2}}}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {2}{3}}}\ _{\color {Blue}(7)}&&&{\tfrac {2}{4}}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {2}{5}}}&\cdots \\{{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&{\color {MidnightBlue}\swarrow }&&&{{\color {MidnightBlue}\nearrow }&&&&\\\\{\tfrac {3}{1}}}}\ _{\color {Blue}(4)}&&&{\tfrac {3}{2}}}\ _{\color {Blue}(8)}&&&{\tfrac {3}{3}{3}}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {3}{4}}}&&&&{\tfrac {3}{5}}}&\cdots \\&&{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&&&&&\\{{\tfrac {4}{1}}}\ _{\color {Blue}(9)}&&&{\tfrac {4}{2}}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {4}{3}}}&&&{\tfrac {4}{4}{4}}}}&&&{\tfrac {4}{5}}}&\cdots \\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&&&&&\\\{\tfrac {5}{1}}}\ _{\color {Blue}(10)}&&&{\tfrac {5}{2}}}&&&{\tfrac {5}{3}}}&&{\tfrac {5}{4}}}&&{\tfrac {5}{4}}}&{\tfrac {5}{5}}}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\end{array}}}}

På den måde tælles brøkerne med:

1 2 3 3 4 5 5 6 7 8 8 9 9 10 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 2 3 1 3 1 4 2 3 3 3 2 4 4 5 1 5 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccc}{color {Blue}1}&{\color {Blue}2}&{{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}11}&{\color {Blue}11}{\color {Blue}\cdots }\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\[3pt]1&{\tfrac {1}{2}}}&2&3&&{\tfrac {1}{3}}}&{\tfrac {1}{4}}}&{\tfrac {2}{3}}}}&{\tfrac {3}{2}}}&4&5&{\tfrac {1}{5}}}&\cdots \\\end{array}}}}

Ved at udelade brøker, som stadig kan forenkles, er der en bijektion, som forbinder hvert element i de naturlige tal med et element i brøkerne:

For at vise, at alle naturlige tal og brøker har samme kardinalitet, skal elementet 0 tilføjes; efter hver brøk tilføjes dens negativ;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 - 1 1 2 - 1 2 2 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 2 3 - 2 3 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccccccccc}{\color {Blue}1}}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}12}&{\color {Blue}13}&{\color {Blue}14}&{\color {Blue}15}&{\color {Blue}15}&{\color {Blue}\cdots }\\[3pt]{\color {MidnightBlue}\downarrow }&{{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\[3pt]0&1&-1&{\tfrac {1}{2}}}&-{\tfrac {1}{2}}}&&{\tfrac {1}{2}}}&2&-2&3&-3&{\tfrac {1}{3}}}&-{\tfrac {1}{3}}}&{\tfrac {1}{4}}}&-{\tfrac {1}{4}}}&{\tfrac {2}{3}}}&-{\tfrac {2}{3}}}&\cdots \\\\end{array}}}}

På den måde er der en komplet bijektion, som knytter en brøk til hvert naturligt tal. Med andre ord: begge mængder har den samme kardinalitet. I dag kaldes mængder, der har det samme antal elementer som mængden af naturlige tal, for tællelige. Mængder, der har færre elementer end de naturlige tal, kaldes højst tællelige. Med denne definition er mængden af rationale tal/brøker tællelig.

Uendelige mængder har ofte egenskaber, som strider mod intuitionen: David Hilbert viste dette i et eksperiment, som kaldes Hilberts paradoks på Grand Hotel.

Reelle tal

Mængden af reelle tal har ikke samme kardinalitet som mængden af naturlige tal; der er flere reelle tal end naturlige tal. Ovennævnte idé har påvirket hans bevis. I sin artikel fra 1891 betragtede Cantor mængden T af alle uendelige sekvenser af binære tal (dvs. at hvert tal er nul eller et).

Han begynder med et konstruktivt bevis for følgende sætning:

Hvis s₁ , s₂ , ... , s_n , ... er en hvilken som helst opregning af elementer fra T, er der altid et element s i T, som ikke svarer til noget s_n i opregningen.

For at bevise dette, skal man give en opregning af elementer fra T, som f.eks.

Sekvensen s konstrueres ved at vælge det første ciffer som komplement til det første ciffer i s₁ (0'er byttes ud med 1'er og omvendt), det andet ciffer som komplement til det andet ciffer i s₂ , det tredje ciffer som komplement til det tredje ciffer i s₃ , og generelt for hvert n, det n^th ciffer som komplement til det n^th ciffer i s_n . I eksemplet giver dette:

Ved konstruktionen adskiller s sig fra hvert s_n , da deres n^th cifre er forskellige (fremhævet i eksemplet). Derfor kan s ikke optræde i opregningen.

Baseret på denne sætning bruger Cantor derefter et modbevis for at vise, at:

Mængden T er utællelig.

Han antager, at T var tællelig. I så fald kunne alle dens elementer skrives som en opregning s₁ , s₂ , ... , s_n , ... ... . Hvis man anvender den foregående sætning på denne opregning, vil man få en sekvens s, der ikke tilhører opregningen. Men s var et element i T og burde derfor være med i opregningen. Dette er i modstrid med den oprindelige antagelse, så T må være utællelig.