Cantors teorem
Beviset för att det finns mängder större än oändligheten fascinerade mig redan som barn. Det är ett av ganska få matematiska bevis, där det inte behövs några egentliga förkunskaper i matematik för att förstå det, men där bevisets resultat ändå är oerhört fascinerande och svårt att intuitivt ta till sig.
Man skiljer alltså mellan uppräkneligt stora oändligheter och ouppräkneligt stora oändligheter. Men hur kan något vara större än oändligheten? Det är precis det beviset går ut på att visa.
En typisk oändlig mängd är mängden av naturliga heltal. Den börjar med 1, 2, 3, 4… och så vidare, och den tar aldrig slut. Vi kan alltid lägga till +1 och få ett nytt element i mängden. Detta är en uppräkneligt oändlig mängd.
Låt oss kalla denna mängda av naturliga heltal för S.
Låt os sedan bilda mängden S´, som vi definierar som mängden av alla delmängder av S.
Mängden S´ har alltså inte tal som element, utan delmängder av S.
Exempel på element i S´ är: {1,2}, {1,3}, {1,2,3}, {2,3,4},{12,14}, … och så vidare.
Lår oss nu tillämpa principen reductio ad absurdum, vi antar att mängden S´ bara är uppräkneligt oändlig, och visar att det leder till en motsägelse. Om vi lyckas med det måste mängden således vara större än så.
Vi antar alltså att S´ är uppräkneligt oändlig. För två uppräkneligt oändliga mängder råder en ett-till-ett-korrespondens mellan dem. I så fall kan vi använda elementen i S för att numrera elementen i S´, eftersom båda mängderna är uppräkneligt oändliga.
Vi radar upp elementen i S´ i en godtycklig ordning och numrerar dem 1, 2, 3, 4 och så vidare. Det kan till exempel se ut så här:
1 2 3 4 …456
{1,2} {1,3} {1,2,3} {2,3,4} …{12,14}
Vi kan snabbt konstatera att numreringssiffrorna kan delas in i två kategorier, dels de numreringssiffror som själva är med i mängden som de numrerar, dels de som inte är med i mängden de numrerar.
Siffran 1 i exemplet ovan tillhör den första kategorin, siffran 2 tillhör den andra.
Således kan vi skapa en ny mycket speciell mängd, vi kallar den X = mängden av alla naturliga heltal som inte är med i den mängden de numrerar.
Vad är X för slags mängd? Jo, en delmängd av S. Då måste X finnas med som element i S´, eftersom S´ är mängden av alla delmängder av S. Alltså måste ju X finnas med någonstans i den sekvens av element som vi radar upp ur S. Alltså:
1 2 3 4 N …456
{1,2} {1,3} {1,2,3} {2,3,4} X …{12,14}
Eftersom vi har antagit att S´ är uppräkneligt oändlig, så måste X ha fått ett nummer, N.
Nu kommer knäckfrågan: Om mängden X har fått ett nummer, N, så måste N antingen vara med i X, eller inte.
Antag att N är med i X: Men själva definitionen av X är ju alla naturliga tal som inte är med i den mängden de numrerar. Alltså kan N inte vara med i X.
Antag då att N inte är med i X. Men definitionen av X säger ju att då borde N vara med i X.
Vi drar slutsatsen att N inte existerar, det vill säga X kan inte ha fått något nummer. X ”blev över” när vi radade upp alla element i S´.
Eftersom detta tankeexperiment bygger på en helt godtycklig uppräkning av elementen i S´, betyder det att det alltid kommer bli minst ett element X över. Mängden S´ är alltså större än mängden av de naturliga heltalen, S.
S´ är ouppräkneligt stor. Quod erat demonstrandum, QED (Vilket skulle bevisas).
Senaste kommentarerna