Girard’s maxim, that Peano Arithmetic is a theory of one inductive definition, is re-examined in the light of a weak theory EA formalising basic principles of Nelson’s predicative Arithmetic.

The class of all recursive functions fails to possess a natural hierarchical structure, generated predicatively from "within". On the other hand, many (proof-theoretically significant) sub-recursive classes do. This paper attempts to measure the limit of predicative generation in this context, by classifying and characterizing those (predictably terminating) recursive functions which can be successively defined according to an autonomy condition of the form: allow recursions only over well-orderings which have already been "coded" at previous levels. The question is: how can a (...) recursion code a well-ordering? The answer lies in Girard's theory of dilators, but is reworked here in a quite different and simplified framework specific to our purpose. The "accessible" recursive functions thus generated turn out to be those provably recursive in $(\prod_{1}^{1}-CA)_{0}$. (shrink)

We introduce the appropriate iterated version of the system of ordinal notations from [G1] whose order type is the familiar Howard ordinal. As in [G1], our ordinal notations are partly inspired by the ideas from [P] where certain crucial properties of the traditional Munich' ordinal notations are isolated and used in the cut-elimination proofs. As compared to the corresponding “impredicative” Munich' ordinal notations (see e.g. [B1, B2, J, Sch1, Sch2, BSch]), our ordinal notations arearbitrary terms in the appropriate simple term (...) algebra based on the notion of collapsing functions (which we would rather identify as projective functions). In Sect. 1 below we define the systems of ordinal notationsPRJ( ), for any primitive recursive limit wellordering . In Sect. 2 we prove the crucial well-foundness property by using the appropriate well-quasi-ordering property of the corresponding binary labeled trees [G3]. In Sect. 3 we interprete inPRJ( ) the familiar Veblen-Bachmann hierarchy of ordinal functions, and in Sect. 4 we show that the corresponding Buchholz's system of ordinal notationsOT( ) is a proper subsystem ofPRJ( ), although it has the same order type according to [G3] together with the interpretation from Sect. 2 in the terms of labeled trees. In Sect. 5 we use Friedman's approach in order to obtain an appropriate purely combinatorial statement which is not provable in the theory of iterated inductive definitions ID< λ, for arbitrarily large limit ordinalλ. Formal theories, axioms, etc. used below are familiar in the proof theory of subsystems of analysis (see [BFPS, T, BSch]). (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)

Subrecursive hierarchy classifications are used to compare the complexities of recursive functions according to their derivations in a version of Kleene's equation calculus, and their computations by term-rewriting. In each case ordinal bounds are assigned, and it turns out that the respective complexity measures are given by a version of the Fast Growing Hierarchy, and the Slow Growing Hierarchy. Known comparisons between the two hierarchies then provide ordinal trade-offs between derivation and computation. Characteristics of some well-known subrecursive classes are also (...) read off. (shrink)

Kruskal proved that finite trees are well-quasi-ordered by hom(e)omorphic embeddability. Friedman observed that this statement is not provable in predicative analysis. Friedman also proposed (see in [Simpson]) some stronger variants of the Kruskal theorem dealing with finite labeled trees under home(e)omorphic embeddability with a certain gap-condition, where labels are arbitrary finite ordinals from a fixed initial segment of ω. The corresponding limit statement, expressing that for all initial segments of ω these labeled trees are well-quasi-ordered, is provable in Π 1 (...) 1 -CA, but not in the analogous theory Π 1 1 -CA 0 with induction restricted to sets. Schutte and Simpson proved that the one-dimensional case of Friedman's limit statement dealing with finite labeled intervals is not provable in Peano arithmetic. However, Friedman's gap-condition fails for finite trees labeled with transfinite ordinals. In [Gordeev 1] I proposed another gap-condition and proved the resulting one-dimensional modified statements for all (countable) transfinite ordinal-labels. The corresponding universal modified one-dimensional statement UM 1 is provable in (in fact, is equivalent to) the familiar theory ATR 0 whose proof-theoretic ordinal is Γ 0 . In [Gordeev 1] I also announced that, in the general case of arbitrarily-branching finite trees labeled with transfinite ordinals, in the proof-theoretic sense the hierarchy of the limit modified statements $\mathbf{M}_{ (which are denoted by LM λ in the present note) is as strong as the hierarchy of the familiar theories of iterated inductive definitions (more precisely, see [Gordeev 1, Concluding Remark 3]). In this note I present a "positive" proof of the full universal modified statement UM, together with a short proof of the crucial "reverse" results which is based on Okada's interpretation of the well-established ordinal notations of Buchholz corresponding to the theories of iterated inductive definitions. Formally the results are summarized in $\S5$ below. (shrink)

Weiermann [18] introduces a new method to generate fast growing functions in order to get an elegant and perspicuous proof of a bounding theorem for provably total recursive functions in a formal theory, e.g., in PA. His fast growing function θαn is described as follows. For each ordinal α and natural number n let T α n denote a finitely branching, primitive recursive tree of ordinals, i.e., an ordinal as a label is attached to each node in the tree so (...) that the labelling is compatible with the tree ordering. Then the tree T α n is well founded and hence finite by Konig's lemma. Define θαn=the depth of the tree T α n =the length of the longest branch in T α n . We introduce new fast and slow growing functions in this mode of definitions and show that each of these majorizes provably total recursive functions in PA. (shrink)

In this, journal, W. Buchholz gave an elegant proof of a characterization theorem for provably total recursive functions in the theory IDv for the v-times iterated inductive definitions . He characterizes the classes of functions by Hardy functions. In this note we will show that a slow growing analogue to the theorem can be obtained by a slight modification of Buchholz' proof.