Goodstein at the Second Threshold: An independence Result for 𝖨𝖣 𝟤 \sf ID_{2}

Oriola Gjetaj, Andreas Weiermann · 2026

Read Goodstein at the Second Threshold: An independence Result for 𝖨𝖣 𝟤 \sf ID_{2} by Oriola Gjetaj, Andreas Weiermann (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-00771.txt.

Introduction

Gjetaj and Weiermann generalize the classical Goodstein process with a new process based on the Hardy hierarchy. They build an ordinal notation system using a two-step collapsing procedure, yielding a proof-theoretic ordinal, and define k-normal forms for natural numbers within it. Their Goodstein-type process cannot be shown to terminate in ID2. ID2 is the theory of non-iterated positive inductive definitions with two operators. That marks a fresh independence finding at the second proof-theoretic threshold.

Catalog record

CREATOROriola Gjetaj, Andreas Weiermann
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE167864
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.00771

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Goodstein at the Second Threshold: An independence Result for 𝖨𝖣 𝟤 \sf ID_{2} Oriola Gjetaj, Andreas Weiermann Abstract . The classical Goodstein process, defined via hereditary base- k k exponential normal form, is a well-known example of a principle unprovable in Peano Arithmetic. In this paper, we generalize this framework by constructing a new Goodstein process based on the Hardy hierarchy. We develop an ordinal notation system utilizing a two-step collapsing procedure, which yields a proof-theoretic ordinal of ψ 0 ​ ψ 1 ​ ( ε Ω 2 + 1 ) \psi_{0}\psi_{1}(\varepsilon_{{\Omega}_{2}+1}) . By defining k k -normal forms for natural numbers within this system, we introduce a Goodstein-type process and demonstrate that the theory of non-iterated positive inductive definitions for two operators ( 𝖨𝖣 2 \mathsf{ID}_{2} ) cannot prove its termination. This result establishes a new independence result at the second proof-theoretic threshold, further extending the reach of Goodstein-type principles beyond the Bachmann–Howard level. 1. Introduction Goodstein’s theorem [ 12 ] is a natural instance of Gödel’s incompleteness phenomenon: its formalization in first–order arithmetic is true but unprovable in \mathsf{PA} . The usual proof proceeds by transfinite induction up to \varepsilon_{0} , which is itself not provable in \mathsf{PA} . Kirby and Paris later showed that the Goodstein principle is independent of \mathsf{PA} [ 14 ] . Goodstein’s original process is defined on natural numbers written in hereditary base– k exponential normal form and concerns the termination of certain fast-growing sequences of natural numbers. Say that m is in nested (exponential) base- k normal form if it is written in standard exponential base k , with each exponent written in turn in base k . Thus for example, 20 would become 2^{2^{2}}+2^{2} in nested base- 2 normal form. Then, define a sequence (g_{k}(0))_{m\in\mathbb{N}} by setting g_{0}(m)=m and defining g_{k+1}(m) recursively by writing g_{k}(m) in nested base- (k+2) normal form, replacing every occurrence of k+2 by k+3 , then subtracting one (unless g_{k}(m)=0 , in which case g_{k+1}(m)=0 ). In the case that m=20 , we obtain \displaystyle g_{0}(20) \displaystyle=20=2^{2^{2}}+2^{2} \displaystyle g_{1}(20) \displaystyle=3^{3^{3}}+3^{3}-1=3^{3^{3}}+3^{2}\cdot 2+3\cdot 2+2 \displaystyle g_{2}(20) \displaystyle=4^{4^{4}}+4^{2}\cdot 2+4\cdot 2+2-1=4^{4^{4}}+4^{2}\cdot 2+4\cdot 2+1, and so forth. At first glance, these numbers seem to grow superexponentially. It should thus be a surprise that, as Goodstein showed, for every m there is k^{*} for which g_{k^{*}}(m)=0 . By coding finite Goodstein sequences as natural numbers in a standard way, Goodstein’s principle can be formalized in the language of arithmetic, but this formalized statement is unprovable in \mathsf{PA} . Independence can be shown by proving that the Goodstein process takes at least as long as stepping down the fundamental sequences below \varepsilon_{0} ; these are canonical sequences (\xi[n])_{n<\omega} such that \xi[n]<\xi for all \xi and for limit \xi , \xi[n]\to\xi as n\to\infty . For standard fundamental sequences below \varepsilon_{0} , \mathsf{PA} does not prove that the sequence \xi>\xi[1]>\xi[1][2]>\xi[1][2][3]\ldots is finite. Cichon later gave a shorter proof by relating Goodstein process to the fast - growing hierarchy F_{\alpha} and the ordinal - recursion characterization of the provably total functions of \mathsf{PA} . [ 7 ] These developments are part of a broader interaction between Goodstein - type processes, fast - growing hierarchies and proof - theoretic ordinal analysis [ 5 , 16 , 8 ] . Buchholz, Cichon, and Weiermann [ 3 ] gave a uniform treatment of fundamental sequences and Hardy fast - growing hierarchy, which supports many later independence results. Ketonen and Solovay’s analysis of the Paris–Harrington theorem linked finite combinatorics to the same hierarchy, yielding another natural \mathsf{PA} - independent statement. [ 13 ] Goodstein processes have since been extended well beyond the \varepsilon_{0} - level. Arai, Wainer, and Weiermann [ 2 ] introduced Goodstein sequences using parametrized Ackermann-Péter functions. They showed that each of these sequences terminates and is independent of a range of theories: \mathsf{PRA},\mathsf{PA},\sf\Sigma_{1}^{1}-DC_{0},\mathsf{ATR}_{0} up to \mathsf{ID}_{1} . Crucially, they employed tree ordinals to obtain their results. Arai, Fernández-Duque, Wainer, and Weiermann [ 1 ] developed Ackermannian Goodstein principles independent of \mathsf{ATR}_{0} , using an elaborate ‘sandwiching’ procedure first introduced in [ 18 ] . Later, Fernández-Duque et al. [ 9 ] consider simpler, and arguably more intuitive, normal forms, also based on the Ackermann function, giving rise to three Goodstein-like processes, independent of \mathsf{ACA}_{0},\mathsf{ACA}_{0}^{{}^{\prime}} and \mathsf{ACA}_{0}^{+} , respectively. More recently, Fernández - Duque and Weiermann introduced a new variant of the classic Goodstein process, Fast Goodstein Walks [ 11 ] based on a family (\mathcal{A}_{k})_{k<\omega} of fast-growing functions defined by transfinite recursion below \varepsilon_{0} . They demonstrate that these walks always terminate and obtained independence results at the Bachmann-Howard ordinal for \mathsf{ID}_{1} and related systems such as Kripke-Platek set theory. In further work [ 10 ] they developed the notion of base–change maximality and show that by varying the initial base of the Goodstein process, one readily obtains independence results for each of the fragments \sf I\Sigma^{0}_{n} of Peano arithmetic. We extend this line of work from the Bachmann–Howard level to a new independence result for \mathsf{ID}_{2} . We construct an ordinal notation system for |\mathsf{ID}_{2}| following Buchholz–Schütte [ 4 ] and design a Goodstein process using a Bachmann–Howard Hardy hierarchy. We show the termination of this Goodstein principle and obtain a new natural statement independent of \mathsf{ID}_{2} . In our setting, the collapse is a two step procedure, where \psi_{0} ordinals collapse to Hardy functions and \psi_{1} ordinals to \psi_{0} ordinals, avoiding the simultaneous definition of [ 4 ] . This gives a more detailed framework for analyzing Goodstein process, while working entirely with countable ordinals and avoiding a Hardy hierarchy at \varepsilon_{\Omega_{1}+1} . The underlying system of fundamental sequences enjoys the Bachmann property (due to Buchholz [ 6 ] , in the formulation of Weiermann [ 16 ] ), which is crucial for transferring proof–theoretic facts to our Goodstein process. The proof proceeds in four steps. First, an ordinal notation system is constructed for the theory |\mathsf{ID}2| via a two-step collapsing procedure, providing a framework for ordinals below the proof-theoretic ordinal of the theory. Second, define a fast-growing hierarchy to represent natural numbers as k -normal forms, embedding these numbers into our ordinal system. In our case, this is the Hardy hierarchy. Third, define a monotone base-change operation on these representations, which controls the dynamics of our Goodstein process. Finally, assign an ordinal to each natural number such that every step of our Goodstein process corresponds to a strict descent in our notation system. By showing that this process grows at least as quickly as the fast-growing hierarchy F_{|\mathsf{ID}2|} , it is shown that its termination cannot be proven in \mathsf{ID}_{2} . The paper is organized as follows. In Section 2 , following Buchholz and Schütte [ 4 ] , we construct the relevant ordinal notation system and recall the proof-theoretic facts needed later. Section 3 develops structural properties of this system for |\mathsf{ID}2| , providing the groundwork for our Goodstein process. In Section 4 we introduce a Hardy-like hierarchy to express natural numbers and define the associated Goodstein process. Then we obtain termination via an ordinal assignment into |\mathsf{ID}2| . Finally, in Section 5 we show that \mathsf{ID}_{2} does not prove this termination, yielding an independence result at the second proof-theoretic threshold. 1.1. Notation and

Read the complete text