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 ε₀-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:

$m=a_{k}n^{k}+a_{k-1}n^{k-1}+\cdots +a_{0},$

där varje koefficient uppfyller 0 ≤ a_i < n, och a_k ≠ 0. Till exempel, i bas 2,

$35=32+2+1=2^{5}+2^{1}+2^{0}.$

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

$100=81+18+1=3^{4}+2\cdot 3^{2}+3^{0}.$

Observera att exponenterna själva inte är skrivna i bas-n notation. Till exempel innehåller uttrycken ovan 2⁵ och 3⁴.

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 2⁵ + 2 + 1, så skrivs det i ärftlig bas-2 notation som

$35=2^{2^{2}+1}+2+1,$

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

$100=3^{3+1}+2\cdot 3^{2}+1.$

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:

Bas	Ärftlig notation	Värde	Kommentar
2	$2^{1}+1$	3	Skriv 3 i bas-2 notation
3	$3^{1}+1-1=3^{1}$	3	Byt 2:an till en 3:a, subtrahera 1
4	$4^{1}-1=3$	3	Byt 3:an till en 4:a, subtrahera 1. Nu finns ingen 4:a kvar
5	$3-1=2$	2	Ingen 4:a kvar, byt till en 5:a. Subtrahera 1
6	$2-1=1$	1	Ingen 5:a kvar, byt till en 6:a. Subtrahera 1
7	$1-1=0$	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
$2^{2}$	4
$3^{3}-1=2\cdot 3^{2}+2\cdot 3+2$	26
$2\cdot 4^{2}+2\cdot 4+1$	41
$2\cdot 5^{2}+2\cdot 5$	60
$2\cdot 6^{2}+2\cdot 6-1=2\cdot 6^{2}+6+5$	83
$2\cdot 7^{2}+7+4$	109
$\vdots$	$\vdots$
$2\cdot 11^{2}+11$	253
$2\cdot 12^{2}+12-1=2\cdot 12^{2}+11$	299
$\vdots$	$\vdots$

Elementen i G(4) fortsätter att öka ett tag, men för basen $3\cdot 2^{402\,653\,209}$ når de maximum $3\cdot 2^{402\,653\,210}-1$, stannar där under de följande $3\cdot 2^{402\,653\,209}$ stegen, och börjar sedan sitt första och slutliga avtagande.

Värdet 0 nås för basen $3\cdot 2^{402\,653\,211}-1$. Detta är märkligt nog ett Woodalltal: $3\cdot 2^{402\,653\,211}-1=402\,653\,184\cdot 2^{402\,653\,184}-1$. 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
$2^{2^{2}}+2+1$	19
$3^{3^{3}}+3$	7012762559748499000♠7625597484990
$4^{4^{4}}+3$	$\approx 1.3\times 10^{154}$
$5^{5^{5}}+2$	$\approx 1.8\times 10^{2184}$
$6^{6^{6}}+1$	$\approx 2.6\times 10^{36\,305}$
$7^{7^{7}}$	$\approx 3.8\times 10^{695\,974}$
$8^{8^{8}}-1=7\cdot 8^{(7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7)}$ $+7\cdot 8^{(7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+6)}+\cdots$ $+7\cdot 8^{(8+2)}+7\cdot 8^{(8+1)}+7\cdot 8^{8}$ $+7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}$ $+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7$	$\approx 6\times 10^{15\,151\,335}$
$7\cdot 9^{(7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+7)}$ $+7\cdot 9^{(7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+6)}+\cdots$ $+7\cdot 9^{(9+2)}+7\cdot 9^{(9+1)}+7\cdot 9^{9}$ $+7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}$ $+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+6$	$\approx 4.3\times 10^{369\,693\,099}$
$\vdots$	$\vdots$

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, G(3)(1) = 3 = 2¹ + 2⁰ ger P(3)(1) = f(G(3)(1)) = ω¹ + ω⁰ = ω + 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, $f(3\cdot 4^{4^{4}}+4)=3\omega ^{\omega ^{\omega }}+\omega =f(3\cdot 5^{5^{5}}+5)$ och därmed är $f(3\cdot 4^{4^{4}}+4)$ strikt större än $f((3\cdot 5^{5^{5}}+5)-1).$

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 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 b₁, b₂, b₃, ... 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 b_n representationen av G(m)(n) och ersätt varje förekomst av basen b_n med b_n+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 b_n representationen av G(m)(n), och ersätt varje förekomst av basen b_n 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 b_n = 4 och b_n+1 = 9, så är $f(3\cdot 4^{4^{4}}+4,4)=3\omega ^{\omega ^{\omega }}+\omega =f(3\cdot 9^{9^{9}}+9,9)$ och ordinaltalet $f(3\cdot 4^{4^{4}}+4,4)$ är strikt större än ordinaltalet $f((3\cdot 9^{9^{9}}+9)-1,9).$

Sekvensens längd som en funktion av startvärdet

Goodsteinfunktionen, ${\mathcal {G}}:\mathbb {N} \to \mathbb {N}$ är definierad som att ${\mathcal {G}}(n)$ ä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 ${\mathcal {G}}(n)$ kan kalibreras genom att relatera till olika standard ordinaltal-indexerade hierarkier av funktioner, såsom funktionerna $H_{\alpha }$ i Hardy-hierarkin, och funktionerna $f_{\alpha }$ i den snabbväxande Löb-Wainer-hierarkin:

• Kirby och Paris (1982) visade att

${\mathcal {G}}$ har ungefär samma tillväxthastighet som $H_{\epsilon _{0}}$ (vilket är samma som den för $f_{\epsilon _{0}}$); mer exakt, ${\mathcal {G}}$ dominerar $H_{\alpha }$ för varje $\alpha <\epsilon _{0}$, och $H_{\epsilon _{0}}$ dominerar ${\mathcal {G}}\,\!.$

För två funktioner $f,g:\mathbb {N} \to \mathbb {N}$, sägs $f$ dominera $g$ om $f(n)>g(n)$ för alla tillräckligt stora $n$.

• Cichon (1983) visade att

${\mathcal {G}}(n)=H_{R_{2}^{\omega }(n+1)}(1)-1,$

där $R_{2}^{\omega }(n)$ ä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 $n=2^{m_{1}}+2^{m_{2}}+\cdots +2^{m_{k}}$ med $m_{1}>m_{2}>\cdots >m_{k},$ så är

${\mathcal {G}}(n)=f_{R_{2}^{\omega }(m_{1})}(f_{R_{2}^{\omega }(m_{2})}(\cdots (f_{R_{2}^{\omega }(m_{k})}(3))\cdots ))-2$.

Några exempel:

n			${\mathcal {G}}(n)$
1	$2^{0}$	$2-1$	$H_{\omega }(1)-1$	$f_{0}(3)-2$	2
2	$2^{1}$	$2^{1}+1-1$	$H_{\omega +1}(1)-1$	$f_{1}(3)-2$	4
3	$2^{1}+2^{0}$	$2^{2}-1$	$H_{\omega ^{\omega }}(1)-1$	$f_{1}(f_{0}(3))-2$	6
4	$2^{2}$	$2^{2}+1-1$	$H_{\omega ^{\omega }+1}(1)-1$	$f_{\omega }(3)-2$	3·2402653211 − 2
5	$2^{2}+2^{0}$	$2^{2}+2-1$	$H_{\omega ^{\omega }+\omega }(1)-1$	$f_{\omega }(f_{0}(3))-2$	> A(4,4)
6	$2^{2}+2^{1}$	$2^{2}+2+1-1$	$H_{\omega ^{\omega }+\omega +1}(1)-1$	$f_{\omega }(f_{1}(3))-2$	> A(6,6)
7	$2^{2}+2^{1}+2^{0}$	$2^{2+1}-1$	$H_{\omega ^{\omega +1}}(1)-1$	$f_{\omega }(f_{1}(f_{0}(3)))-2$	> A(8,8)
8	$2^{2+1}$	$2^{2+1}+1-1$	$H_{\omega ^{\omega +1}+1}(1)-1$	$f_{\omega +1}(3)-2$	> A3(3,3) = A(A(61, 61), A(61, 61))
$\vdots$
12	$2^{2+1}+2^{2}$	$2^{2+1}+2^{2}+1-1$	$H_{\omega ^{\omega +1}+\omega ^{\omega }+1}(1)-1$	$f_{\omega +1}(f_{\omega }(3))-2$	> fω+1(64) > Graham's number
$\vdots$
19	$2^{2^{2}}+2^{1}+2^{0}$	$2^{2^{2}}+2^{2}-1$	$H_{\omega ^{\omega ^{\omega }}+\omega ^{\omega }}(1)-1$	$f_{\omega ^{\omega }}(f_{1}(f_{0}(3)))-2$

(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

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

Vidare läsning

• Goodstein, R. (1944), ”On the restricted ordinal theorem”, Journal of Symbolic Logic 9: 33–41, doi:10.2307/2268019 .
• Cichon, E. (1983), ”A Short Proof of Two Recently Discovered Independence Results Using Recursive Theoretic Methods”, Proceedings of the American Mathematical Society 87: 704–706, doi:10.2307/2043364 .
• Caicedo, A. (2007), ”Goodstein's function”, Revista Colombiana de Matemáticas 41 (2): 381–391, http://andrescaicedo.files.wordpress.com/2008/04/goodstein.pdf .

Externa länkar

• Goodstein Sequences: The Power of a Detour via Infinity - en bra introduktion som illustrerar Goodsteinsekvenser och hydraspelet.