Goodsteins sats: följden som exploderar och ändå alltid återvänder till noll
Välj ett heltal. Vilket heltal som helst. Följ nu en tvåstegsregel, om och om igen, och se resultatet. För nästan varje startvärde du väljer rusar följden uppåt förbi ett googol, förbi tal som dvärgar antalet atomer i det observerbara universum, förbi allt du skulle kunna skriva ner i ett liv. Och ändå kommer den bevisligen alltid tillbaka till noll.
Det är Goodsteins sats, och första gången du hör den låter den som ett trick. Regeln är inte komplicerad, talen är vanliga, och påståendet är rent. Ändå hade skälet till att den är sann i årtionden inget hem inne i vanlig aritmetik. Den här artikeln ber dig inte följa ett logikbevis. I stället visar den dig bilden under, och när du ser den slutar satsen vara mystisk.
Regeln är nästan barnsligt enkel
Du startar med ett heltal och en bas, med början i bas 2. Vid varje steg gör du två saker: först, skriv om det aktuella talet i något som kallas hereditär bas-n-notation; sedan, ersätt varje förekomst av basen n med n+1, och subtrahera sedan 1. Gå därefter till nästa bas och upprepa.
Höj-och-subtrahera låter milt. Att höja en bas från 2 till 3 känns som en liten förändring. Att subtrahera 1 känns som om det borde tygla talet. Du ska strax se varför ingen av de intuitionerna överlever mötet med hereditär notation.
Se den explodera
Börja med 4. I hereditär bas 2 är det . Höj varje 2 till 3 och subtrahera 1: du får minus 1, vilket är 26. Skriv nu 26 i hereditär bas 3, höj till bas 4, subtrahera 1, och du får 41. Fortsätt.
| 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 |
Följden som startar vid 4 löper: 4, 26, 41, 60, 83, 109, och fortsätter klättra därifrån. Även den här blygsamma starten växer en anmärkningsvärt lång sträcka innan den till slut sjunker. Börja i stället från 19, och talen når höjder som är fysiskt oskrivbara. Antalet steg innan följden ens börjar vända är större än antalet atomer i det observerbara universum. Om du startade beräkningen vid Big Bang på den snabbaste dator som går att tänka sig skulle du inte se toppen idag.
Varje instinkt säger: det här divergerar. Det finns ingen återkomst från tal så stora. Intuitionen har helt enkelt fel här, och det är poängen. Något osynligt händer som de nakna talen inte visar.
Det dolda talet som bara går ner
Ersätt varje term med dess ordinalskugga
Här är nyckeldraget. Ta vilken term som helst i Goodsteinföljden och läs dess hereditära bas-n-uttryck. Skriv nu, där du ser basen n, symbolen omega (det första oändliga ordinaltalet) i stället. Du har inte ändrat strukturen i uttrycket alls. Du har bara bytt en etikett. Resultatet är ett ordinaltal, en sorts räkning som sträcker sig bortom heltalen in i det oändliga.
Till exempel är 4 i hereditär bas 2 lika med . Ersätt 2 med omega och du får . Ordinalskuggan av 26 i hereditär bas 3 är två gånger omega i kvadrat, plus två gånger omega, plus två: ett polynom av ändlig höjd i omega, långt mindre än omega-upphöjt-till-omega. Exponenterna 2, 1 och 0 i det hereditära bas-3-uttrycket ligger redan under 3, så ingen vidare stapling sker. Dessa ordinaltal är fullt väldefinierade matematiska objekt.
Att höja basen gör ingenting med skuggan
När du höjer basen från n till n+1 ändrar det hereditära uttrycket sin etikett från n till n+1, men formen på uttrycket förblir identisk. Så ordinalskuggan ändras inte när du höjer. Skuggan av termen före höjningen och skuggan av termen efter höjningen är samma ordinaltal.
Men sedan subtraherar du 1 från heltalet. Att subtrahera 1, i hereditär notation, kräver att du skalar av den lägsta termen i uttrycket. Det ändrar formen på det hereditära uttrycket på ett sätt som, när du ersätter basen med omega, ger ett strikt mindre ordinaltal. Inte med en pytteliten mängd, inte av en slump: varje subtraktion av 1 från heltalsföljden tvingar ordinalskuggan strikt nedåt.
Så mönstret är: höj basen (skuggan står still), subtrahera 1 (skuggan sjunker). Nettoeffekt per steg: ordinalskuggan går ner minst ett steg, varje enda gång.
Ordinaltal kan inte minska för evigt
En strikt avtagande följd av ordinaltal kan inte pågå för evigt. Det är ett av de mest grundläggande fakta om ordinaltal: till skillnad från heltalen kan du inte fortsätta neråt i oändlighet. Det finns en botten. Följden av ordinalskuggor måste till slut nå noll, och när ordinalskuggan är noll är det enda heltal vars hereditära uttryck avbildas på noll-ordinaltalet noll självt. Så Goodsteinföljden måste nå noll också.
Heltalen kan svälla till ofattbara storlekar. Men ordinaltalen bakom dem tickar tyst, oundvikligt, nedåt vid varje steg. Bruset sitter i de synliga talen. Sanningen sitter i skuggan.
Hydran säger samma sak
Du kan berätta samma historia som ett spel. Föreställ dig ett trädformat monster, en hydra, med huvuden i ändarna av sina grenar. Du hugger av ett huvud. Beroende på vilket huvud du skär och när kan flera nya huvuden växa från stubben, ibland många fler. Du fortsätter skära. Hydran ser ut att vinna.
Kirby-Paris-hydraspelet, introducerat av matematikerna Jeff Paris och Laurie Kirby 1982, är exakt den här situationen, och det kodar samma matematik som Goodsteins följd. Regeln för huvudens utväxt motsvarar explosionen när basen höjs. Trädstrukturen motsvarar den hereditära notationen. Och det dolda ordinaltalet bakom trädet minskar strikt vid varje hugg, precis som i Goodsteins argument.
Oavsett vilken strategi du använder, oavsett hur slarvigt du väljer vilket huvud du hugger, vinner du alltid. Hydran dör alltid. Explosionen av nya huvuden är verklig, och den kan vara spektakulär, men under fyrverkeriet tickar en nedräkning. Hydraspelet är Goodsteins sats i kostym.
Varför matematiker bryr sig
Här tar historien en vändning. Goodsteins sats är sann. Den är bevisligen sann, som ordinalargumentet ovan visar. Men 1982 bevisade Kirby och Paris något annat: satsen kan inte bevisas inne i Peanos aritmetik.
Peanos aritmetik är det standardformella systemet för att resonera om heltal. Det fångar nästan allt du skulle kalla vanlig aritmetik: addition, multiplikation, induktion över de naturliga talen. Det är arenan där de flesta klassrumsresultat lever. Och det är helt enkelt inte starkt nog att bevisa att Goodsteinföljder terminerar.
Det betyder inte att satsen är obevisbar i varje mening. Ordinalargumentet fungerar, och det är helt rigoröst. Men ordinalargumentet kräver resonemang om oändlighet på ett sätt som Peanos aritmetik inte kan nå. Systemet kan beskriva Goodsteinföljder precist. Det kan köra dem, term för term. Det kan till och med känna igen att varje term är ett specifikt heltal. Vad det inte kan göra är att se skuggan, den ordinala struktur som garanterar nedstigningen.
Goodsteins sats var ett av de första exemplen på ett naturligt, vanligt-utseende påstående om vanliga tal som visade sig leva precis bortom räckvidden för standardaritmetik. Det är inte något konstgjort logikpussel konstruerat för att vara obevisbart. Det är ett påstående du skulle kunna förklara för en gymnasieelev, om en följd du skulle kunna skriva på en servett, och standardaritmetiken kan inte stänga fallet.
Zenen i det
Här finns något värt att sitta med. Följden som ser ut att explodera utan gräns deltar, vid varje steg, i en nedstigning som de nakna talen döljer för dig. De två sakerna händer samtidigt: enorm tillväxt, och tyst oundviklig återkomst.
Det är ingen motsägelse. Det är en påminnelse om att storleken på ett tal inte är samma sak som dess öde. Vad som spelar roll är strukturen under, och strukturen här pekar alltid mot noll.
Matematiken är full av sådana ögonblick: en storhet som ser ut att böra divergera men inte gör det, ett bevis som ser ut att böra misslyckas men håller, en följd som ser oändlig ut men terminerar. Skickligheten sitter inte i att räkna ut termer med råstyrka. Den sitter i att hitta rätt skugga att följa, den som talar om vad som faktiskt händer. När du väl ser ordinaltalet ticka ner bakom pyrotekniken är satsen inte bara sann. Den känns oundviklig.
Storlek är brus. Struktur är signalen. Följden var alltid på väg hem.
Vanliga frågor
- Vad säger Goodsteins sats egentligen?
- Den säger att varje Goodsteinföljd, hur stora talen än växer på vägen, till slut når noll. Tillväxten kan vara astronomisk och pågå i ett ofattbart antal steg, men terminering är garanterad för varje startvärde.
- Varför kommer följden tillbaka ner om den fortsätter växa?
- Varje term har en dold ordinalpartner som strikt minskar vid varje steg. De synliga heltalen kan svälla, men ordinaltalet bakom dem kan bara gå ner, och en avtagande följd av ordinaltal kan inte falla för evigt, så processen måste sluta vid noll.
- Vad är hereditär bas-n-notation?
- Det betyder att skriva ett tal i bas n, och sedan skriva alla dess exponenter i bas n också, hela vägen ner. Till exempel skrivs 4 i hereditär bas 2 som två upphöjt till två, där exponenten också uttrycks i bas 2.
- Varför är Goodsteins sats berömd i logiken?
- För att den är sann men inte kan bevisas med enbart Peanos aritmetik. Den var ett av de första naturliga, icke-konstruerade påståendena om vanliga tal som visades obevisbara i det systemet, vilket är varför den sitter på gränsen mellan matematik och logik.
- Är hydraspelet samma idé?
- Ja, Kirby-Paris-hydran är en återberättelse av samma matematik. Att hugga av ett huvud kan få många fler att växa, och ändå besegras hydran alltid till slut, av exakt samma skäl som en Goodsteinföljd alltid når noll.
Öva själv nu
Tyckte du det var kul att tänka igenom det här?
Math Zen gör den här sortens intuition till daglig övning, med adaptiva uppgifter inom 24 matteområden.
