Goodsteins sats

Goodsteins teorem är inom matematisk logik ett uttalande om de naturliga talen, som Reuben Goodstein bevisade 1944, vilket säger att varje Goodstein-sekvens till slut terminerar vid 0. Kirby och Paris visade att det är oavgörbart i Peano-aritmetik (men det kan bevisas i starkare system, såsom andra ordningens aritmetik). Detta var det tredje exemplet på ett sant uttalande som är oavgörbart inom Peano-aritmetik, efter Gödels ofullständighetsteorem och Gerhard Gentzens direkta bevis 1943 av att ε0-induktion är oavgörbar i Peano-aritmetik. Paris-Harringtons sats var ett senare exempel.

Laurence Kirby och Jeff Paris introducerade ett grafteoretiskt hydra-spel med ett beteende som liknar Goodstein-sekvenser: "Hydra" är ett rotat träd och ett drag består av att klippa av ett av dess "huvuden" (en gren av trädet), på vilket Hydra svarar genom att odla ett begränsat antal nya huvuden enligt vissa regler. Kirby och Paris visade att Hydra så småningom kommer att dödas, oavsett vilken strategi Herakles använder för att hugga av huvudena, men det kan ta mycket lång tid. Precis som för Goodstein-sekvenser visade Kirby och Paris att detta inte kan bevisas i Peano-aritmetiken ensam.

Ärftlig bas-n notation 
Goodstein-sekvenser definieras i form av ett begrepp som kallas "ärftlig bas-n-notation". Denna beteckning liknar den vanliga bas-n notationen, men den vanliga notationen är inte tillräcklig för Goodsteins teorem.

I vanlig bas-n notation, där n är ett naturligt tal större än 1, skrivs ett godtyckligt naturligt tal m som summan av potenser av n:

där varje koefficient uppfyller , och  Till exempel, i bas 2,

Bas-2-representationen av 35 är således 100011, vilket betyder . På samma sätt är 100 representerad i bas 3 av 10201:

Observera att exponenterna själva inte är skrivna i bas-n notation. Till exempel innehåller uttrycken ovan 25 och 34.

För att konvertera ett tal i bas-n notation till ärftlig bas-n notation, skriv först om alla exponenter i bas-n notation. Skriv sedan om alla exponenter inne i exponenten och fortsätt på detta sätt tills alla tal som visas i uttrycket har omvandlats till bas-n notation.

Till exempel, medan 35 i vanliga bas-2 notation är , så skrivs det i ärftlig bas-2 notation som

med hjälp av att . På samma sätt blir 100 i ärftlig bas-3 notation

Goodstein-sekvenser 
Goodstein-sekvensen G(m) av ett tal m är en följd av naturliga tal. Det första elementet i följden G(m) är m själv. För att få det andra, G(m)(2), skriv m i ärftlig bas-2 notation, ändra alla 2:or till 3:or och subtrahera sedan 1 från resultatet. I allmänhet fås G(m)(n + 1), term (n + 1) av Goodstein-sekvensen av m, på följande sätt:
 Skriv G(m)(n) med ärftlig bas-n+1 representation.
 Ersätt alla förekomster av bas-n+1 med n+2.
 Subtrahera 1. Observera att nästa term beror både på den föregående termen och på index n.
 Fortsätt tills resultatet är noll, då sekvensen avslutas.
De första Goodstein-sekvenserna terminerar snabbt. Till exempel slutar G(3) på 6:e steget:

Senare Goodstein-sekvenser ökar under ett mycket stort antal steg. Till exempel börjar G(4),  A056193, som följer:

Elementen i G(4) fortsätter att öka ett tag, men för basen 
når de maximum , stannar där under de följande  stegen, och börjar sedan sitt första och slutliga avtagande.

Värdet 0 nås för basen . Detta är märkligt nog ett Woodalltal: . Detta är också fallet för alla andra avslutande baser för startvärden som är större än 4.

Inte heller G(4) ger en bra uppfattning om hur snabbt elementen i en Goodstein-sekvens kan öka.
G(19) ökar mycket snabbare och startar enligt följande:

Trots denna snabba tillväxt säger Goodsteins sats att varje Goodstein-sekvens så småningom slutar på 0, oavsett vad startvärdet är.

Bevis av Goodsteins sats 
Goodsteins sats kan bevisas (med metoder som är utanför Peano-aritmetiken, se nedan) enligt följande: Givet en Goodstein-sekvens G(m), konstruerar vi en parallell sekvens P(m) av ordinaltal som är strängt avtagande och terminerar. Då måste G(m) också terminera, och den kan bara terminera genom att gå till 0. Ett vanligt missförstånd av detta bevis är att tro att G(m) går till 0 eftersom den domineras av P(m). Det faktumet att P(m) dominerar G(m) spelar faktiskt ingen roll alls. Den viktiga påståendet är: G(m)(k) existerar om och endast om P(m)(k) existerar (parallellism). Om sedan P(m) terminerar, så terminerar också G(m). Och G(m) kan bara terminera när den kommer till 0.

Mer exakt, varje term P(m)(n) i sekvensen P(m) erhålls genom att tillämpa en funktion f på termen G(m)(n) enligt följande: ta ärftlig bas-n+1 representationen av G(m)(n), och ersätt varje förekomst av bas-n+1 med det första oändliga ordinaltalet ω. Till exempel,  ger . Addition, multiplikation och potenser av ordinaltal är väldefinierade.
 Den basändrande operationen som används i Goodstein-sekvensen när man går från G(m)(n) till  ändrar inte värdet av f (detta är poängen med konstruktionen), efter minus 1 operationen kommer P(m)(n+1) att vara strikt mindre än P(m)(n). Till exempel,  och därmed är  strikt större än 

Om sekvensen G(m) inte skulle gå till 0, det vill säga inte skulle terminera, skulle den vara oändlig (eftersom G(m)(k+1) alltid skulle finnas). Följaktligen skulle P(m) också vara oändlig (eftersom i sin tur P(m)(k+1) alltid skulle finnas). Men P(m) är strängt avtagande och standardordningen < för ordinaltal är välgrundad. Därför kan inte en oändlig, strikt avtagande sekvens existera, eller ekvivalent, varje strikt avtagande sekvens av ordinaltal terminerar (och kan inte vara oändlig). Denna motsägelse visar att G(m) terminerar och eftersom den terminerar så går den till 0. Eftersom det finns ett naturligt tal k sådant att  medför konstruktionen av .

Även om detta bevis av Goodsteins sats är ganska lätt så är Kirby–Paris sats, som visar att Goodsteins sats inte är en sats inom Peano-aritmetiken, teknisk och betydligt svårare. Den använder sig av uppräkningsbara icke-standardmodeller av Peanoaritmetik.

Utökad Goodstein sats 
Antag att definitionen av Goodstein-sekvensen ändras så att i stället för att ersätta alla förekomster av bas b med b+1, så ersätts de med b+2. Kommer sekvensen fortfarande att terminera?
Mer generellt, låt b1, b2, b3, ... vara någon sekvens av heltal. Låt term n+1 av den utökade Goodstein-sekvensen av m, G(m)(n+1), beräknas på följande sätt: ta ärftlig bas bn representationen av G(m)(n) och ersätt varje förekomst av basen bn med bn+1 och subtrahera sedan 1. Kravet är att denna sekvens fortfarande terminerar.
Det utökade beviset definierar 
på följande sätt: ta ärftlig bas bn representationen av G(m)(n), och ersätt varje förekomst av basen bn med det första oändliga ordinaltalet ω.
Den basändrande operationen i Goodstein-sekvensen när man går från G(m)(n) till G(m)(n+1) ändrar fortfarande inte värdet av f. Till exempel, om  och ,
så är  och ordinaltalet  är strikt större än ordinaltalet

Sekvensens längd som en funktion av startvärdet 
Goodsteinfunktionen,  är definierad som att  är längden av Goodstein-sekvensen som börjar med n. (Detta är en total funktion eftersom varje Goodstein sekvens avslutas.) Den extrema tillväxten av  kan kalibreras genom att relatera till olika standard ordinaltal-indexerade hierarkier av funktioner, såsom funktionerna  i Hardy-hierarkin, och funktionerna  i den snabbväxande Löb-Wainer-hierarkin:
 Kirby och Paris (1982) visade att
  har ungefär samma tillväxthastighet som  (vilket är samma som den för ); mer exakt,  dominerar  för varje , och  dominerar 
 För två funktioner , sägs  dominera  om  för alla tillräckligt stora .
 Cichon (1983) visade att
 
 där  är resultatet av att sätta n i ärftlig bas-2 notation och sedan byta ut alla 2:or mot ω (som i beviset av Goodsteins teorem).
 Caicedo (2007) visade att om  med  så är
 .
Några exempel:

(Funktionen A(m, n) är Ackermannfunktionen.)

Tillämpning på beräkningsbara funktioner 
Goodsteins sats kan användas för att skapa en totalt beräkningsbar funktion som Peano-aritmetiken inte kan visa att den är total. Goodstein-sekvensen av ett nummer kan på ett effektivt sätt räknas upp med en Turingmaskin. Den funktion som avbildar n på antalet steg som krävs för Goodstein-sekvensen av n ska terminera är beräkningsbar av en viss Turingmaskin. Denna maskin räknar bara upp Goodstein sekvensen av n och när sekvensen når 0, returnerar den längden på sekvensen. Eftersom varje Goodstein sekvens så småningom slutar är denna funktion total. Men eftersom Peano-aritmetiken inte kan bevisa att varje Goodstein sekvens avslutas, så kan Peano-aritmetiken inte bevisa att denna Turingmaskin beräknar en total funktion.

Källor

Noter

Vidare läsning 
 .
 .
 .

Externa länkar 
 Goodstein Sequences: The Power of a Detour via Infinity - en bra introduktion som illustrerar Goodsteinsekvenser och hydraspelet.
Mycket stora tal
Mängdteori