Cantors diagonalargument

Cantors första diagonalargument

I exemplet nedan används två av de enklaste oändliga mängderna, nämligen de naturliga talen och de positiva bråken. Tanken är att visa att båda dessa mängder, N {\displaystyle \mathbb {N} } och Q + {\displaystyle \mathbb {Q^{{+}} } har samma kardinalitet.

Först anpassas bråken i en matris enligt följande:

1 1 1 1 1 2 1 3 1 1 4 1 5 ⋯ 2 1 2 2 2 2 2 3 2 2 2 4 2 5 ⋯ 3 1 1 3 2 3 3 3 3 3 3 4 3 3 5 ⋯ 4 1 4 2 4 3 4 4 4 4 5 ⋯ 5 1 5 2 5 3 5 4 5 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccccc}{\tfrac {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}}}&&&{\tfrac {3}{4}}}&&&{\tfrac {3}{5}}&\cdots \\&&&&&&&&&&\\\\tfrac {4}{1}}&&{\tfrac {4}{2}}}&&{\tfrac {4}{3}}}&&{\tfrac {4}{4}}}&&{\tfrac {4}{5}}}&&{\tfrac {4}{5}}&\cdots \\&&&&&&&&&\\\\{\tfrac {5}{1}}&&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}}&&&{\tfrac {5}{4}}}&&{\tfrac {5}{5}}}&\cdots \\\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\end{array}}}

Därefter räknas siffrorna, enligt bilden. Bråk som kan förenklas utelämnas:

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}{lclclclclclc}{\tfrac {1}{1}}}\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{2}}}\ _{\color {Blue}(2)}&&&{\tfrac {1}{3}}}\ _{\color {Blue}(5)}&&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{4}}}\ _{\color {Blue}(6)}&&&{\tfrac {1}{5}}}\ _{\color {Blue}(11)}&&{\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}}}}&&{\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}{5}}}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\end{array}}}}

På så sätt räknas bråken:

1 2 3 4 4 5 6 7 8 9 10 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 2 3 1 3 1 4 2 3 3 3 2 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}\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 }&{Färg färg av medelblått, nedåtgående pilar och färg av medelblått, nedåtgående pilar och färg av medelblått, nedåtgående pilar och färg av medelblått, nedåtgående pilar och färg av medelblått, nedåtgående pilar och färg av medelblått, nedåtgående pilar.{\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}}}

Genom att utelämna bråk som fortfarande kan förenklas finns det en övergång som associerar varje element i de naturliga talen med ett element i bråken:

För att visa att alla naturliga tal och bråk har samma kardinalitet måste elementet 0 läggas till; efter varje bråk läggs dess negativ till;

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}{cccccccccccccccccccc}{\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}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 }&{Färg färg: MidnightBlue Downarrow & MidnightBlue Downarrow & MidnightBlue Downarrow & MidnightBlue Downarrow & MidnightBlue Downarrow & MidnightBlue Downarrow & 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}}}&&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å så sätt finns det en fullständig bijektion som associerar en bråkdel till varje naturligt tal. Med andra ord: båda uppsättningarna har samma kardinalitet. Idag kallas mängder som har samma antal element som mängden naturliga tal för räknebara. Mängder som har färre element än de naturliga talen kallas högst räkningsbara. Med den definitionen är mängden rationella tal/bråk räknbara.

Oändliga mängder har ofta egenskaper som strider mot intuitionen: David Hilbert visade detta i ett experiment som kallas Hilberts paradox på Grand Hotel.

Reella tal

Mängden reella tal har inte samma kardinalitet som de naturliga talen; det finns fler reella tal än naturliga tal. Den idé som beskrivs ovan påverkade hans bevis. I sin artikel från 1891 betraktade Cantor mängden T av alla oändliga sekvenser av binära siffror (dvs. varje siffra är noll eller ett).

Han börjar med ett konstruktivt bevis för följande sats:

Om s₁ , s₂ , ... , s_n , ... är en uppräkning av element från T, finns det alltid ett element s i T som inte motsvarar något s_n i uppräkningen.

För att bevisa detta kan vi ge en uppräkning av element från T, som t.ex.

Sekvensen s konstrueras genom att välja den första siffran som komplement till den första siffran i s₁ (genom att byta ut 0 mot 1 och vice versa), den andra siffran som komplement till den andra siffran i s₂ , den tredje siffran som komplement till den tredje siffran i s₃ , och i allmänhet för varje n, den n^th som komplement till den n^th siffran i s_n . I exemplet ger detta:

Genom konstruktionen skiljer sig s från varje s_n , eftersom deras n^th siffror skiljer sig åt (markerade i exemplet). Därför kan s inte förekomma i uppräkningen.

Baserat på denna sats använder Cantor sedan ett motsägelsebevis för att visa att:

Mängden T är oräknelig.

Han antar att T är räkningsbar, för att motbevisa detta. I så fall kan alla dess element skrivas som en uppräkning s₁ , s₂ , ... , s_n , ... ... . Om man tillämpar föregående sats på denna uppräkning skulle man få fram en sekvens s som inte hör till uppräkningen. s var dock ett element i T och borde därför finnas med i uppräkningen. Detta motsäger det ursprungliga antagandet, så T måste vara oräknelig.