Cantors diagonaalargument: waarom de reële getallen niet op een lijst passen

Stel dat iemand je een lijst geeft. Het is een oneindige lijst, en die persoon beweert dat hij elk reëel getal tussen 0 en 1 bevat. Geen steekproef, geen selectie: elk afzonderlijk, netjes geïndexeerd als r1, r2, r3, enzovoort, eindeloos doorlopend.

Georg Cantors antwoord, in 1891, was dit: welke lijst je me ook geeft, ik kan een getal aflezen dat er niet op staat. De constructie kost ongeveer dertig seconden om te beschrijven. De consequentie kostte wiskundigen decennia om te verwerken, omdat het betekent dat oneindigheid in meer dan één grootte voorkomt.

Tellen en opsommen

Voor de diagonaalzet helpt het om precies te zijn over wat "aftelbaar" betekent. Een verzameling is aftelbaar als je elk element een uniek natuurlijk-getallabel kunt geven: een eerste element, een tweede, een derde, enzovoort, zonder rest. De natuurlijke getallen zelf zijn per definitie aftelbaar. De gehele getallen ook (som ze op als 0, 1, -1, 2, -2, ...) en zelfs de rationale, hoewel het opsommen van elke breuk een slim zigzagpatroon vraagt.

Cantors argument laat zien dat de reële getallen tussen 0 en 1 écht anders zijn: er bestaat geen nummering, hoe je het ook probeert. Dat is geen falen van de verbeelding. Het is een bewijs dat de taak onmogelijk is.

Neem aan dat de lijst bestaat

Het argument is een bewijs uit het ongerijmde. Begin met de tegenstander alles te gunnen wat die wil: neem aan dat er een complete lijst van elk reëel getal in (0, 1) bestaat. Schrijf elk getal als oneindige decimale ontwikkeling.

De lijst zou zo kunnen beginnen:

• $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$
• ...

Elk item loopt eeuwig door. De lijst loopt eeuwig door. En volgens de aanname verschijnt elk reëel getal tussen 0 en 1 ergens erop.

Kijk nu wat er gebeurt als je de diagonaal afleest.

De diagonaal lezen

Kijk naar het eerste decimale cijfer van r1, het tweede decimale cijfer van r2, het derde van r3, enzovoort. In het voorbeeld hierboven zijn die diagonaalcijfers: 1, 3, 0, 2, 9, ...

Je bouwt nu een nieuw getal, noem het d, cijfer voor cijfer. De regel: kies voor elk diagonaalcijfer een ander cijfer, maar vermijd bewust 0 en 9.

De diagonaalcijfers zijn 1, 3, 0, 2, 9. De regel toepassen levert 2, 4, 1, 3, 8. Dus $d = 0.24138\dots$

Het vermijden van 0 en 9 is een kleine maar noodzakelijke waarborg. Sommige reële getallen hebben twee decimale schrijfwijzen: 0.4999... en 0.5000... noemen hetzelfde punt op de getallenlijn. Een cijfer naar 0 of 9 omdraaien zou je op de "andere naam" van een getal dat al op de lijst staat kunnen zetten, wat het argument vertroebelt. Door voor elk omgedraaid cijfer in het bereik 1 tot en met 8 te blijven, garandeer je dat d precies één decimale ontwikkeling heeft, en de vergelijking hieronder schoon is.

Het nieuwe getal verschilt van elk item

Hier is de uitbetaling.

De tegenspraak is scherp: we namen aan dat de lijst compleet was, en we produceerden een reëel getal dat er niet op staat. De aanname moet onjuist zijn. Er kan geen complete lijst van de reële getallen tussen 0 en 1 bestaan.

Wat dit eigenlijk zegt

Wiskundigen zeggen dat de natuurlijke getallen kardinaliteit alef-nul hebben (geschreven met de Hebreeuwse letter alef: het eerste transfiniete kardinaalgetal). De reële getallen hebben een strikt grotere kardinaliteit, soms geschreven als c of als 2 tot de macht alef-nul. Cantors argument is wat vaststelt dat deze twee oneindigheden niet dezelfde grootte hebben.

Dit was diep controversieel toen Cantor het publiceerde. Sommige collega's wezen het resultaat af als curiositeit of fout. Het is geen van beide. Het zit aan de basis van hoe wiskundigen denken over verzamelingen, kardinaliteit en de structuur van de reële getallenlijn, en het sluit direct aan op vragen over wat wel en niet berekend kan worden (zie ook het bewijs in de stelling van Goodstein voor een ander geval waarin iets bewijsbaar waars tegen de grenzen van formele systemen duwt).

Waarom de diagonaal werkt

Wat het argument elegant maakt is de specificiteit. Je raadt niet naar een ontbrekend getal en doet geen beroep op vage intuïtie over hoe groot de reële getallen zijn. Je leest precies af welke posities op de lijst elk item beheerst, en bouwt dan een getal dat elk item precies op die positie ontwijkt.

De lijst zelf vertelt je waar je moet kijken. Elk item op de lijst geeft je één coördinaat, zijn eigen diagonaalcijfer, en de constructie draait die coördinaten om tot een getal dat de lijst niet kan bevatten.

De eenvoud is bedrieglijk. Er is hier niets dat vereist dat je iets weet over de items op de lijst. Het maakt niet uit welke getallen erop staan, in welke volgorde, of hoe ze gekozen zijn. Het argument is universeel: pak willekeurig welke lijst van reële getallen, en de diagonaalconstructie produceert een reëel getal dat er niet op staat.

De zen ervan

Cantors diagonaalargument zit in een lange traditie van wiskundige resultaten die aanvoelen alsof ze niet zouden moeten werken. Je staart naar het bewijs en wacht op de truc, de verborgen aanname, de plek waar de logica glijdt. Die is er niet. Het bewijs is precies zo eenvoudig als het eruitziet.

Wat het je vraagt te accepteren is vreemder dan het bewijs zelf: dat "oneindig" geen enkele bestemming is. De gehele getallen en de reële getallen zijn beide oneindig, maar ze zijn oneindig op categorisch verschillende manieren. Het diagonaalargument is de scheidslijn.

Voor een dieper gevoel van hoe oneindige collecties zich vreemd kunnen gedragen is de structuur van oneindige decimalen een goed volgend punt, of hoe limieten werken wanneer rijen eeuwig een waarde naderen zonder die te bereiken. Het diagonaalargument hoort in dezelfde familie: een precieze, geduldige blik op wat er gebeurt aan de rand van het oneindige, waar intuïtie een bewijs nodig heeft om eerlijk te blijven.

Oneindigheid is niet één ding. Dat is het nieuws. Het argument dat het aflevert past op een halve pagina.