In this paper we calibrate the exact proof-theoretic strength of Kruskal's theorem, thereby giving, in some sense, the most elementary proof of Kruskal's theorem. Furthermore, these investigations give rise to ordinal analyses of restricted bar induction.

In this article we give a unifying approach to the theory of fundamental sequences and their related Hardy hierarchies of number-theoretic functions and we show the equivalence of the new approach with the classical one.

The fact that “natural” theories, i.e. theories which have something like an “idea” to them, are almost always linearly ordered with regard to logical strength has been called one of the great mysteries of the foundation of mathematics. However, one easily establishes the existence of theories with incomparable logical strengths using self-reference . As a result, PA+Con is not the least theory whose strength is greater than that of PA. But still we can ask: is there a sense in which (...) PA+Con is the least “natural” theory whose strength is greater than that of PA? In this paper we exhibit natural theories in strength strictly between PA and PA+Con by introducing a notion of slow consistency. (shrink)

For α less than ε0 let $N\alpha$ be the number of occurrences of ω in the Cantor normal form of α. Further let $\mid n \mid$ denote the binary length of a natural number n, let $\mid n\mid_h$ denote the h-times iterated binary length of n and let inv(n) be the least h such that $\mid n\mid_h \leq 2$ . We show that for any natural number h first order Peano arithmetic, PA, does not prove the following sentence: For all (...) K there exists an M which bounds the lengths n of all strictly descending sequences $\langle \alpha_0, ..., \alpha_n\rangle$ of ordinals less than ε0 which satisfy the condition that the Norm $N\alpha_i$ of the i-th term αi is bounded by $K + \mid i \mid \cdot \mid i\mid_h$ . As a supplement to this (refined Friedman style) independence result we further show that e.g., primitive recursive arithmetic, PRA, proves that for all K there is an M which bounds the length n of any strictly descending sequence $\langle \alpha_0,..., \alpha_n\rangle$ of ordinals less than ε0 which satisfies the condition that the Norm $N\alpha_i$ of the i-th term αi is bounded by $K + \mid i \mid\cdot 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 $\breve$ ek and Loebl we obtain similar characterizations for finite bad sequences of finite trees in terms of Otter's tree constant 2.9557652856... (shrink)

This paper is intended to give for a general mathematical audience a survey of intriguing connections between analytic combinatorics and logic. We define the ordinals below ε0 in non-logical terms and we survey a selection of recent results about the analytic combinatorics of these ordinals. Using a versatile and flexible compression technique we give applications to phase transitions for independence results, Hilbert’s basis theorem, local number theory, Ramsey theory, Hydra games, and Goodstein sequences. We discuss briefly universality and renormalization issues (...) in this context. Finally, we indicate how regularity properties of ordinal count functions can be used to prove logical limit laws. (shrink)

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 T n 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 T n .) As a corollary of the main theorem of this paper we obtain (reobtain?) optimal bounds for the T n -derivation lengths in terms of ω n+2 -descent recursive functions. The derivation lengths of type one functionals from T n (hence also their computational complexities) are classified optimally in terms of $ -descent recursive functions. In particular we obtain (reobtain?) that the derivation lengths function of a type one functional a ∈ T 0 is primitive recursive, thus any type one functional a in T 0 defines a primitive recursive function. Similarly we also obtain (reobtain?) a full classification of T 1 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 ( $\varepsilon_0) \vdash \Pi^0_2$ - Refl(PA) and PRA + PRWO ( $\omega_{n+2}) \vdash \Pi^0_2$ - Refl(I Σ n+1 ), hence PRA + PRWO( $\epsilon_0) \vdash$ Con(PA) and PRA + PRWO( $\omega_{n+2}) \vdash$ 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. (shrink)

In this article we provide an intrinsic characterization of the famous Howard–Bachmann ordinal in terms of a natural well-partial-ordering by showing that this ordinal can be realized as a maximal order type of a class of generalized trees with respect to a homeomorphic embeddability relation. We use our calculations to draw some conclusions about some corresponding subsystems of second order arithmetic. All these subsystems deal with versions of light-face Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varPi ^1_1$$\end{document}-comprehension.

The termination of rewrite systems for parameter recursion, simple nested recursion and unnested multiple recursion is shown by using monotone interpretations both on the ordinals below the first primitive recursively closed ordinal and on the natural numbers. We show that the resulting derivation lengths are primitive recursive. As a corollary we obtain transparent and illuminating proofs of the facts that the schemata of parameter recursion, simple nested recursion and unnested multiple recursion lead from primitive recursive functions to primitive recursive functions.

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(\prec\lceil)$ (where it is assumed that the well-ordering $\prec$ has some reasonable closure properties) and KPω. Our method relies on a new approach to subrecursion due to Buchholz, Cichon and the author.

We classify the phase transition thresholds from provability to unprovability for certain Friedman-style miniaturizations of Kruskal's Theorem and Higman's Lemma. In addition we prove a new and unexpected phase transition result for ε0. Motivated by renormalization and universality issues from statistical physics we finally state a universality hypothesis.

Gödel’s first incompleteness result from 1931 states that there are true assertions about the natural numbers which do not follow from the Peano axioms. Since 1931 many researchers have been looking for natural examples of such assertions and breakthroughs were obtained in the seventies by Jeff Paris [Some independence results for Peano arithmetic. J. Symbolic Logic 43 725–731] , Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977] and Laurie Kirby [L. Kirby, Jeff Paris, Accessible independence results for Peano Arithmetic, Bull. of (...) the LMS 14 285–293]) and Harvey Friedman [S.G. Simpson, Non-provability of certain combinatorial properties of finite trees, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 87–117; R. Smith, The consistency strength of some finite forms of the Higman and Kruskal theorems, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 119–136] who produced the first mathematically interesting independence results in Ramsey theory and well-order and well-quasi-order theory .In this article we investigate Friedman-style principles of combinatorial well-foundedness for the ordinals below ε0. These principles state that there is a uniform bound on the length of decreasing sequences of ordinals which satisfy an elementary recursive growth rate condition with respect to their Gödel numbers.For these independence principles we classify their phase transitions, i.e. we classify exactly the bounding conditions which lead from provability to unprovability in the induced combinatorial well-foundedness principles.As Gödel numbering for ordinals we choose the one which is induced naturally from Gödel’s coding of finite sequences from his classical 1931 paper on his incompleteness results.This choice makes the investigation highly non-trivial but rewarding and we succeed in our objectives by using an intricate and surprising interplay between analytic combinatorics and the theory of descent recursive functions. For obtaining the required bounds on count functions for ordinals we use a classical 1961 Tauberian theorem of Parameswaran which apparently is far remote from Gödel’s theorem. (shrink)

This article provides a detailed comparison between two systems of collapsing functions. These functions play a crucial role in proof theory, in the analysis of patterns of resemblance, and the analysis of maximal order types of well partial orders. The exact correspondence given here serves as a starting point for far reaching extensions of current results on patterns and well partial orders. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

Let T(Ω) be the ordinal notation system from Buchholz-Schütte (1988). [The order type of the countable segmentT(Ω)0 is — by Rathjen (1988) — the proof-theoretic ordinal the proof-theoretic ordinal ofACA 0 + (Π 1 l −TR).] In particular let ↦Ω a denote the enumeration function of the infinite cardinals and leta ↦ ψ0 a denote the partial collapsing operation on T(Ω) which maps ordinals of T(Ω) into the countable segment TΩ 0 of T(Ω). Assume that the (fast growing) extended Grzegorczyk (...) hierarchy $(F_a )_{a \in T(\Omega )_0 }$ and the slow growing hierarchy $(G_a )_{a \in T(\Omega )_0 }$ are defined with respect to the natural system of distinguished fundamental sequences of Buchholz and Schütte (1988) in the following way: $$\begin{array}{*{20}c} {G_0 (n): = 0,} & {F_0 (n): = (n + 1)^2 ,} \\ {\begin{array}{*{20}c} {G_{a + 1} (n): = G_a (n) + 1,} \\ {G_l (n): = G_{l[n]} (n),} \\ \end{array} } & {\begin{array}{*{20}c} {F_{a + 1} (n): = \underbrace {F_a (...F_a }_{n + 1 - times}(n)...),} \\ {F_l (n): = F_{l[n]} (n),} \\ \end{array} } \\ \end{array}$$ wherel is a countable limit ordinal (term) and (l[n]) n ∈N is the distinguished fundamental sequence assigned tol. For each ordinal (term)a in T(Ω) and each natural numbern letC n (a) be the formal term which results from the ordinal terma by successively replacing every occurence ofψ a by $\psi _{ - 1 + C_n (a)}$ whereψ −1 is considered as a defined function symbol, namely $\psi _{ - 1} b: = F_{\psi _0 b + 1} (n + 1)$ . (Note thatψ a 0=Ω a ) In this article it is shown that for each ordinal termψ 0 a in T(Ω) there exists a natural numbern 0 such thatψ 0 C n (a) ∈ T(Ω) and $G_{\psi _0 a} (n) \leqslant F_{\psi _0 C_n (a) + 1} (n + 1)$ holds for alln≥n 0. This hierarchy comparison theorem yields a plethora of new results on nontrivial lower bounds for the slow growing ordinals — i.e. ordinals for which the slow growing hierarchy yields a classification of the provably total functions of the theory in question — of various theories of iterated inductive definitions (and subsystems ofKPi) and on the number and size of the subrecursively inaccessible ordinals — i.e. ordinals at which the extended Grzegorczyk hierarchy and the slow growing hierarchy catch up — below the proof-theoretic ordinal ofACA 0+(Π 1 l −TR). In particular these subrecursively inaccessibles ordinals are necessarily of the form $\psi _0 \Omega ..._{\Omega _\omega }$. (shrink)

We give a self-contained and streamlined version of the classification of the provably computable functions of PA. The emphasis is put on illuminating as well as seems possible the intrinsic computational character of the standard cut elimination process. The article is intended to be suitable for teaching purposes and just requires basic familiarity with PA and the ordinals below ε0. (Familiarity with a cut elimination theorem for a Gentzen or Tait calculus is helpful but not presupposed).

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 $\Gamma_0$. Let T be the set-theoretic ordinal notation system for $\Gamma_0$ and $T^{tree}$ the tree ordinal representation for $\Gamma$. It is shown in this paper that $_{\alpha \in T}$ matches up with the class of functions which are elementary (...) recursive in the Ackermann function as does $_{\alpha \in T^{tree}}$. By thinning out terms in which the addition function symbol occurs we single out subsystems $T* \subseteq T$ and $T^{tree*} \subseteq T^{tree}$ and prove that $_{\alpha \in T^{tree*}}$ still matches up with $_{\alpha \in T^{tree}}$ but $_{\alpha \in T*}$ now consists of elementary recursive functions only. We discuss the relationship between these results and the $\Gamma_0$-based termination proof for the standard rewrite system for the Ackermann function. (shrink)

We survey a selection of results about majorization hierarchies. The main focus is on classical and recent results about the comparison between the slow and fast growing hierarchies.

. We estimate the derivation lengths of functionals in Gödel's system \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document} of primitive recursive functionals of finite type by a purely recursion-theoretic analysis of Schütte's 1977 exposition of Howard's weak normalization proof for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}. By using collapsing techniques from Pohlers' local predicativity approach to proof theory and based on the Buchholz-Cichon and Weiermann 1994 approach to subrecursive hierarchies we define (...) a collapsing f unction\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} ${\cal D}:T\to \omega$\end{document} so that for terms \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $a,b$\end{document} of Gödel's \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document} we have: If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $a$\end{document} reduces to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $b$\end{document} then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\omega>{\cal D}>{\cal D}.$\end{document} By one uniform proof we obtain as corollaries: A derivation lengths classification for functionals in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}, hence new proof of strongly uniform termination of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}. A new proof of the Kreisel's classific ation of the number-theoretic functions which can be defined in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}, hence a classification of the provably total functions of Peano Arithmetic. A new proof of Tait's results on weak normalization for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}. A new proof of Troelstra's result on strong normalization for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}. Additionally, a slow growing analysis of Gödel's \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document} is obtained via Girard's hierarchy comparison theorem. This analyis yields a contribution to two open pro blems posed by Girard in part two of his book on proof theory. For the sake of completeness we also mention the Howard Schütte bound on derivation lengths for the simple typed \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\lambda$\end{document}-calculus. (shrink)

Inspired from Buchholz' ordinal analysis of ID1 and Beckmann's analysis of the simple typed λ-calculus we classify the derivation lengths for Gödel's system T in the λ-formulation.

The slow growing hierarchy is commonly defined as follows: G0 = 0, Gx−1 := Gx + 1 and Gλ := Gλ[x] where λ<0 is a limit and ·[·]:0∩ Lim × ω → 0 is a given assignment of fundamental sequences for the limits below 0. The first obvious question which is encountered when one looks at this definition is: How does this hierarchy depend on the choice of the underlying system of fundamental sequences? Of course, it is well known and (...) easy to prove that for the standard assignment of fundamental sequence the hierarchy x<0 is slow growing, i.e. each Gx is majorized by a Kalmar elementary recursive function.It is shown in this paper that the slow growing hierarchy x<0 — when it is defined with respect to the norm-based assignment of fundamental sequences which is defined in the article by Cichon — is actually fast growing, i.e. each PA-provably recursive function is eventually dominated by Gx for some α<0. The exact classification of this hierarchy, i.e. the problem whether it is slow or fast growing, has been unsolved since 1992. The somewhat unexpected result of this paper shows that the slow growing hierarchy is extremely sensitive with respect to the choice of the underlying system of fundamental sequences.The paper is essentially self-contained. Only little knowledge about ordinals less than 0 — like the existence of Cantor normal forms, etc. and the beginnings of subrecursive hierarchy theory as presented, for example, in the 1984 textbook of Rose — is assumed. (shrink)

Let T be Gödel's system of primitive recursive functionals of finite type in a combinatory logic formulation. Let $T^{\star}$ be the subsystem of T in which the iterator and recursor constants are permitted only when immediately applied to type 0 arguments. By a Howard-Schütte-style argument the $T^{\star}$ -derivation lengths are classified in terms of an iterated exponential function. As a consequence a constructive strong normalization proof for $T^{\star}$ is obtained. Another consequence is that every $T^{\star}$ -representable number-theoretic function is elementary (...) recursive. Furthermore, it is shown that, conversely, every elementary recursive function is representable in $T^{\star}$ .The expressive weakness of $T^{\star}$ compared to the full system T can be explained as follows: In contrast to $T$ , computation steps in $T^{\star}$ never increase the nesting-depth of ${\mathcal I}_\rho$ and ${\mathcal R}_\rho$ at recursion positions. (shrink)

Continuing the earlier research from [T. Bigorajska, H. Kotlarski, Partitioning α-large sets: some lower bounds, Trans. Amer. Math. Soc. 358 4981–5001] we show that for the price of multiplying the number of parts by 3 we may construct partitions all of whose homogeneous sets are much smaller than in [T. Bigorajska, H. Kotlarski, Partitioning α-large sets: some lower bounds, Trans. Amer. Math. Soc. 358 4981–5001]. We also show that the Paris–Harrington independent statement remains unprovable if the number of colors is (...) restricted to 2, in fact, the statement is unprovable in IΣb. Other results concern some lower bounds for partitions of pairs. (shrink)

In this article we characterize a countable ordinal known as the big Veblen number in terms of natural well-partially ordered tree-like structures. To this end, we consider generalized trees where the immediate subtrees are grouped in pairs with address-like objects. Motivated by natural ordering properties, extracted from the standard notations for the big Veblen number, we investigate different choices for embeddability relations on the generalized trees. We observe that for addresses using one finite sequence only, the embeddability coincides with the (...) classical tree-embeddability, but in this article we are interested in more general situations. We prove that the maximal order type of some of these new embeddability relations hit precisely the big Veblen ordinal ϑΩΩ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\vartheta \Omega^{\Omega}}$$\end{document}. Somewhat surprisingly, changing a little bit the well-partially ordered addresses, the maximal order type hits an ordinal which exceeds the big Veblen number by far, namely ϑΩΩΩ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\vartheta \Omega^{\Omega^\Omega}}$$\end{document}. Our results contribute to the research program on classifying properties of natural well-orderings in terms of order-theoretic properties of the functions generating the orderings. (shrink)

We introduce strong Goodstein principles which are true but unprovable in strong impredicative theories like IDn.

We elaborate Weiermann-style phase transitions for well-partial-orderings (wpo) determined by iterated finite sequences under Higman-Friedman style embedding with Gordeev’s symmetric gap condition. For every d-times iterated wpo ${\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d}\right)}$ in question, d > 1, we fix a natural extension of Peano Arithmetic, ${T \supseteq \sf{PA}}$ , that proves the corresponding second-order sentence ${\sf{WPO}\left({\rm S}{\textsc{eq}}^{d}, \trianglelefteq _{d}\right) }$ . Having this we consider the following parametrized first-order slow well-partial-ordering sentence ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d}, r\right):}$ $$\left( \forall K > 0 (...) \right) \left( \exists M > 0\right) \left( \forall x_{0},\ldots ,x_{M}\in {\rm S}\text{\textsc{eq}}^{d}\right)$$ $$\left( \left( \forall i\leq M\right) \left( \left| x_{i}\right| < K + r \left\lceil \log _{d} \left( i+1\right) \right\rceil \right)\rightarrow \left( \exists i < j \leq M \right) \left(x_{i} \trianglelefteq _{d} x_{j}\right) \right)$$ for a natural additive Seq d -norm |·| and r ranging over EFA-provably computable positive reals, where EFA is an abbreviation for IΔ 0 + exp. We show that the following basic phase transition clauses hold with respect to ${T = \Pi_{1}^{0}\sf{CA}_{ < \varphi ^{_{\left( d-1\right) }} \left(0\right) }}$ and the threshold point1. If r < 1 then ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d},r \right) }$ is provable in T. If ${r > 1}$ then ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d},r \right) }$ is not provable in T.Moreover, by the well-known proof theoretic equivalences we can just as well replace T by PA or ACA 0 and ${\Delta _{1}^{1}\sf{CA}}$ , if d = 2 and d = 3, respectively.In the limit case d → ∞ we replaceEFA-provably computable reals r by EFA-provably computable functions ${f: \mathbb{N} \rightarrow \mathbb{R}_{+}}$ and prove analogous theorems. (In the sequel we denote by ${\mathbb{R}_{+}}$ the set of EFA-provably computable positive reals). In the basic case T = PA we strengthen the basic phase transition result by adding the following static threshold clause ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2}, 1\right)}$ is still provable in T = PA (actually in EFA). Furthermore we prove the following dynamic threshold clauses which, loosely speaking are obtained by replacing the static threshold t by slowly growing functions 1 α given by ${1_{\alpha }\left( i\right)\,{:=}\,1+\frac{1}{H_{\alpha }^{-1}\left(i\right) }, H_{\alpha}}$ being the familiar fast growing Hardy function and ${H_{\alpha }^{-1}\left( i\right)\,{:=}\,\rm min \left\{ j \mid H_{\alpha } \left ( j\right) \geq i \right\}}$ the corresponding slowly growing inversion. If ${\alpha < \varepsilon _{0}}$ , then ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2}, 1_{\alpha}\right)}$ is provable in T = PA. ${\sf{SWP}\left( {\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2},1_{\varepsilon _{0}}\right)}$ is not provable in T = PA. We conjecture that this pattern is characteristic for all ${T\supseteq \sf{PA}}$ under consideration and their proof-theoretical ordinals o (T ), instead of ${\varepsilon _{0}}$. (shrink)

Let $R$ be a (finite) rewrite system over a (finite) signature. Let $\succ$ be a strict well-founded termination ordering on the set of terms in question so that the rules of $R$ are reducing under $\succ$ . Then $R$ is terminating. In this article it is proved for a certain class of far reaching termination orderings (of order type reaching up to the first subrecursively inaccessible ordinal, i.e. the proof-theoretic ordinal of $ID_{<\omega}$ ) that – under some reasonable assumptions which (...) are met in current applications – the derivation lengths function for $R$ is bounded by a function from the slow growing hierarchy of level determined by the order type of the underlying termination ordering. This result is a (correction of the proof of and a) strong generalization of theorem 8.1 in Cichon's article Termination orderings and complexity characterisations. Leeds, Proof Theory 1990, (Aczel, Simmons, and Wainer, editors), Cambridge University Press 1992, 171-193. (shrink)

In this article we define a new and transparent concept of total collapsing functions for an ordinal notation system which is characteristic for the theory (Δ 2 1 -CA)+(BI). We show that our construction allows the application of Pohler's method of local predicativity as presented in [2] which yields a perspicious proof-theoretic analysis of (Δ 2 1 -CA)+(BI) being not much more complicated than for ID1.

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 Godel's system T of primitive recursive functionals of finite types by constructing an $\varepsilon_0$-recursive function [ ]$_0$: T $\rightarrow \omega$ so that a reduces to b implies [a]$_0 > [b]_0$. The construction of [ ]$_0$ is based on a careful analysis of the Howard-Schutte treatment of Godel's T and (...) utilizes the collapsing function $\psi: \varepsilon_0 \rightarrow \omega$ 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 Godel'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 T$_n$ be the subsystem of T in which the recursors have type level less than or equal to n+2. As a corollary of the main theorem of this paper we obtain optimal bounds for the T$_n$-derivation lengths in terms of $\omega_{n+2}$-descent recursive functions. The derivation lengths of type one functionals from T$_n$ are classified optimally in terms of $< \omega_{n+2}$-descent recursive functions. In particular we obtain that the derivation lengths function of a type one functional a $\in T_0$ is primitive recursive, thus any type one functional a in T$_0$ defines a primitive recursive function. Similarly we also obtain a full classification of T$_1$ in terms of multiple recursion. As proof-theoretic corollaries we reobtain the classification of the I$\Sigma_{n+1}$-provably recursive functions. Taking advantage from our finitistic and constructive treatment of the terms of Godel's T we reobtain additionally that PRA + PRWO \vdash \Pi^0_2$ - Refl and PRA + PRWO \vdash \Pi^0_2$ - Refl, hence PRA + PRWO \vdash$ Con and PRA + PRWO \vdash$ Con$. 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. (shrink)

Let T be the standard Veblen 1908 ordinal notation system for Γ0 as defined, for example, in Schütte's 1977 textbook [13] on Proof Theory. We define a slight modification of the standard assignment of fundamental sequences for the limit ordinals in T and prove that Γ0 is subrecursively inaccessible for this assignment, i.e. the induced slow and fast growing hierarchy match up at Γ0 for the first time.The results of this paper also indicate that φε00 may be considered as a (...) new slow growing ordinal of PA in the sense that the induced slow growing hierarchy up to φε00 classifies the PA-provablyrecursive functions.We show how the results of this paper can be used to bui d a subrecursive hierarchyover the predicative ordinals in the spirit of Wainer's 1970 abstract [16 ]. (shrink)

This book bridges the gaps between logic, mathematics and computer science by delving into the theory of well-quasi orders, also known as wqos. This highly active branch of combinatorics is deeply rooted in and between many fields of mathematics and logic, including proof theory, commutative algebra, braid groups, graph theory, analytic combinatorics, theory of relations, reverse mathematics and subrecursive hierarchies. As a unifying concept for slick finiteness or termination proofs, wqos have been rediscovered in diverse contexts, and proven to be (...) extremely useful in computer science. The book introduces readers to the many facets of, and recent developments in, wqos through chapters contributed by scholars from various fields. As such, it offers a valuable asset for logicians, mathematicians and computer scientists, as well as scholars and students. (shrink)

In this article we investigate whether the following conjecture is true or not: does the addition-free theta functions form a canonical notation system for the linear versions of Friedman’s well-partial-orders with the so-called gap-condition over a finite set of n labels. Rather surprisingly, we can show this is the case for two labels, but not for more than two labels. To this end, we determine the order type of the notation systems for addition-free theta functions in terms of ordinals less (...) than ε0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon _0$$\end{document}. We further show that the maximal order type of the Friedman ordering can be obtained by a certain ordinal notation system which is based on specific binary theta functions. (shrink)

Let Ω be the least uncountable ordinal. Let K(Ω) 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 K(Ω) which preserves direct limits and pullbacks. Let $\tau \Omega: \xi = \omega^\xi\}$ . Then τ has a unique "term"-representation in Ω. λξη.ω ξ + η and countable ordinals called the constituents of τ. Let $\delta and K(τ) be the set of the constituents of τ. (...) Let β = max K(τ). Let [ β ] be an occurrence of β in τ such that τ [ β] = τ. Let $\bar \theta$ 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 $\xi \mapsto \bar \theta(\tau \lbrack \gamma + \xi \rbrack)\delta$ is a dilator for every $\gamma > \max\{\beta. \delta.\omega\}$. (shrink)

It is well known that the Ackermann function can be defined via diagonalization from an iteration hierarchy which is built on a start function like the successor function. In this paper we study for a given start function g iteration hierarchies with a sub-linear modulus h of iteration. In terms of g and h we classify the phase transition for the resulting diagonal function from being primitive recursive to being Ackermannian.

We survey a selection of results about majorization hierarchies. The main focus is on classical and recent results about the comparison between the slow and fast growing hierarchies.

Let $\Omega:= \aleph_1$ . For any $\alpha \Omega:\xi = \omega^\xi\}$ 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 $\alpha^\ast:= \max (E_\Omega(\alpha) \cup \{0\})$ . A function f: εΩ + 1 → Ω is called essentially increasing, if for any $\alpha < \varepsilon_{\Omega + 1}; f(\alpha) \geq \alpha^\ast: f$ is called essentially monotonic, if for any $\alpha,\beta < \varepsilon_{\Omega + (...) 1}$; $\alpha \leq \beta \wedge \alpha^\ast \leq \beta^\ast \Rightarrow f(\alpha) \leq f(\beta).$ Let Clf(0) be the least set of ordinals which contains 0 as an element and which satisfies the following two conditions: (a) $\alpha,\beta \epsilon \mathrm{Cl}_f(0) \Rightarrow \omega^\alpha + \beta \epsilon \mathrm{Cl}_f(0)$ , (b) $E_\Omega\alpha \subseteq \mathrm{Cl}_f(0) \Rightarrow f(\alpha) \epsilon \mathrm{Cl}_f(0)$ . Let ϑεΩ + 1 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 Clf(0) is less than or equal to ϑεΩ + 1. (shrink)

In this article we show how to extract with the use of the Buchholz -Cichon-Weiermann approach to subrecursive hierarchies from Rathjen's 1991 ordinal analysis of KPM a characterization of the provably total number-theoretic functions of KPM and some of its subsystems in a uniform and direct way.

We give a simple and elementary proof of the following result of Girard and Vauzeilles which is proved in [5]: “The binary Veblen function ψ: On × On — On is a dilator.” Our proof indicates the intimate connection between the traditional theory of ordinal notation systems and Girard's theory of denotation systems. MSC: 03F15.