Goodsteins sats är inom matematisk logik en utsaga om de naturliga talen, som Reuben Goodstein bevisade 1944, vilken säger att varje Goodstein-följd till slut terminerar vid 0. Kirby och Paris visade att den är oavgörbar i Peano-aritmetik (men den kan bevisas i starkare system, såsom andra ordningens aritmetik). Detta var det tredje exemplet på en sann utsaga som är oavgörbar 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-följdernas: "hydran" ä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 Hydran svarar genom att låta ett begränsat antal nya huvuden växa ut enligt vissa regler. Kirby och Paris visade att hydran 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-följder visade Kirby och Paris att detta inte kan bevisas i Peano-aritmetiken ensam.
Ärftlig bas-n notation Goodstein-följder 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 sats.
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-följder Goodstein-följden 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-följden 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å följden avslutas. De första Goodstein-följderna terminerar snabbt. Till exempel slutar G(3) på 6:e steget:
Bas Ärftlig notation Värde Kommentar 2 3 Skriv 3 i bas-2 notation 3 3 Byt 2:an till en 3:a, subtrahera 1 4 3 Byt 3:an till en 4:a, subtrahera 1. Nu finns ingen 4:a kvar 5 2 Ingen 4:a kvar, byt till en 5:a. Subtrahera 1 6 1 Ingen 5:a kvar, byt till en 6:a. Subtrahera 1 7 0 Ingen 6:a kvar, byt till en 7:a. Subtrahera 1
Senare Goodstein-följder ökar under ett mycket stort antal steg. Till exempel börjar G(4), länk=Nätuppslagsverket_över_heltalsföljder|15x15px|OEIS A056193, som följer: Ärftlig notation Värde 4 26 41 60 83 109 253 299 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-följder kan öka. G(19) ökar mycket snabbare och startar enligt följande: Ärftlig notation Värde 19
Trots denna snabba tillväxt säger Goodsteins sats att varje Goodstein-följd 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-följd G(m), konstruerar vi en parallell följd 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 följden 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-följden 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 följden 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 följde existera, eller ekvivalent, varje strikt avtagande följd 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-följden ä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 följden fortfarande att terminera? Låt mer allmänt b1, b2, b3, ... vara en heltalsföljd. Låt term n+1 av den utökade Goodstein-följden 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 följd 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-följden 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
Följdens längd som en funktion av startvärdet Goodsteinfunktionen, är definierad som att är längden av Goodstein-följden som börjar med n. (Detta är en total funktion eftersom varje Goodsteinföljd 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 sats). Caicedo (2007) visade att om med så är . Några exempel: n 1 2 2 4 3 6 4 3·2402653211 − 2 5 > A(4,4) 6 > A(6,6) 7 > A(8,8) 8 > A3(3,3) = A(A(61, 61), A(61, 61)) 12 > fω+1(64) > Graham's number 19 (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-öljden av ett tal 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-följden av n ska terminera är beräkningsbar av en viss Turingmaskin. Denna maskin räknar bara upp Goodstein-följden av n och när följden når 0, returnerar den följdens längd. Eftersom varje Goodstein-följd så småningom avslutas är denna funktion total. Men eftersom Peano-aritmetiken inte kan bevisa att varje Goodstein-följd 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 Goodsteinföljder och hydraspelet. Kategori:Mycket stora tal Kategori:Mängdteori