A walk with Goodstein. (English) Zbl 07828956
Summary: Goodstein’s principle is arguably the first purely number-theoretic statement known to be independent of Peano arithmetic. It involves sequences of natural numbers which at first appear to diverge, but eventually decrease to zero. These sequences are defined relative to a notation system based on exponentiation for the natural numbers. In this article, we provide a self-contained and modern analysis of Goodstein’s principle, obtaining some variations and improvements. We explore notions of optimality for notation systems and apply them to the classical Goodstein process and to a weaker variant based on multiplication rather than exponentiation. In particular, we introduce the notion of base-change maximality, and show how it leads to far-reaching extensions of Goodstein’s result. We moreover show that by varying the initial base of the Goodstein process, one readily obtains independence results for each of the fragments \(\mathsf{I}\Sigma_n\) of Peano arithmetic.
MSC:
| 03F40 | Gödel numberings and issues of incompleteness |
| 03D20 | Recursive functions and relations, subrecursive hierarchies |
| 03D60 | Computability and recursion theory on ordinals, admissible sets, etc. |
References:
| [1] | Arai, T., Fernández-Duque, D., Wainer, S. S., and Weiermann, A., Predicatively unprovable termination of the Ackermannian Goodstein process. Proceedings of the American Mathematical Society, vol. 148 (2020), no. 8, pp. 3567-3582. · Zbl 1484.03125 |
| [2] | Cichon, E. A., A short proof of two recently discovered independence results using recursion theoretic methods. Proceedings of the American Mathematical Society, vol. 87 (1983), no. 4, pp. 704-706. · Zbl 0512.03028 |
| [3] | Cichon, E. A., Buchholz, W., and Weiermann, A., A uniform approach to fundamental sequences and hierarchies. Mathematical Logic Quarterly, vol. 40 (1994), pp. 273-286. · Zbl 0812.03023 |
| [4] | Clote, P. and Mcaloon, K., Two further combinatorial theorems equivalent to the 1-consistency of Peano arithmetic. The Journal of Symbolic Logic, vol. 48 (1983), no. 4, pp. 1090-1104. · Zbl 0545.03033 |
| [5] | Erickson, J., Nivasch, G., and Xu, J., Fusible numbers and Peano arithmetic. Logical Methods in Computer Science, vol. 18 (2022), no. 3, pp. 6:1-6:26. · Zbl 07577570 |
| [6] | Fairtlough, M. and Wainer, S. S., Hierarchies of provably recursive functions, Handbook of Proof Theory (Buss, Samuel R., editor), Elsevier, New York, 1998, pp. 149-207. · Zbl 0961.03053 |
| [7] | Fernández-Duque, D. and Weiermann, A., Fast Goodstein walks, preprint, 2022, arXiv:2111.15328. |
| [8] | Fernández-Duque, D. and Weiermann, A., Fundamental sequences and fast-growing hierarchies for the Bachmann-Howard ordinal, Preprint, 2024, arXiv:2203.07758. |
| [9] | Gödel, K., Über Formal Unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme, I. Monatshefte für Mathematik und Physik, vol. 38 (1931), pp. 173-198. · JFM 57.0054.02 |
| [10] | Goodstein, R. L., On the restricted ordinal theorem. The Journal of Symbolic Logic, vol. 9 (1944), no. 2, pp. 33-41. · Zbl 0060.02306 |
| [11] | Goodstein, R. L., Transfinite ordinals in recursive number theory. The Journal of Symbolic Logic, vol. 12 (1947), no. 4, pp. 123-129. · Zbl 0030.00401 |
| [12] | Hájek, P. and Paris, J., Combinatorial principles concerning approximations of functions. Archiv für mathematische Logik und Grundlagenforschung, vol. 26 (1987), pp. 13-28. · Zbl 0645.03057 |
| [13] | Kanamori, A. and Mcaloon, K., On Gödel incompleteness and finite combinatorics. Annals of Pure and Applied Logic, vol. 33 (1987), pp. 23-41. · Zbl 0627.03041 |
| [14] | Kirby, L., Flipping properties in arithmetic. The Journal of Symbolic Logic, vol. 47 (1982), no. 2, pp. 416-422. · Zbl 0488.03031 |
| [15] | Kirby, L. and Paris, J., Accessible independence results for Peano arithmetic. Bulletin of the London Mathematical Society, vol. 14 (1982), no. 4, pp. 285-293. · Zbl 0501.03017 |
| [16] | Loebl, M. and Nešetřil, J., An unprovable Ramsey-type theorem. Proceedings of the American Mathematical Society, vol. 116 (1992), no. 3, pp. 819-824. · Zbl 0773.05098 |
| [17] | Meskens, F. and Weiermann, A., Classifying phase transition thresholds for Goodstein sequences and hydra games, Gentzen’s Centenary: The Quest for Consistency (Kahle, R. and Rathjen, M., editors), Springer, Cham, 2015, pp. 455-478. · Zbl 1378.03040 |
| [18] | Paris, J. and Harrington, L., A mathematical incompleteness in Peano arithmetic, Handbook of Mathematical Logic (Barwise, J., editor), North-Holland, Amsterdam, 1977, pp. 1133-1142. |
| [19] | Rathjen, M., Goodstein’s theorem revisited, Gentzen’s Centenary: The Quest for Consistency (Kahle, R. and Rathjen, M., editors), Springer, Cham, 2015, pp. 229-242. · Zbl 1378.03048 |
| [20] | Schmidt, D., Built-up systems of fundamental sequences and hierarchies of number-theoretic functions. Archive for Mathematical Logic, vol. 18 (1977), no. 1, pp. 47-53. · Zbl 0358.02061 |
| [21] | Wainer, S. S. and Buchholz, W., Provably computable functions and the fast growing hierarchy, Logic and Combinatorics (Simpson, S. G., editor), Contemporary Mathematics, vol. 65, American Mathematical Society, Providence, 1987, pp. 179-198. · Zbl 0635.03056 |
| [22] | Weiermann, A., Classifying the provably total functions of PA, this Journal, vol. 12 (2006), no. 2, pp. 177-190. · Zbl 1118.03053 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
