De stelling van Goodstein: de rij die explodeert en toch altijd naar nul terugkeert
Kies een geheel getal. Een willekeurig geheel getal. Volg nu een regel van twee stappen, steeds opnieuw, en kijk naar het resultaat. Voor bijna elke startwaarde die je kiest, raast de rij omhoog voorbij een googol, voorbij getallen die het aantal atomen in het waarneembare heelal dwarven, voorbij alles wat je in een leven zou kunnen opschrijven. En toch komt ze bewijsbaar altijd terug naar nul.
Dat is de stelling van Goodstein, en de eerste keer dat je haar hoort klinkt ze als een truc. De regel is niet ingewikkeld, de getallen zijn gewoon, en de uitspraak is schoon. Toch had de reden waarom ze waar is decennia geen thuis in de gewone rekenkunde. Dit artikel vraagt je niet een logisch bewijs te volgen. In plaats daarvan toont het je het beeld eronder, en zodra je dat ziet, stopt de stelling mysterieus te zijn.
De regel is bijna kinderlijk eenvoudig
Je start met een geheel getal en een basis, beginnend bij basis 2. Bij elke stap doe je twee dingen: eerst herschrijf je het huidige getal in zogenaamde hereditaire basis-n-notatie; daarna vervang je elk voorkomen van de basis n door n+1, en trek je 1 af. Ga dan naar de volgende basis en herhaal.
Het ophogen-en-aftrekken klinkt mild. De basis van 2 naar 3 ophogen voelt als een kleine verandering. 1 aftrekken voelt alsof het het getal zou moeten intomen. Je zult zo zien waarom geen van beide intuïties het contact met hereditaire notatie overleeft.
Kijk hoe ze explodeert
Start met 4. In hereditaire basis 2 is dat . Verhoog elke 2 naar 3 en trek 1 af: je krijgt min 1, wat 26 is. Schrijf 26 nu in hereditaire basis 3, verhoog naar basis 4, trek 1 af, en je krijgt 41. Ga door.
| Step | Base | Written in that base | Value |
|---|---|---|---|
| 1 | 2 | 2² | 4 |
| 2 | 3 | 2·3² + 2·3 + 2 | 26 |
| 3 | 4 | 2·4² + 2·4 + 1 | 41 |
| 4 | 5 | 2·5² + 2·5 | 60 |
| 5 | 6 | 2·6² + 6 + 5 | 83 |
| 6 | 7 | 2·7² + 7 + 4 | 109 |
De rij die bij 4 start loopt: 4, 26, 41, 60, 83, 109, en blijft vanaf daar klimmen. Zelfs dit bescheiden begin groeit een opmerkelijk lange tijd voordat hij uiteindelijk daalt. Start in plaats daarvan vanaf 19, en de getallen bereiken hoogtes die fysiek niet opschrijfbaar zijn. Het aantal stappen voordat de rij zelfs maar begint om te keren is groter dan het aantal atomen in het waarneembare heelal. Als je de berekening bij de oerknal was begonnen op de snelste denkbare computer, zou je de piek vandaag nog niet zien.
Elk instinct zegt: dit divergeert. Van getallen van die grootte is geen terugkeer. Intuïtie heeft het hier simpelweg mis, en dat is het punt. Er gebeurt iets onzichtbaars dat de kale getallen niet tonen.
Het verborgen getal dat alleen omlaag gaat
Vervang elke term door zijn ordinale schaduw
Hier is de sleutelzet. Neem willekeurig welke term in de Goodstein-rij en lees zijn hereditaire basis-n-uitdrukking. Schrijf nu, waar je de basis n ziet, het symbool omega (het eerste oneindige ordinaalgetal). Je hebt de structuur van de uitdrukking helemaal niet veranderd. Je hebt alleen een label omgewisseld. Het resultaat is een ordinaalgetal, een soort telling die voorbij de gehele getallen tot in het oneindige reikt.
Bijvoorbeeld: 4 in hereditaire basis 2 is . Vervang 2 door omega en je krijgt . De ordinale schaduw van 26 in hereditaire basis 3 is twee keer omega kwadraat, plus twee keer omega, plus twee: een polynoom van eindige hoogte in omega, veel kleiner dan omega-tot-de-omega. De exponenten 2, 1 en 0 in de hereditaire basis-3-uitdrukking liggen al onder 3, dus er is geen verdere stapeling. Deze ordinalen zijn volmaakt welgedefinieerde wiskundige objecten.
Het ophogen van de basis doet de schaduw niets
Wanneer je de basis van n naar n+1 ophoogt, verandert de hereditaire uitdrukking haar label van n naar n+1, maar de vorm van de uitdrukking blijft identiek. Dus de ordinale schaduw verandert niet bij het ophogen. De schaduw van de term vóór het ophogen en de schaduw van de term erna zijn hetzelfde ordinaalgetal.
Maar daarna trek je 1 af van het gehele getal. 1 aftrekken, in hereditaire notatie, vereist dat je de laagste term van de uitdrukking afpelt. Dat verandert de vorm van de hereditaire uitdrukking op een manier die, wanneer je de basis door omega vervangt, een strikt kleiner ordinaalgetal geeft. Niet met een piepklein bedrag, niet toevallig: elke aftrekking van 1 van de rij gehele getallen dwingt de ordinale schaduw strikt omlaag.
Dus het patroon is: hoog de basis op (schaduw blijft staan), trek 1 af (schaduw daalt). Netto-effect per stap: de ordinale schaduw gaat minstens één stap omlaag, elke enkele keer.
Ordinalen kunnen niet eeuwig dalen
Een strikt dalende rij ordinalen kan niet eeuwig doorgaan. Dit is een van de fundamenteelste feiten over ordinalen: in tegenstelling tot de gehele getallen kun je niet onbeperkt omlaag blijven gaan. Er is een bodem. De rij ordinale schaduwen moet uiteindelijk nul bereiken, en wanneer de ordinale schaduw nul is, is het enige gehele getal waarvan de hereditaire uitdrukking op het nul-ordinaal afbeeldt nul zelf. Dus de Goodstein-rij moet ook nul bereiken.
De gehele getallen kunnen opblazen tot onvoorstelbare groottes. Maar de ordinalen erachter tikken stil, onvermijdelijk, bij elke stap omlaag. Het lawaai zit in de zichtbare getallen. De waarheid zit in de schaduw.
De hydra zegt hetzelfde
Je kunt hetzelfde verhaal als een spel vertellen. Stel je een boomvormig monster voor, een hydra, met koppen aan de uiteinden van haar takken. Je hakt een kop af. Afhankelijk van welke kop je snijdt en wanneer, kunnen er meerdere nieuwe koppen uit de stomp groeien, soms veel meer. Je blijft snijden. De hydra lijkt te winnen.
Het Kirby-Paris-hydra-spel, geïntroduceerd door de wiskundigen Jeff Paris en Laurie Kirby in 1982, is precies deze situatie, en het codeert dezelfde wiskunde als de Goodstein-rij. De kop-uitspruitregel correspondeert met de explosie van het ophogen van de basis. De boomstructuur correspondeert met de hereditaire notatie. En het verborgen ordinaalgetal achter de boom daalt strikt bij elke snede, net als in Goodsteins argument.
Welke strategie je ook gebruikt, hoe achteloos je ook kiest welke kop je afhakt, je wint altijd. De hydra sterft altijd. De explosie van nieuwe koppen is echt, en ze kan spectaculair zijn, maar onder het vuurwerk loopt een aftelling. Het hydra-spel is de stelling van Goodstein in een kostuum.
Waarom wiskundigen het interesseert
Hier neemt het verhaal een wending. De stelling van Goodstein is waar. Ze is bewijsbaar waar, zoals het ordinale argument hierboven laat zien. Maar in 1982 bewezen Kirby en Paris iets anders: de stelling kan niet bewezen worden binnen de Peano-rekenkunde.
Peano-rekenkunde is het standaard formele systeem voor redeneren over gehele getallen. Het vangt bijna alles wat je gewone rekenkunde zou noemen: optellen, vermenigvuldigen, inductie over de natuurlijke getallen. Het is de arena waarin de meeste klasresultaten leven. En het is simpelweg niet sterk genoeg om te bewijzen dat Goodstein-rijen termineren.
Dit betekent niet dat de stelling in elke zin onbewijsbaar is. Het ordinale argument werkt, en het is volledig rigoureus. Maar het ordinale argument vereist redeneren over oneindigheid op een manier die Peano-rekenkunde niet kan bereiken. Het systeem kan Goodstein-rijen precies beschrijven. Het kan ze term voor term draaien. Het kan zelfs herkennen dat elke term een specifiek geheel getal is. Wat het niet kan, is de schaduw zien, de ordinale structuur die de afdaling garandeert.
De stelling van Goodstein was een van de eerste voorbeelden van een natuurlijke, gewoon ogende uitspraak over gewone getallen die net buiten het bereik van de standaardrekenkunde bleek te leven. Het is geen kunstmatige logische puzzel die is gemaakt om onbewijsbaar te zijn. Het is een uitspraak die je aan een scholier zou kunnen uitleggen, over een rij die je op een servet zou kunnen schrijven, en de standaardrekenkunde kan de zaak niet sluiten.
De zen ervan
Hier is iets om bij stil te staan. De rij die lijkt te exploderen zonder grens neemt bij elke stap deel aan een afdaling die de kale getallen voor je verbergen. De twee dingen gebeuren tegelijk: enorme groei, en stille onvermijdelijke terugkeer.
Dit is geen tegenspraak. Het is een herinnering dat de grootte van een getal niet hetzelfde is als zijn lot. Wat telt is de structuur eronder, en de structuur hier wijst altijd naar nul.
De wiskunde zit vol van zulke momenten: een grootheid die lijkt te moeten divergeren maar dat niet doet, een bewijs dat lijkt te moeten falen maar standhoudt, een rij die oneindig lijkt maar termineert. De vaardigheid zit niet in brute-kracht termen uitrekenen. Ze zit in het vinden van de juiste schaduw om te volgen, die je vertelt wat er écht gebeurt. Zodra je het ordinaalgetal omlaag ziet tikken achter het vuurwerk, is de stelling niet alleen waar. Ze voelt onvermijdelijk.
Grootte is ruis. Structuur is het signaal. De rij was altijd al op weg naar huis.
Veelgestelde vragen
- Wat zegt de stelling van Goodstein eigenlijk?
- Ze zegt dat elke Goodstein-rij, hoe groot haar getallen onderweg ook groeien, uiteindelijk nul bereikt. De groei kan astronomisch zijn en een onvoorstelbaar aantal stappen duren, maar terminatie is gegarandeerd voor elke startwaarde.
- Waarom komt de rij terug omlaag als ze blijft groeien?
- Elke term heeft een verborgen ordinaal-partner die bij elke stap strikt daalt. De zichtbare gehele getallen kunnen opblazen, maar het ordinaalgetal erachter kan alleen omlaag, en een dalende rij ordinalen kan niet eeuwig dalen, dus het proces moet bij nul eindigen.
- Wat is hereditaire basis-n-notatie?
- Het betekent een getal in basis n schrijven, en dan ook al zijn exponenten in basis n schrijven, helemaal naar beneden. Bijvoorbeeld: 4 in hereditaire basis 2 wordt geschreven als twee tot de twee, waarbij de exponent ook in basis 2 is uitgedrukt.
- Waarom is de stelling van Goodstein beroemd in de logica?
- Omdat ze waar is maar niet bewezen kan worden met alleen Peano-rekenkunde. Ze was een van de eerste natuurlijke, niet-geconstrueerde uitspraken over gewone getallen die in dat systeem onbewijsbaar bleken, daarom zit ze op de grens van wiskunde en logica.
- Is het hydra-spel hetzelfde idee?
- Ja, de Kirby-Paris-hydra is een hervertelling van dezelfde wiskunde. Een kop afhakken kan vele nieuwe laten groeien, en toch wordt de hydra altijd verslagen, om precies dezelfde reden dat een Goodstein-rij altijd nul bereikt.
Oefen het zelf
Vond je het leuk om dit door te denken?
Math Zen maakt van dit soort inzicht dagelijkse oefening, met adaptieve opgaven bij 24 wiskundeonderwerpen.
