Correo Electrónico
DNINFOA - SIA
Bibliotecas
Convocatorias
Identidad U.N.
Publicado
Goodstein’s function
Función de Goodstein
Palabras clave:
Goodstein function, Hardy hierarchy, Fast growing hierarchy, Peano Arithmetic, 2000 Mathematics Subject Classification. 03F30, 03D20 (en)Función de Goodstein, Jerarquía de Hardy, Jerarquía de crecimiento rápido, Aritmética de Peano (es)
Descargas
Abstract. Goodstein’s function Ģ: ℕ → ℕ is an example of a fast growing recursive function. Introduced in 1944 by R. L. Goodstein [9], Kirby and Paris [12] showed in 1982, using model theoretic techniques, that Goodstein’s result that Ģ is total, i.e., that Ģ(n) is defined for all 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 [2].
La función de Goodstein Ģ: ℕ → ℕ es un ejemplo de una función recursiva de crecimiento rápido. Introducida en 1944 por R. L. Goodstein [9], Kirby y Paris [12] demostraron en 1982, usando técnicas de teoría de modelos, que el resultado de Goodstein de que Ģ es total, es decir, que Ģ(n) está definida para todo 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 [2].
Referencias
Ackermann, W. Die Widerspruchsfreiheit der allgemeinen Mengenlehre. Mathematische Annalen 114 (1937), 305-315.
Clchon, E. A short proof of two recently discovered independence proofs using recursion theoretic methods. Proceedings of the American Mathematical Society 87 (1983), 704- 706.
Cori, R., and Lascar, D. Mathematical Logic. A course with exercises. Part II. Oxford University Press, Oxford, 2001.
Fairtlough, M., and Wainer, S. Handbook of Proof Theory. Elsevier-North Holland, 1998, ch. Hierarchies of provably recursive functions, pp. 149-207.
Feferman, S. Systems of predicative analysis, i. The Journal of Symbolic Logic 29, 1 (1964), 1-30.
Feferman, S. Systems of predicative analysis, ii. The Journal of Symbolic Logic 33 (1968), 193-220.
Gentzen, G. Die Widerspruchsfreiheit der reinen Zahlentheorie. Mathematische Annalen 112, 1 (1936), 493-565.
Gentzen, G. Beweisbarkeit und Unbeweisbarkeit von Anfangsfällcn der transfiniten Induktion in der reinen Zahlentheorie. Mathematische Annalen 119 (1943), 140-161.
Goodstein, R. On the restricted ordinal theorem. The Journal of Symbolic Logic 9, 2 (1944), 33-41.
Hardy, G. A theorem concerning the infinite cardinal numbers. Quarterly Journal of Mathematics 35 (1904), 87-94.
Ketonen, J., and Solovay, R. Rapidly growing Ramsey functions. The Annals of Mathematics 113, 2 (1981), 267-314.
Kirby, L., and Paris, J. Accessible independence results for Peano arithmetic. Bulletin London Mathematical Society 14 (1982), 285-293.
Kunen, K. Set Theory. An introduction to independence proofs. Elsevier Science Publishers, Amsterdam, 1980.
Löb, M., and Wainer, S. Hierarchies of number theoretic functions, i. Arch. Math. Logik Grundlagenforsch 14 (1970), 39-51.
Simpson, S. Subsystems of second order arithmetic. Springer, Berlin, 1999.
Wainer, S. A classification of the ordinal recursive functions. Arch. Math. Logik Grundlagenforsch 13 (1970), 136-153.
Weyl, H. Das Kontinuum: Kritische Untersuchungen über die Grundlagen der Analysis. Chelsea, New York, 1973. Reprinted in H. Weyl, E. Landau, B. Riemann. Das Kontinuum und andere Monographien.
