The unfolding of schematic formal systems is a novel concept which was initiated in Feferman , Gödel ’96, Lecture Notes in Logic, Springer, Berlin, 1996, pp. 3–22). This paper is mainly concerned with the proof-theoretic analysis of various unfolding systems for non-finitist arithmetic . In particular, we examine two restricted unfoldings and , as well as a full unfolding, . The principal results then state: is equivalent to ; is equivalent to ; is equivalent to . Thus is proof-theoretically equivalent (...) to predicative analysis. (shrink)

This article provides the proof-theoretic analysis of the transfinitely iterated fixed point theories $\widehat{ID}_\alpha and \widehat{ID}_{ the exact proof-theoretic ordinals of these systems are presented.

In this article we introduce systems for metapredicative Mahlo in explicit mathematics and admissible set theory. The exact upper proof-theoretic bounds of these systems are established.

In this paper we study applicative theories of operations and numbers with the non-constructive minimum operator in the context of a total application operation. We determine the proof-theoretic strength of such theories by relating them to well-known systems like Peano Arithmetic PA and the system <0 of second order arithmetic. Essential use will be made of so-called fixed-point theories with ordinals, certain infinitary term models and Church-Rosser properties.

This article provides the proof-theoretic analysis of the transfinitely iterated fixed point theories $\widehat{ID}_\alpha and \widehat{ID}_{<\alpha};$ the exact proof-theoretic ordinals of these systems are presented.

The aim of this article is to give the proof-theoretic analysis of various subsystems of Feferman's theory T1 for explicit mathematics which contain the non-constructive μ-operator and join. We make use of standard proof-theoretic techniques such as cut-elimination of appropriate semiformal systems and asymmetrical interpretations in standard structures for explicit mathematics.

In this paper we establish the proof-theoretic equivalence of (i) $\hbox {\sf ATR}$ and $\widehat{\hbox{\sf ID}}_{\omega}$ , (ii) $\hbox{\sf ATR}_0+ (\Sigma^1_1-\hbox{\sf DC})$ and $\widehat{\hbox {\sf ID}}_{<\omega^\omega} , and (iii) $\hbox {\sf ATR}+(\Sigma^1_1-\hbox{\sf DC})$ and $\widehat{\hbox {\sf ID}}_{<\varepsilon_0} $.

We study elementary second order extensions of the theoryID 1 of non-iterated inductive definitions and the theoryPA Ω of Peano arithmetic with ordinals. We determine the exact proof-theoretic strength of those extensions and their natural subsystems, and we relate them to subsystems of analysis with arithmetic comprehension plusΠ 1 1 comprehension and bar induction without set parameters.

This paper deals with: (i) the theory ID # 1 which results from $\widehat{\mathrm{ID}}_1$ by restricting induction on the natural numbers to formulas which are positive in the fixed point constants, (ii) the theory BON(μ) plus various forms of positive induction, and (iii) a subtheory of Peano arithmetic with ordinals in which induction on the natural numbers is restricted to formulas which are Σ in the ordinals. We show that these systems have proof-theoretic strength φω 0.

The concept of the (full) unfolding of a schematic system is used to answer the following question: Which operations and predicates, and which principles concerning them, ought to be accepted if one has accepted ? The program to determine for various systems of foundational significance was previously carried out for a system of nonfinitist arithmetic, ; it was shown that is proof-theoretically equivalent to predicative analysis. In the present paper we work out the unfolding notions for a basic schematic system (...) of finitist arithmetic, , and for an extension of that by a form of the so-called Bar Rule. It is shown that and are proof-theoretically equivalent, respectively, to Primitive Recursive Arithmetic, , and to Peano Arithmetic,. (shrink)

We show that the principle of ω model reflection for Π1n − 1 formulas is equivalent over ACA0 to the scheme of Π1n bar induction. This extends and refines previous results of Friedman and Simpson.

In this article we provide wellordering proofs for metapredicative systems of explicit mathematics and admissible set theory featuring suitable axioms about the Mahloness of the underlying universe of discourse. In particular, it is shown that in the corresponding theories EMA of explicit mathematics and KPm 0 of admissible set theory, transfinite induction along initial segments of the ordinal φω00, for φ being a ternary Veblen function, is derivable. This reveals that the upper bounds given for these two systems in the (...) paper Jager and Strahm [11] are indeed sharp. (shrink)

This paper studies systems of explicit mathematics as introduced by Feferman [9, 11]. In particular, we propose weak explicit type systems with a restricted form of elementary comprehension whose provably terminating operations coincide with the functions on binary words that are computable in polynomial time. The systems considered are natural extensions of the first-order applicative theories introduced in Strahm [19, 20].

We give a broad discussion of reflection principles in explicit mathematics, thereby addressing various kinds of universe existence principles. The proof-theoretic strength of the relevant systems of explicit mathematics is couched in terms of suitable extensions of Kripke–Platek set theory.

This paper is a direct successor to 12. Its aim is to introduce a new realisability interpretation for weak systems of explicit mathematics and use it in order to analyze extensions of the theory PET in 12 by the so-called join axiom of explicit mathematics.

In this paper we study (self)-applicative theories of operations and binary words in the context of polynomial time computability. We propose a first order theory PTO which allows full self-application and whose provably total functions on W = {0, 1} * are exactly the polynomial time computable functions. Our treatment of PTO is proof-theoretic and very much in the spirit of reductive proof theory.

This paper is about two topics: 1. systems of explicit mathematics with universes and a non-constructive quantification operator $\mu$; 2. iterated fixed point theories with ordinals. We give a proof-theoretic treatment of both families of theories; in particular, ordinal theories are used to get upper bounds for explicit theories with finitely many universes.

In this paper it is shown that the intuitionistic .xed point theory equation image for α times iterated fixed points of strictly positive operator forms is conservative for negative arithmetic and equation image sentences over the theory equation image for α times iterated arithmetic comprehension without set parameters.This generalizes results previously due to Buchholz [5] and Arai [2].

In this article we introduce systems for metapredicative Mahlo in explicit mathematics and admissible set theory. The exact upper proof-theoretic bounds of these systems are established.

This paper deals with the proof theory of first-order applicative theories with non-constructive μ operator and a form of the bar rule, yielding systems of ordinal strength Γ0 and 20, respectively. Relevant use is made of fixed-point theories with ordinals plus bar rule.

This paper deals with: (i) the theory $\mathrm{ID}^{\tt\#}_1$ which results from $\widehat{\mathrm{ID}}_1$ by restricting induction on the natural numbers to formulas which are positive in the fixed point constants, (ii) the theory $\mathrm{BON}(\mu)$ plus various forms of positive induction, and (iii) a subtheory of Peano arithmetic with ordinals in which induction on the natural numbers is restricted to formulas which are $\Sigma$ in the ordinals. We show that these systems have proof-theoretic strength $\varphi\omega 0$.

We propose two admissible closures $${\mathbb{A}({\sf PTCA})}$$ and $${\mathbb{A}({\sf PHCA})}$$ of Ferreira’s system PTCA of polynomial time computable arithmetic and of full bounded arithmetic (or polynomial hierarchy computable arithmetic) PHCA. The main results obtained are: (i) $${\mathbb{A}({\sf PTCA})}$$ is conservative over PTCA with respect to $${\forall\exists\Sigma^b_1}$$ sentences, and (ii) $${\mathbb{A}({\sf PHCA})}$$ is conservative over full bounded arithmetic PHCA for $${\forall\exists\Sigma^b_{\infty}}$$ sentences. This yields that (i) the $${\Sigma^b_1}$$ definable functions of $${\mathbb{A}({\sf PTCA})}$$ are the polytime functions, and (ii) the $${\Sigma^b_{\infty}}$$ definable (...) functions of $${\mathbb{A}({\sf PHCA})}$$ are the functions in the polynomial time hierarchy. (shrink)

We introduce and analyze two theories for typed inductive definitions and establish their proof-theoretic ordinal to be the small Veblen ordinal \. We investigate on the one hand the applicative theory \ of functions, inductive definitions, and types. It includes a simple type structure and is a natural generalization of S. Feferman’s system \\). On the other hand, we investigate the arithmetical theory \ of typed inductive definitions, a natural subsystem of \, and carry out a wellordering proof within \ (...) that makes use of fundamental sequences for ordinal notations in an ordinal notation system based on the finitary Veblen functions. The essential properties for describing the ordinal notation system are worked out. (shrink)

This paper is a companion to work of Feferman, Jäger, Glaß, and Strahm on the proof theory of the type two functionals μ and E1 in the context of Feferman-style applicative theories. In contrast to the previous work, we analyze these two functionals in the context of Schlüter's weakened applicative basis PRON which allows for an interpretation in the primitive recursive indices. The proof-theoretic strength of PRON augmented by μ and E1 is measured in terms of the two subsystems of (...) second order arithmetic, Π10-CA and Π11-CA, respectively. (shrink)

In this paper we study -applicative theories of operations and binary words in the context of polynomial time computability. We propose a first order theory PTO which allows full self-application and whose provably total functions on $\mathbb{W} = \{0, 1\}^\ast$ are exactly the polynomial time computable functions. Our treatment of PTO is proof-theoretic and very much in the spirit of reductive proof theory.

This paper is about two topics: 1. systems of explicit mathematics with universes and a non-constructive quantification operator $\mu$; 2. iterated fixed point theories with ordinals. We give a proof-theoretic treatment of both families of theories; in particular, ordinal theories are used to get upper bounds for explicit theories with finitely many universes.