One of the most important principles of J.-Y. Girard's Π 2 1 -logic is induction on dilators. In particular, Girard used this principle to construct his famous functor Λ. He claimed that the totality of Λ is equivalent to the set existence axiom of Π 1 1 -comprehension from reverse mathematics. While Girard provided a plausible description of a proof around 1980, it seems that the very technical details have not been worked out to this day. A few years ago, a loosely related approach led to an equivalence between Π 1 1 -comprehension and a certain Bachmann-Howard principle. The present paper closes the circle. We relate the Bachmann-Howard principle to induction on dilators. This allows us to show that Π 1 1 -comprehension is equivalent to the totality of a functor J due to P. Päppinghaus, which can be seen as a streamlined version of Λ.

Hardy functions are defined by transfinite recursion and provide upper bounds for the growth rate of the provably total computable functions in various formal theories, making them an essential ingredient in many proofs of independence. Their definition is contingent on a choice of fundamental sequences, which approximate limits in a ‘canonical’ way. In order to ensure that these functions behave as expected, including the aforementioned unprovability results, these fundamental sequences must enjoy certain regularity properties. In this article, we prove that Buchholz's system of fundamental sequences for the ϑ function enjoys such conditions, including the Bachmann property. We partially extend these results to variants of the ϑ function, including a version without addition for countable ordinals. We conclude that the Hardy functions based on these notation systems enjoy natural monotonicity properties and majorize all functions defined by primitive recursion along the Bachmann Howard ordinal.

Abstract Japaridze’s provability logic ${\operatorname {GLP}}$ has one modality $[n]$ for each natural number and has been used by Beklemishev for a proof theoretic analysis of Peano arithmetic (${\operatorname {PA}}$) and related theories. Among other benefits, this analysis yields the so-called Every Worm Dies (${\operatorname {EWD}}$) principle, a natural combinatorial statement independent of ${\operatorname {PA}}$. Recently, Beklemishev and Pakhomov have studied notions of provability corresponding to transfinite modalities in ${\operatorname {GLP}}$. We show that indeed the natural transfinite extension of ${\operatorname {GLP}}$ is sound for this interpretation and yields independent combinatorial principles for the second-order theory ${\operatorname {ACA}}$ of arithmetical comprehension with full induction. We also provide restricted versions of ${\operatorname {EWD}}$ related to the fragments ${\operatorname {I\varSigma }}_n$ of PA. In order to prove the latter, we show that standard Hardy functions majorize their variants based on tree ordinals.

The article concerns subrecursive computability of real numbers. Certain significant real numbers are shown to be M2-computable, and the set of the M2-computable real numbers is shown to be closed under the elementary functions of calculus.

Motivated by the classical Ramsey for pairs problem in reverse mathematics, we investigate the recursion-theoretic complexity of certain assertions which are related to the Erdös–Szekeres theorem. We show that resulting density principles give rise to Ackermannian growth. We then parameterize these assertions with respect to a number theoretic function f and investigate for which functions f Ackermannian growth is still preserved. We show that this is the case for f(i) = i1Ack−1(i) but not for f(i)=1iAd−1(i).

Harvey Friedman introduced natural independence results for the Peano axioms (PA) via certain schemes of combinatorial well-foundedness. We consider in this article parameterized versions of a specific Friedman-style scheme and classify exactly the threshold for the transition from provability to unprovability in PA. For this purpose we fix a natural Schütte-style bijection between the ordinals below ε0 and the positive integers. This coding induces a natural well ordering ≺ on the positive integers. Using bounds on the asymptotic of the resulting global count functions we classify precisely the phase transition for the parameterized hierarchy of elementary descent recursive functions and hence for the combinatorial well-foundedness scheme. Let CWF(g) be the assertion that for all natural numbers K there exists a natural number M which is so large that there does not exist a strictly ≺-descending sequence m0,…,mM of positive integers such that for every i with 0 ≤ i ≤ M we have that mi ≤ K + g(i). For classifying the provable from the unprovable version of CWF(g) (as a problem depending on g) let fα(i):=i|i|Fα-1(i) where | · |k denotes the k-times iterated binary length function and where Fα-1 denotes the functional inverse of the α-th function from the fast growing hierarchy. Then our main result is: PA proves CWF (fα) iff α < ɛ0.

We investigate natural systems of fundamental sequences for ordinals below the Howard–Bachmann ordinal and study growth rates of the resulting slow growing hierarchies. We consider a specific assignment of fundamental sequences that depends on a non-negative real number greater than zero is one of the biggest jumps in growth rates for subrecursive hierarchies one might think of.

Abstract Forαless thanε0letNαbe the number of occurrences ofωin the Cantor normal form ofα. Further let ∣n∣ denote the binary length of a natural numbern, let ∣n∣hdenote theh-times iterated binary length ofnand let inv(n) be the leasthsuch that ∣n∣h≤ 2. We show that for any natural numberhfirst order Peano arithmetic, PA, does not prove the following sentence: For allKthere exists anMwhich bounds the lengthsnof all strictly descending sequences 〈α0, …,αn〉 of ordinals less thanε0which satisfy the condition that the NormNαiof thei-th termαiis bounded byK+ ∣i∣ · ∣i∣i. As a supplement to this (refined Friedman style) independence result we further show that e.g., primitive recursive arithmetic, PRA, proves that for allKthere is anMwhich bounds the lengthnof any strictly descending sequence 〈α0, …,αn〉 of ordinals less thanε0which satisfies the condition that the NormNαiof thei-th termαiis bounded byK+ ∣i∣ · inv(i). The proofs are based on results from proof theory and techniques from asymptotic analysis of Polya-style enumerations. Using results from Otter and from Matoušek and Loebl we obtain similar characterizations for finite bad sequences of finite trees in terms of Otter's tree constant 2.9557652856.…

Abstract It is shown that the so called slow growing hierarchy depends non trivially on the choice of its underlying structure of ordinals. To this end we investigate the growth rate behaviour of the slow growing hierarchy along natural subsets of notations for Γ0. Let T be the set-theoretic ordinal notation system for Γ0 and Ttree the tree ordinal representation for Γ0. It is shown in this paper that (Gα)α∈T matches up with the class of functions which are elementary recursive in the Ackermann function as does (by folklore). By thinning out terms in which the addition function symbol occurs we single out subsystems T* ⊆ T and Ttree* ⊆ Ttree (both of order type not exceeding ε0) and prove that still matches up with but now consists of elementary recursive functions only. We discuss the relationship between these results and the Γ0-based termination proof for the standard rewrite system for the Ackermann function.

Abstract Inspired by Pohlers' local predicativity approach to Pure Proof Theory and Howard's ordinal analysis of bar recursion of type zero we present a short, technically smooth and constructive strong normalization proof for Gödel's system T of primitive recursive functionals of finite types by constructing an ε0-recursive function []0: T → ω so that a reduces to b implies [a]0 > [b]0. The construction of [ ]0 is based on a careful analysis of the Howard-Schütte treatment of Gödel's T and utilizes the collapsing function ψ: ε0 → ω which has been developed by the author for a local predicativity style proof-theoretic analysis of PA. The construction of [ ]0 is also crucially based on ideas developed in the 1995 paper “A proof of strongly uniform termination for Gödel's T by the method of local predicativity” by the author. The results on complexity bounds for the fragments of T which are obtained in this paper strengthen considerably the results of the 1995 paper. Indeed, for given n let Tn be the subsystem of T in which the recursors have type level less than or equal to n + 2. (By definition, case distinction functionals for every type are also contained in Tn.) As a corollary of the main theorem of this paper we obtain (reobtain?) optimal bounds for the Tn-derivation lengths in terms of ω+2-descent recursive functions. The derivation lengths of type one functionals from Tn (hence also their computational complexities) are classified optimally in terms of <ωn+2 -descent recursive functions. In particular we obtain (reobtain?) that the derivation lengths function of a type one functional a ∈ T0 is primitive recursive, thus any type one functional a in T0 defines a primitive recursive function. Similarly we also obtain (reobtain?) a full classification of T1 in terms of multiple recursion. As proof-theoretic corollaries we reobtain the classification of the IΣn+1-provably recursive functions. Taking advantage from our finitistic and constructive treatment of the terms of Gödel's T we reobtain additionally (without employing continuous cut elimination techniques) that PRA + PRWO(ε0) ⊢ Π20 − Refl(PA) and PRA + PRWO(ωn+2) ⊢ Π20 − Refl(IΣn+1), hence PRA + PRWO(ε0) ⊢ Con(PA) and PRA + PRWO(ωn+2) ⊢ Con(IΣn+1). For programmatic reasons we outline in the introduction a vision of how to apply a certain type of infinitary methods to questions of finitary mathematics and recursion theory. We also indicate some connections between ordinals, term rewriting, recursion theory and computational complexity.

Abstract Inspired by Pohlers' proof-theoretic analysis of KPω we give a straightforward non-metamathematical proof of the (well-known) classification of the provably total functions of PA, PA + TI(⊰ ↾) (where it is assumed that the well-ordering ⊰ has some reasonable closure properties) and KPω. Our method relies on a new approach to subrecursion due to Buchholz, Cichon and the author.

Abstract Let Ω be the least uncountable ordinal. Let be the category where the objects are the countable ordinals and where the morphisms are the strictly monotonic increasing functions. A dilator is a functor on which preserves direct limits and pullbacks. Let τ < ΩE ≔ min{ξ > Ω: ξ = ωξ}. Then τ has a unique “term”-representation in Ω. λξη.ωξ + η and countable ordinals called the constituents of τ. Let δ < Ω and K(τ) be the set of the constituents of τ. Let β = max K(τ). Let [β] be an occurrence of β in τ such that τ[β] = τ. Let be the fixed point-free version of the binary Aczel-Buchholz-Feferman-function (which is defined explicitly in the text below) which generates the Bachman-hierarchy of ordinals. It is shown by elementary calculations that is a dilator for every γ > max{β.δ.ω}.

Abstract Let Ω ≔ ℵ1. For any α< εΩ + 1 ≔ min {ξ > Ω: ξ = ωξ} let EΩ(α) be the finite set of ε-numbers below Ω which are needed for the unique representation of α in Cantor-normal form using 0, Ω, +, and ω. Let α* ≔ max(EΩ(α) ∪ {0}). A function f: εΩ + 1 → Ω is called essentially increasing, if for any α < εΩ + 1; f(α) ≥ α*: f is called essentially monotonic, if for any α, β<εΩ + 1; Let be the least set of ordinals which contains 0 as an element and which satisfies the following two conditions: (a) (b) Let be the Howard-Bachmann ordinal, which is, for example, defined in [3]. The following theorem is shown: If f: εΩ + 1 → Ω is essentially monotonic and essentially increasing, then the order type of is less than or equal to .