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.[1]

Ärftlig bas-n notationRedigera

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 0 ≤ ai < n, och ak ≠ 0. Till exempel, i bas 2,

 

Bas-2-representationen av 35 är således 100011, vilket betyder 25 + 2 + 1. 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 25 + 2 + 1, så skrivs det i ärftlig bas-2 notation som

 

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

 

Goodstein-sekvenserRedigera

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:

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-sekvenser ökar under ett mycket stort antal steg. Till exempel börjar G(4),  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.[källa behövs]

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:

Ärftlig notation Värde
  19
  7625597484990
   
   
   
   

         

 

   
     

 
   

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 satsRedigera

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, G(3)(1) = 3 = 21 + 20 ger P(3)(1) = f(G(3)(1)) = ω1 + ω0 = ω + 1. 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 G(m)(n+1) ä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 G(m)(k) = 0 medför konstruktionen av P(m) också att P(m)(k) = 0.

Ä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 satsRedigera

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(m)(n) = f(G(m)(n), n) 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 bn = 4 och bn+1 = 9, så är   och ordinaltalet   är strikt större än ordinaltalet  

Sekvensens längd som en funktion av startvärdetRedigera

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:

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 funktionerRedigera

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ällorRedigera

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia.

NoterRedigera

  1. ^ Kirby, L.; Paris, J. (1982). ”Accessible Independence Results for Peano Arithmetic”. Bulletin of the London Mathematical Society 14 (4): sid. 285. doi:10.1112/blms/14.4.285. http://www.cs.tau.ac.il/~nachumd/term/Kirbyparis.pdf. 

Vidare läsningRedigera

Externa länkarRedigera