PUBLICACIONES

Sociedad Colombiana de Matemáticas:Publicaciones

Revista Colombiana de Matemáticas

Volumen 41 [2] (2007)Páginas 381 - 391

Goodstein's function

Andrés Eduardo Caicedo
California Institute of Technology, Pasadena CA, USA

Resumen.La función de Goodstein $\G:\N\to\N$ es un ejemplo de una función recursiva {\em de crecimiento rápido}. Introducida en 1944 por R. L. Goodstein \cite{Goodstein}, Kirby y Paris \cite{KirbyParis} demostraron en 1982, usando técnicas de teorí{}a de modelos, que el resultado de Goodstein de que $\G$ es {\em total}, es decir, que $\G(n)$ está definida para todo $n\in\N$, no es un teorema de la Aritmética de Peano de primer orden. Calculamos la función de Goodstein en términos de la jerarquí{}a de funciones de crecimiento rápido de Löb y Wainer; usando esto y resultados clásicos de teorí{}a de la demostración acerca de esta jerarquí{}a, el teorema de Kirby y Paris se sigue de inmediato. También calculamos las funciones de la jerarquí{}a de Hardy en términos de las funciones de Löb y Wainer, con lo que obtenemos una nueva demostración de un resultado similar, debido a Cichon \cite{Cichon}.

Abstract. Goodstein's function $\G:\N\to\N$ is an example of a {\em fast growing} recursive function. Introduced in 1944 by R. L. Goodstein \cite{Goodstein}, Kirby and Paris \cite{KirbyParis} showed in 1982, using model theoretic techniques, that Goodstein's result that $\G$ is {\em total}, i.e., that $\G(n)$ is defined for all $n\in\N$, is not a theorem of first order Peano Arithmetic. We compute Goodstein's function in terms of the Löb-Wainer fast growing hierarchy of functions; from this and standard proof theoretic results about this hierarchy, the Kirby-Paris result follows immediately. We also compute the functions of the Hardy hierarchy in terms of the Löb-Wainer functions, which allows us to provide a new proof of a similar result, due to Cichon \cite{Cichon}.

Palabras claves. Función de Goodstein, jerarquía de Hardy, jerarquía de crecimiento rápido, aritmética de Peano.

Codigo AMS. 03F30, 03D20.

Archivo completo : Formato [PDF] (464 K).