Cantors diagonalargument: varför de reella talen inte kan listas

Tänk dig att någon räcker dig en lista. Det är en oändlig lista, och personen hävdar att den innehåller varje reellt tal mellan 0 och 1. Inte ett urval, inte ett stickprov: varenda ett, prydligt indexerat som r1, r2, r3, och så vidare, i evighet.

Georg Cantors svar, år 1891, var detta: vilken lista du än ger mig kan jag läsa av ett tal som inte står på den. Konstruktionen tar ungefär trettio sekunder att beskriva. Konsekvensen tog årtionden för matematiker att smälta, för den betyder att oändlighet kommer i mer än en storlek.

Räkna och lista

Innan diagonaldraget hjälper det att vara precis med vad "uppräknelig" betyder. En mängd är uppräknelig om du kan ge varje element en unik naturlig-tals-etikett: ett första element, ett andra, ett tredje, och så vidare, utan rest. De naturliga talen själva är uppräkneliga per definition. Heltalen också (lista dem som 0, 1, -1, 2, -2, ...) och till och med de rationella, även om det att lista varje bråk kräver ett fiffigt sicksackmönster.

Cantors argument visar att de reella talen mellan 0 och 1 är verkligt annorlunda: ingen märkning finns, hur du än försöker. Det är inget misslyckande för fantasin. Det är ett bevis på att uppgiften är omöjlig.

Anta att listan finns

Argumentet är ett motsägelsebevis. Börja med att ge motståndaren allt hen vill: anta att en komplett lista över varje reellt tal i (0, 1) faktiskt finns. Skriv varje tal som en oändlig decimalutveckling.

Listan kan börja så här:

• $r_{1} = 0.14159265\dots$
• $r_{2} = 0.73205080\dots$
• $r_{3} = 0.00000000\dots$
• $r_{4} = 0.27182818\dots$
• $r_{5} = 0.91415926\dots$
• ...

Varje post fortsätter i evighet. Listan fortsätter i evighet. Och enligt antagandet dyker varje reellt tal mellan 0 och 1 upp någonstans på den.

Se nu vad som händer när du läser längs diagonalen.

Att läsa diagonalen

Titta på den första decimalsiffran i r1, den andra decimalsiffran i r2, den tredje i r3, och så vidare. I exemplet ovan är de diagonalsiffrorna: 1, 3, 0, 2, 9, ...

Du bygger nu ett nytt tal, kalla det d, en siffra i taget. Regeln: för varje diagonalsiffra, välj en annan siffra, men undvik medvetet 0 och 9.

Diagonalsiffrorna är 1, 3, 0, 2, 9. Regeln ger 2, 4, 1, 3, 8. Alltså $d = 0.24138\dots$

Att undvika 0 och 9 är en liten men nödvändig vakt. Vissa reella tal har två decimalframställningar: 0.4999... och 0.5000... namnger samma punkt på tallinjen. Att vända en siffra till 0 eller 9 skulle kunna landa dig på det "andra namnet" för ett tal som redan står på listan, vilket grumlar argumentet. Genom att stanna i intervallet 1 till 8 för varje vänd siffra garanterar du att d har exakt en decimalutveckling, och jämförelsen nedan är ren.

Det nya talet skiljer sig från varje post

Här är utdelningen.

Motsägelsen är skarp: vi antog att listan var komplett, och vi producerade ett reellt tal som inte står på den. Antagandet måste vara falskt. Ingen komplett lista över de reella talen mellan 0 och 1 kan finnas.

Vad det här egentligen säger

Matematiker säger att de naturliga talen har kardinalitet alef-noll (skrivet med den hebreiska bokstaven alef: det första transfinita kardinaltalet). De reella talen har en strikt större kardinalitet, ibland skriven som c eller som 2 upphöjt till alef-noll. Cantors argument är det som fastslår att dessa två oändligheter inte har samma storlek.

Detta var djupt kontroversiellt när Cantor publicerade det. Vissa kollegor avfärdade resultatet som en kuriositet eller ett fel. Det är ingetdera. Det sitter i grunden för hur matematiker tänker om mängder, kardinalitet och den reella tallinjens struktur, och det kopplar direkt till frågor om vad som kan och inte kan beräknas (se också beviset i Goodsteins sats för ett annat fall där något bevisbart sant trycker mot gränserna för formella system).

Varför diagonalen fungerar

Det som gör argumentet elegant är specificiteten. Du gissar inte efter ett saknat tal eller vädjar till vag intuition om hur stora de reella talen är. Du läser av exakt vilka positioner på listan varje post styr, och bygger sedan ett tal som undviker varje post precis på den positionen.

Listan själv talar om var du ska titta. Varje post på listan räcker dig en koordinat, sin egen diagonalsiffra, och konstruktionen vänder de koordinaterna till ett tal som listan inte kan innehålla.

Enkelheten är bedräglig. Det finns inget här som kräver att du vet något om posterna på listan. Det spelar ingen roll vilka tal som står på den, i vilken ordning, eller hur de valdes. Argumentet är universellt: välj vilken lista av reella tal som helst, och diagonalkonstruktionen producerar ett reellt tal som inte står på den.

Zenen i det

Cantors diagonalargument sitter i en lång tradition av matematiska resultat som känns som om de inte borde fungera. Du stirrar på beviset och väntar på tricket, det dolda antagandet, platsen där logiken halkar. Den finns inte. Beviset är precis så enkelt som det ser ut.

Det det ber dig acceptera är märkligare än beviset självt: att "oändlig" inte är en enda destination. Heltalen och de reella talen är båda oändliga, men de är oändliga på kategoriskt olika sätt. Diagonalargumentet är skiljelinjen.

För en djupare känsla av hur oändliga samlingar kan bete sig märkligt är strukturen hos oändliga decimaler ett bra nästa steg, eller hur gränsvärden fungerar när följder närmar sig ett värde för alltid utan att nå det. Diagonalargumentet hör till samma familj: en precis, tålmodig blick på vad som händer vid kanten av det oändliga, där intuitionen behöver ett bevis för att hållas ärlig.

Oändlighet är inte en sak. Det är nyheten. Argumentet som levererar den ryms på en halv sida.