Teorema de Goodstein

En lògica matemàtica, el Teorema de Goodstein és un enunciat sobre els nombres naturals, provat per Reuben Goodstein el 1944, que afirma que tota seqüència de Goodstein acaba enventualment en 0. Els matemàtics Laurence Kirby i Jeff Paris van mostrar que és indemostrable dintre de l'aritmètica de Peano (però pot ser provat en sistemes més forts, com l'aritmètica de segon ordre). Aquest va ser el tercer exemple d'un resultat cert que no pot ser provat en l'aritmètica de Peano, després dels exemples donats pel teorema d'incompletesa de Gödel i la demostració directa per Gerhard Gentzen el 1943 de la indecidibilitat de la ε₀-inducció en l'aritmètica de Peano. Posteriorment, el teorema de Paris–Harrington va donar un altre exemple.

En el treball de Kirby i Paris, introdueixen un joc de l'hidra en el context de la teoria de grafs i amb un comportament similar al de les seqüències de Goodstein: l'Hidra (anomenada així per la criatura mitològica amb diversos caps Hidra de Lerna) és un arbre arrelat, i un torn consisteix a tallar un dels seus "caps" (una branca de l'arbre), a la qual cosa l'Hidra respon creixent un nombre finit de nous caps d'acord amb unes certes regles. Kirby i Paris demostren que l'Hidra serà eventualment morta, independentment de l'estratègia que Hercules faci servir per anar tallant caps, malgrat que això podria requerir molt de temps. Tal com en les seqüències de Goodstein, Kirby i Paris mostren que no pot ser demostrat tan sols amb l'aritmètica de Peano.

Notació hereditària en base n

Les seqüències de Goodstein són definides en termes d'un concepte anomenat "notació hereditària en base n". Aquesta notació és molt similar a l'habitual notació posicional en base n, malgrat que aquesta no és suficient per al propòsit del teorema de Goodstein.

En notació ordinària de base n, on n és un nombre natural major que 1, un nombre natural arbitrari m s'escriu com a suma de múltiples de potències de n:

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

on cada coeficient a_i satisfà 0 ≤ a_i < n, i a_k ≠ 0. Per exemple, en base 2,

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

Per tant, la representació en base 2 de 35 és 100011, que representa 2⁵ + 2 + 1. Similarment, 100 representat en base 3 és 10201:

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

Notem que els mateixos exponents no s'escriuen en notació en base n. Per exemple, les expressions anteriors inclouen termes 2⁵ i 3⁴, on els exponents són majors que el valor de la base 5 > 2, 4 > 3.

Per convertir una representació en base n a notació en base n hereditària, primer cal reescriure tots els exponents també en notació en base n. Seguidament, cal reescriure els possibles exponents que apareguin en aquesta nova representació en base n, i continuar aquest procés fins que tots els nombres que apareguin en la representació (llevat de les mateixes bases) hagin estat convertits a notació en base n.

Per exemple, mentre que 35 en notació ordinària en base 2 és 2⁵ + 2 + 1, en notació hereditària en base 2 seria

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

usant que 5 = 2²¹ + 1. De forma semblant, 100 en notació hereditària en base 3 és

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

Seqüències de Goodstein

La seqüència de Goodstein G(m) d'un nombre m és una seqüència de nombres naturals definida de la següent manera. El primer element de la seqüència G(m) serà el propi nombre m. Per obtenir el segon, G(m)(2), escrivim m en notació hereditària en base 2, canviem tots els 2s per 3s, i restem 1 del resultat. En general, el (n + 1)-èssim terme, G(m)(n + 1), de la seqüència de Goodstein de m es defineix com:

• Prenem la representació en notació hereditària en base n + 1 del valor anterior, G(m)(n).
• Substituïm cada aparició de la base n + 1 amb n + 2.
• Restem 1. (Notem que el següent terme depèn tant del terme previ com de l'índex n.)
• Continuem fins que el resultat és zero, punt en el qual la seqüència s'atura.

Les seqüències de Goodstein per a valors petits terminen ràpidament. Per exemple, G(3) acaba en només 6 passos:

Base	Notació hereditària	Valor	Observacions
2	$2^{1}+1$	3	Escrivim 3 en notació base 2
3	$3^{1}+1-1=3^{1}$	3	Canviem el 2 per un 3, i després restem 1
4	$4^{1}-1=3$	3	Canviem el 3 per un 4, i després restem 1. Ara ja no hi apareix cap 4.
5	$3-1=2$	2	Cap 4 restant per ser canviat a 5. Simplement restem 1.
6	$2-1=1$	1	Cap 5 restant per ser canviat a 6. Simplement restem 1.
7	$1-1=0$	0	Cap 6 restant per ser canviat a 7. Simplement restem 1.

Seqüències de Goodstein posteriors creixen durant un llarg nombre de passos. Per exemple, G(4) (successió A056193 a l'OEIS) comença així:

Base	Notació hereditària	Valor
2	$2^{2^{1}}$	4
3	$3^{3^{1}}-1=2\cdot 3^{2}+2\cdot 3+2$	26
4	$2\cdot 4^{2}+2\cdot 4+1$	41
5	$2\cdot 5^{2}+2\cdot 5$	60
6	$2\cdot 6^{2}+2\cdot 6-1=2\cdot 6^{2}+6+5$	83
7	$2\cdot 7^{2}+7+4$	109
$\vdots$	$\vdots$	$\vdots$
11	$2\cdot 11^{2}+11$	253
12	$2\cdot 12^{2}+12-1=2\cdot 12^{2}+11$	299
$\vdots$	$\vdots$	$\vdots$
24	$2\cdot 24^{2}-1=24^{2}+23\cdot 24+23$	1151
$\vdots$	$\vdots$	$\vdots$
$B=3\cdot 2^{402\,653\,209}-1$	$2\cdot B^{1}$	$3\cdot 2^{402\,653\,210}-2$
$B=3\cdot 2^{402\,653\,209}$	$2\cdot B^{1}-1=B^{1}+(B-1)$	$3\cdot 2^{402\,653\,210}-1$
$\vdots$	$\vdots$	$\vdots$

Els elements de G(4) continuen creixent durant uns quants termes, però en arribar a la base $3\cdot 2^{402\,653\,209}$, s'assoleix un valor màxim de $3\cdot 2^{402\,653\,210}-1$, que es manté durant els següents $3\cdot 2^{402\,653\,209}$ passos, i llavors comença el descens.

Tanmateix, fins i tot G(4) no és capaç de donar una idea de com de ràpid poden créixer els elements d'una seqüència de Goodstein. Per exemple, G(19) creix molt més ràpidament, i comença així:

Notació hereditària	Valor
$2^{2^{2}}+2+1$	19
$3^{3^{3}}+3$	7.625.597.484.990
$4^{4^{4}}+3$	$\approx 1.3\times 10^{154}$
$5^{5^{5}}+2$	$\approx 1.8\times 10^{2\,184}$
$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.0\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 5.6\times 10^{35\,942\,384}$
$\vdots$	$\vdots$

Malgrat aquest ràpid creixement, el teorema de Goodstein assegura que tota seqüència de Goodstein eventualment acaba en 0, sigui quin sigui el valor inicial.

Demostració del teorema de Goodstein

El teorema de Goodstein pot ser provat (usant tècniques fora de l'aritmètica de Peano, vegeu a sota) com segueix.

Donada una seqüència de Goodstein G(m), construïm una seqüència paral·lela P(m) de nombres ordinals en forma normal de Cantor que és estrictament decreixent i termina. Un malentès habitual d'aquesta prova és creure que G(m) va a 0 perquè està dominada per P(m). En canvi, el fet que P(m) domina G(m) no hi juga cap paper. El punt important és: G(m)(k) existeix si i només si P(m)(k) existeix (paral·lelisme), i la comparació entre dos membres de G(m) es preserva quan es comparen les entrades corresponents de P(m). Aleshores, si P(m) acaba, també ho fa G(m). Per regressió infinita, G(m) ha d'arribar a 0, la qual cosa garanteix que la seqüència acaba.

Definim una funció $f=f(u,k)$ que calcula la representació hereditària en base k d'u i substitueix cada ocurrència de la base k amb el primer nombre ordinal infinit ω. Per exemple, $f(100,3)=f(3^{3^{1}+1}+2\cdot 3^{2}+1,3)=\omega ^{\omega ^{1}+1}+\omega ^{2}\cdot 2+1=\omega ^{\omega +1}+\omega ^{2}\cdot 2+1$.

Cada terme P(m)(n) de la seqüència P(m) es defineix com

$P(m)(n):=f(G(m)(n),n+1)$

Per exemple, G(3)(1) = 3 = 2¹ + 2⁰ i P(3)(1) = f(2¹ + 2⁰,2) = ω¹ + ω⁰ = ω + 1. La suma, multiplicació i exponenciació de nombres ordinals està ben definida.

Ara provarem que $f(G(m)(n),n+1)>f(G(m)(n+1),n+2)$:

Sigui $G'(m)(n)$ el resultat de G(m)(n) després d'aplicar la primera operació de canvi de base en la generació del següent element de la seqüència de Goodstein, però abans de la segona operació de menys 1 en aquesta generació. Observem que $G(m)(n+1)=G'(m)(n)-1$.

Aleshores $f(G(m)(n),n+1)=f(G'(m)(n),n+2)$. Ara apliquem l'operació menys 1, i $f(G'(m)(n),n+2)>f(G(m)(n+1),n+2)$, ja que $G'(m)(n)=G(m)(n+1)+1$. Per exemple, $G(4)(1)=2^{2}$ i $G(4)(2)=2\cdot 3^{2}+2\cdot 3+2$, així que $f(2^{2},2)=\omega ^{\omega }$ i $f(2\cdot 3^{2}+2\cdot 3+2,3)=\omega ^{2}\cdot 2+\omega \cdot 2+2$, el qual és estrictament més petit. Notem que per tal de calcular f(G(m)(n),n+1), primer requerim escriure G(m)(n) en notació hereditària en base n+1, ja que en efecte l'expressió $\omega ^{\omega }-1$ no és un ordinal.

En conseqüència, la seqüència P(m) és estrictament decreixent. Com l'ordre estàndard < en els ordinals és una relació ben fonamentada, una seqüència infinita estrictament decreixent no pot existir o, equivalent, tota seqüència estrictament decreixent d'ordinals ha de terminar (i no pot ser infinita). Però P(m)(n) es calcula directament de G(m)(n). Per tant, la seqüència G(m) ha d'acabar de la mateixa manera, la qual cosa significa que ha d'arribar a 0.

Mentre que la prova del teorema de Goodstein és prou senzilla, el teorema de Kirby–Paris, que demostra que el teorema de Goodstein no és un teorema de l'aritmètica de Peano, és tècnic i considerablement més complicat. Fa ús de models comptables no estàndards de l'aritmètica de Peano.

Extensió del teorema de Goodstein

Suposem que modifiquem la definició d'una seqüència de Goodstein de manera que, en lloc de substituir cada ocurrència de la base b amb b+1, la subsituïm amb b+2. En aquesta situació, la seqüència encara acabaria?

Més generalment, sigui b₁, b₂, b₃, … qualsevol seqüència d'enters. Llavors, definim el (n + 1)-èssim terme G(m)(n + 1) de la seqüència de Goodstein estesa de m com: prenem la representació hereditària en base b_n de G(m)(n) i substituïm cada ocurrència de la base b_n amb b_n+1, i llavors restem 1.

El resultat llavors és que la seqüència encara termina, i la prova d'aquesta generalització és pràcticament la mateixa que per al resultat original.

Longitud de la seqüència com a funció del valor inicial

La funció de Goodstein, ${\mathcal {G}}:\mathbb {N} \to \mathbb {N}$, es defineix de manera que ${\mathcal {G}}(n)$ és la longitud de la seqüència de Goodstein que comença per n. (Aquesta és una funció total ja que tota seqüència de Goodstein termina.) La extremada rapidesa de creixement de ${\mathcal {G}}$ pot ser calibrada a partir de relacionar-la amb diverses jerarquies estàndards de funcions, indexades per ordinals, com per exemple les funcions $H_{\alpha }$ en la jerarquia de Hardy, i les funcions $f_{\alpha }$ en la jerarquia de creixement ràpid de Löb i Wainer:

• Kirby i Paris (1982) van provar que

${\mathcal {G}}$ té aproximadament la mateixa taxa de creixement que $H_{\epsilon _{0}}$ (la qual és la mateixa que $f_{\epsilon _{0}}$); més precisament, ${\mathcal {G}}$ domina $H_{\alpha }$ per tot $\alpha <\epsilon _{0}$, i $H_{\epsilon _{0}}$ domina ${\mathcal {G}}\,\!.$

(Per qualssevol dues funcions $f,g:\mathbb {N} \to \mathbb {N}$, diem que $f$ domina $g$ si $f(n)>g(n)$ per tot $n$ prou gran.)

• Cichon (1983) va demostrar que

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

where $R_{2}^{\omega }(n)$ és el resultat d'escriure n en notació hereditària en base 2, i llavors substituir tots els 2s amb ω (tal com es feia en la prova del teorema de Goodstein).

• Caicedo (2007) va provar que si $n=2^{m_{1}}+2^{m_{2}}+\cdots +2^{m_{k}}$ with $m_{1}>m_{2}>\cdots >m_{k},$ aleshores

${\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$.

Alguns exemples:

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 ≈ 6.895080803×10121210694
5	$2^{2}+2^{0}$	$2^{2}+2-1$	$H_{\omega ^{\omega }+\omega }(1)-1$	$f_{\omega }(f_{0}(3))-2$	> A(4,4) > 10101019727
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) > nombre de Graham
$\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$

Aplicació a funcions computables

El teorema de Goodstein pot usar-se per construir una funció computable total que l'aritmètica de Peano no pot demostrar que sigui total. La seqüència de Goodstein d'un nombre pot ser enumerada de forma efectiva per una màquina de Turing; llavors la funció que envia n al nombre de passos requerits perquè la seqüència de Goodstein de n termini és computable per a una màquina de Turing particular. Aquesta màquina simplement enumera els termes de la corresponent seqüència i, quan aquesta arriba a 0, retorna la llargada. Atès que tota seqüència de Goodstein eventualment acaba, aquesta funció és total. Tanmateix, en l'aritmètica de Peano això no és demostrable, de manera que, en particular, no és demostrable que la màquina de Turing descrita computi una funció total.

Vegeu també

• Aritmètica no estàndard

Bibliografia

• Goodstein, R. «On the restricted ordinal theorem». Journal of Symbolic Logic, 9, 2, 1944, p. 33–41. DOI: 10.2307/2268019..
• Cichon, E. «A Short Proof of Two Recently Discovered Independence Results Using Recursive Theoretic Methods». Proceedings of the American Mathematical Society, 87, 4, 1983, p. 704–706. DOI: 10.2307/2043364..
• Caicedo, A. «Goodstein's function». Revista Colombiana de Matemáticas, 41, 2, 2007, p. 381–391..

Links Externs

• Weisstein, Eric W., «Goodstein Sequence» a MathWorld (en anglès).
• Alguns elements de la demostració que el teorema de Goodstein no és un teorema de l'AP - Tesi de Justin T Miller
• Una classificació de models no estàndards de l'Aritmètica de Peano pel teorema de Goodstein - Tesi de Dan Kaplan, Franklan and Marshall College Library
• Definició de les seqüències de Goodstein en Haskell i el càlcul lambda
• El joc de l'Hidra implementat com a applet de Java
• Implementació en Javascript d'una variant del joc de l'Hidra
• Goodstein Sequences: The Power of a Detour via Infinity - bona exposició amb il·lustracions de les seqüències de Goodstein i el joc de l'hidra.
• Calculadora de Goodstein Arxivat 2017-02-04 a Wayback Machine.