Teorema de Goodstein

En llògica matemàtica, la teorema de Goodstein és una proposició sobre els número natural, demostrada per Reuben Goodstein en 1944, que establix que tota successió de Goodstein (tal com es definix més alvance) termina en 0. Laurence Kirby i Jeff Paris varen demostrar en 1982 que la teorema de Goodstein és indemostrable a partir de l'aritmètica de Peano (pero pot demostrar-se en sistemes més forts, com l'aritmètica de segon orde o els axioma de Zermelo-Fraenkel). Est va ser el tercer eixemple d'una afirmació verdadera sobre els número natural que resulta indemostrable en l'aritmètica de Peano, despuix dels eixemples proporcionats pels teoremes de incompletitud de Gödel i la demostració directa de Gerhard Gentzen en 1943 sobre la indemostrabilidad de l'inducció de ε₀ en l'aritmètica de Peano. El principi de Paris-Harrington va proporcionar un atre eixemple.

Kirby i Paris també varen introduir en teoria de grafos el joc de la hidra en un comportament similar al de les successions de Goodstein: la Hidra (cridada aixina per la criatura mitològica de múltiples caps, la Hidra de Lerna) és un arbre, i un moviment de "Hércules" consistix en tallar una de les seues "caps" (una branca de l'arbre), a lo que la Hidra respon fent créixer un número finito de nous caps segons certes regles. Kirby i Paris varen demostrar que la Hidra acabarà sent derrotada, independentment de l'estratègia que Hércules utilise per a tallar-li els caps, encara que açò pot dur molt temps. De la mateixa manera que en les successions de Goodstein, Kirby i Paris varen demostrar que no es pot provar solament en l'aritmètica de Peano.

Notació hereditària en base n

Les successions de Goodstein es definixen per mig d'un concepte cridat "notació hereditària en base n". Esta notació és molt similar a la notació usual en la notació posicional de base n per als número natural, pero la notació usual no és suficient per als propòsits de la teorema de Goodstein.

Per a obtindre la notació ordinària en base n, a on n és un número natural major que 1, un número natural arbitrari m s'escriu com una suma de múltiples de potències de n:

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

a on cada coeficient a_i satisfà 0 ≤ a_i < n i a_k ≠ 0.

Per eixemple, la notació base-3 de 100 és:

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

Ací, els exponents de n no s'escriuen en la notació de base n , com es veu en el cas 3⁴, dalt.

Per a convertir una notació en base n a una notació hereditària en base n, primer deuen reescriure's tots els exponents com una suma de potències de n (en la llimitació en els coeficients 0 ≤ a_i < n). Després, cal reescriure qualsevol exponent dins dels exponents novament en notació en base n (en la mateixa llimitació en els coeficients), i continuar d'esta manera fins que cada número que aparega en l'expressió (llevat les bases mateixes) estiga escrit en notació en base n.

Per eixemple, 100 en notació hereditària en base 3 és:

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

Successions de Goodstein

La successió de Goodstein $G_m$ d'un número m és una successió d'número natural. El primer element de la successió, escrit com $G_m(1)$, és m mateixa. El segon element, $G_m(2)$ s'obté escrivint m en notació hereditària de base 2, canviant tots els 2 per 3 i restant 1 al resultat. En general, el terme $G_m(n+1)$ de la successió de Goodstein m es calcula de la següent manera:

• Prenent la representació hereditària de base (n + 1) de $G_m(n)$
• Reemplaçant cada ocurrència de la base (n + 1) per n + 2, i després
• Restant un.

$G_m(n+1)$ depén tant de $G_m(n)$ com de l'índex n. A voltes, $G_m(n)$ s'escriu com $G_{n-1}(m)$.

Una successió de Goodstein termina quan el seu element aplega a 0. Les primeres successions de Goodstein terminen ràpidament. Per eixemple, $G_3$ termina en el sext pas (la columna etiquetada com "Notació hereditària" mostra cóm es calcula el valor):

Base	Notació hereditarria	Valor	Càlcul
2	$2^1+1$	3
3	$3^1+1-1=3^1$	3	S'obté escrivint l'últim element (3) en notació hereditària de base 2, reemplaçant tots els 2 per 3 i després restant 1.
4	$4^1-1=3$	3	S'obté escrivint l'últim element (3) en notació hereditària de base 3, reemplaçant tots els 3 per 4 i després restant 1.
5	$3-1=2$	2	S'obté restant 1 a l'últim element (3), ya que no hi ha 4 que reemplaçar.
6	$2-1=1$	1	S'obté restant 1 a l'últim element (2), ya que no hi ha 5 que reemplaçar.
7	$1-1=0$	0	S'obté restant 1 a l'últim element (1), ya que no hi ha 6 que reemplaçar.

Les successions de Goodstein posteriors aumenten durant un gran número de passos. Per eixemple, $G_4$ comença de la següent manera Plantilla:OEIS2C:

Base	Notació hereditarria	Valor
2	$2^{2^1}$	4
3	$3^{3^1}-1=2\cdot 3^2+2\cdot 3^1+2$	26
4	$2\cdot 4^2+2\cdot 4^1+1$	41
5	$2\cdot 5^2+2\cdot 5^1$	60
6	$2\cdot 6^2+2\cdot 6-1=2\cdot 6^2+6^1+5$	83
7	$2\cdot 7^2+7^1+4$	109
$⋮$	$⋮$	$⋮$
11	$2\cdot 11^2+11^1$	253
12	$2\cdot 12^2+12^1-1=2\cdot 12^2+11$	299
$⋮$	$⋮$	$⋮$
24	$2\cdot 24^2-1=24^2+23\cdot 24^1+23$	1151
$⋮$	$⋮$	$⋮$
$B=3\cdot 2^{402653209}-1$	$2\cdot B^1$	$3\cdot 2^{402653210}-2$
$B=3\cdot 2^{402653209}$	$2\cdot B^1-1=B^1+(B-1)$	$3\cdot 2^{402653210}-1$
$⋮$	$⋮$	$⋮$

Els elements de $G_4$ continuen aumentant durant un temps, pero en la base $3\cdot 2^{402653209}$, alcancen el màxim de $3\cdot 2^{402653210}-1$, es mantenen allí durant els següents $3\cdot 2^{402653209}$ passos i després comencen a descendir d'un en un, aplegant a 0 quan la base alcança $3\cdot 2^{402653211}-1.$. L'exponent ací és igual a $3\cdot 2^{27}+27,$, per lo que la base és igual a $n\cdot 2^n-1,$ el número de Woodall en $n=3\cdot 2^{27}.$

Per un atre costat, $G_{19}$ aumenta molt més ràpidament i comença com a continuació:

Notació hereditarria	Valor
$2^{2^2}+2^1+1$	19
$3^{3^3}+3^1$	7 625 597 484 990
$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^{36305}$
$7^{7^7}$	$\approx 3.8\times 10^{695974}$
$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^1+7$	$\approx 6.0\times 10^{15151335}$
$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^1+6$	$\approx 5.6\times 10^{35942384}$
$⋮$	$⋮$

A pesar d'este ràpit creiximent, la teorema de Goodstein establix que tota successió de Goodstein termina en 0, independentment del valor inicial.

Vore també

• Aritmètica no estàndar
• Jerarquia de ràpit creiximent
• Principi de París-Harrington
• Teorema de Kanamori-McAloon
• Teorema dels arbres de Kruskal
• Rompecabezas de cordes cremades

Bibliografia

• “Accessible Independence Results for Peano Arithmetic” . London Mathematical Society 14 (4): 285. doi:10.1112/blms/14.4.285.
• Plantilla:Cite arXiv

• Goodstein, R.. “On the restricted ordinal theorem”. Journal of Symbolic Logic 9 (2): 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): 704–706. doi:10.2307/2043364.
• Caicedo, A.. “Goodstein's function”. Revista Colombiana de Matemàtiques 41 (2): 381–391.