On inverse Goodstein sequences

• Patrick Uftring ^[1]
  1. [1] University of Würzburg

     University of Würzburg

     Kreisfreie Stadt Würzburg, Alemania

     
• Localización: Selecta Mathematica, New Series, ISSN 1022-1824, Vol. 31, Nº. 4, 2025
• Idioma: inglés
• DOI: 10.1007/s00029-025-01071-4
• Enlaces
  • Texto completo
• Resumen

  • In the late 1980s, Abrusci, Girard and van de Wiele defined a variant of Goodstein sequences: the so-called inverse Goodstein sequence. In their work, they show that it terminates precisely at the Bachmann–Howard ordinal. This reveals that a proof of this fact requires substantial consistency strength. Moreover, the authors could show that sequences of this kind terminate even if the hereditary base change at the heart of their construction is replaced by a generalization using arbitrary dilators. It has been a conjecture by Andreas Weiermann that this more general result has a connection to Bachmann–Howard fixed points and is, therefore, equivalent to one of the most famous strong set existence principles from reverse mathematics: Π11\Pi^1_1Π11-comprehension. In this article, we prove this conjecture to be correct. Moreover, we show that the ordinal at which such sequences terminate is, in a fundamental way, isomorphic to the 1-fixed point of their dilator, a new concept introduced by Freund and Rathjen. This yields explicit notation systems and a general method for specifying such ordinals. Also, using the notation systems provided by 1-fixed points, we can reproduce the result that the Goodstein sequence terminates at the Bachmann–Howard ordinal in a weak system. Additionally, we perform a similar computation for a variant of Goodstein sequences, which terminates at a predicative ordinal.

• Referencias bibliográficas
  • Abrusci, V. M.: Dilators, generalized Goodstein sequences, independence results: a survey, Logic and combinatorics (Arcata, Calif., 1985),...
  • Abrusci, V. M., Girard, J.-Y., van de Wiele, J.: Some uses of dilators in combinatorial problems. I, Logic and combinatorics (Stephen G. Simpson,...
  • Abrusci, V.M., Girard, J.-Y., van de Wiele, J.: Some uses of dilators in combinatorial problems. II. J. Symbolic Logic 55(1), 32–40 (1990) Aguilera,...
  • Arai, T., Fernández-Duque, D., Wainer, S., Weiermann, A.: Predicatively unprovable termination of the Ackermannian Goodstein process. Proc....
  • Buchholz, W.: A new system of proof-theoretic ordinal functions. Ann. Pure Appl. Logic 32(3), 195–207 (1986)
  • Buchholz, W.: A survey on ordinal notations around the Bachmann-Howard ordinal, Feferman on foundations (Gerhard Jäger and Wilfried Sieg,...
  • Cichon, E.A.: A short proof of two recently discovered independence results using recursion theoretic methods. Proc. Amer. Math. Soc. 87(4),...
  • Feferman, S.: Systems of predicative analysis. J. Symbolic Logic 29, 1–30 (1964)
  • Fodor, G.: Eine Bemerkung zur Theorie der regressiven Funktionen. Acta Sci. Math. (Szeged) 17, 139–142 (1956)
  • Freund, A.: A Higher Bachmann-Howard Principle, arXiv:1704.01662, pp. 1–65 (2018)
  • Freund, A.: Type-Two Well-Ordering Principles, Admissible Sets, and 11^11-Comprehension, Ph.D. thesis, University of Leeds, 3, (2018). http://etheses.whiterose.ac.uk/20929/
  • Freund, A.: A categorical construction of Bachmann-Howard fixed points. Bull. Lond. Math. Soc. 51(5), 801–814 (2019)
  • Freund, A.: 11^11-comprehension as a well-ordering principle. Adv. Math. 355, 106767 (2019)
  • Freund, A.: Computable aspects of the Bachmann-Howard principle. J. Math. Log. 20(2), 2050006 (2020)
  • Freund, A.: Predicative collapsing principles. J. Symb. Log. 85(1), 511–530 (2020)
  • Freund, A.: Impredicativity and Trees with Gap Condition: A Second Course on Ordinal Analysis, pp. 1–34 (2022), arXiv:2204.09321
  • Freund, A.: Patterns of resemblance and Bachmann-Howard fixed points. Selecta Math. (N.S.) 28(1), 19 (2022)
  • Freund, A.: Reverse mathematics of a uniform Kruskal-Friedman theorem, (2022), arXiv:2112.08727, pp. 1–25
  • Freund, A.: Bachmann-Howard derivatives. Arch. Math. Logic 62(5–6), 581–618 (2023)
  • Freund, A., Rathjen, M.: Well ordering principles for iterated 11^11-comprehension. Selecta Math. (N.S.) 29(5), 76 (2023)
  • Freund, A., Rathjen, M., Weiermann, A.: Minimal bad sequences are necessary for a uniform Kruskal theorem. Adv. Math. 400, 108265 (2022)
  • Friedman, H.M., Hirst, J.L.: Weak comparability of well orderings and reverse mathematics. Ann. Pure Appl. Logic 47(1), 11–29 (1990)
  • Girard, J.-Y.: 12^22-logic. I. Dilators. Ann. Math. Logic 21(2–3), 75–219 (1981)
  • Goodstein, R.L.: On the restricted ordinal theorem. J. Symbolic Logic 9, 33–41 (1944)
  • Hirst, J.L.: Reverse mathematics and ordinal exponentiation. Ann. Pure Appl. Logic 66(1), 1–18 (1994)
  • Kirby, L., Paris, J.: Accessible independence results for Peano arithmetic. Bull. London Math. Soc. 14(4), 285–293 (1982)
  • Marcone, A.: On the logical strength of Nash-Williams’ theorem on transfinite sequences, Logic: from foundations to applications (Staffordshire,...
  • Charles Steinhom, and John Truss, eds.), Oxford Sci. Publ., Oxford Univ. Press, New York, pp. 327–351 (1996)
  • Marcone, A., Montalbán, A.: On Fraïssé’s conjecture for linear orders of finite Hausdorff rank. Ann. Pure Appl. Logic 160(3), 355–367 (2009)
  • Marcone, A., Montalbán, A.: The Veblen functions for computability theorists. J. Symbolic Logic 76(2), 575–602 (2011)
  • Rathjen, M.: Untersuchungen zu Teilsystemen der Zahlentheorie zweiter Stufe und der Mengenlehre mit einer zwischen Π21\Pi^1_2Π21​-CA und Π21\Pi^1_2Π21​-CA...
  • Beweisstärke, Ph.D. thesis, Westfälische Wilhelms-Universität Münster, (1988), pp. iv+134
  • Rathjen, M.: Lecture notes: Selected topics in proof theory, (1989), Münster University
  • Rathjen, M.: The realm of ordinal analysis, Sets and Proofs (S. Barry Cooper and John K. Truss, eds.), London Mathematical Society Lecture...
  • Rathjen, M.: Investigations of subsystems of second order arithmetic and set theory in strength between Π11\Pi^1_1Π11​-CA and Π21\Pi^1_2Π21​-CA...
  • Ontos Math. Log., vol. 2, Ontos Verlag, Heusenstamm, pp. 363–439 (2010)
  • Rathjen,M.: Goodstein’s theorem revisited, Gentzen’s centenary (Reinhard Kahle and Michael Rathjen, eds.), Springer, Cham, pp. 229–242 (2015)
  • Rathjen, M., Sieg, W.: Proof Theory, The Stanford Encyclopedia of Philosophy (Edward N. Zalta and Uri Nodelman, eds.), Metaphysics Research...
  • Rathjen, M., Weiermann, A.: Proof-theoretic investigations on Kruskal’s theorem. Ann. Pure Appl. Logic 60(1), 49–88 (1993)
  • Rathjen, M., Weiermann, A.: Reverse mathematics and well-ordering principles, Computability in context (S Barry Cooper and Andrea Sorbi, eds.),...
  • Simpson, S. G.: Subsystems of second order arithmetic, second ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association...
  • Tanaka, K.: The Galvin-Prikry theorem and set existence axioms. Ann. Pure Appl. Logic 42(1), 81–104 (1989)
  • Tanaka, K.: Weak axioms of determinacy and subsystems of analysis. I. Σ20\Sigma^0_2Σ20​ games. Z. Math. Logik Grundlag. Math. 36(6), 481–491...
  • Uftring, P.: Weak and strong versions of effective transfinite recursion. Ann. Pure Appl. Logic 174(4), 103232 (2023)
  • Uftring, P.: Well-ordering principles across reverse mathematics, Ph.D. thesis, University of Würzburg, pp. x+263 (2025)
  • van der Meeren, J.: Connecting the two worlds: well-partial-orders and ordinal notation systems, Ph.D. thesis, Ghent University, pp. iv+199...
  • van der Meeren, J., Rathjen, M., Weiermann, A.: An order-theoretic characterization of the Howard-Bachmann-hierarchy. Arch. Math. Logic 56(1–2),...