By a theorem of R. Kaye, J. Paris and C. Dimitracopoulos, the class of the Πn+1-sentences true in the standard model is the only consistent Πn+1-theory which extends the scheme of induction for parameter free Πn+1-formulas. Motivated by this result, we present a systematic study of extensions of bounded quantifier complexity of fragments of first-order Peano Arithmetic. Here, we improve that result and show that this property describes a general phenomenon valid for parameter free schemes. As a consequence, we obtain (...) results on the quantifier complexity, finite axiomatizability and relative strength of schemes for Δn+1-formulas. (shrink)

We study the fragment of Peano arithmetic formalizing the induction principle for the class of decidable predicates, $I\Delta_1$ . We show that $I\Delta_1$ is independent from the set of all true arithmetical $\Pi_2-sentences$ . Moreover, we establish the connections between this theory and some classes of oracle computable functions with restrictions on the allowed number of queries. We also obtain some conservation and independence results for parameter free and inference rule forms of $\Delta_1-induction$ . An open problem formulated by J. (...) Paris is whether $I\Delta_1$ proves the corresponding least element principle for decidable predicates, $L\Delta_1$ (or, equivalently. the $\Sigma_1-collection$ principle $B\Sigma_1$ ). We reduce this question to a purely computation-theoretic one. (shrink)

For a theory T, we study relationships among IΔ n +1 (T), LΔ n+1 (T) and B * Δ n+1 (T). These theories are obtained restricting the schemes of induction, minimization and (a version of) collection to Δ n+1 (T) formulas. We obtain conditions on T (T is an extension of B * Δ n+1 (T) or Δ n+1 (T) is closed (in T) under bounded quantification) under which IΔ n+1 (T) and LΔ n+1 (T) are equivalent. These conditions depend (...) on Th Πn +2 (T), the Π n+2 –consequences of T. The first condition is connected with descriptions of Th Πn +2 (T) as IΣ n plus a class of nondecreasing total Π n –functions, and the second one is related with the equivalence between Δ n+1 (T)–formulas and bounded formulas (of a language extending the language of Arithmetic). This last property is closely tied to a general version of a well known theorem of R. Parikh. Using what we call Π n –envelopes we give uniform descriptions of the previous classes of nondecreasing total Π n –functions. Π n –envelopes are a generalization of envelopes (see [10]) and are closely related to indicators (see [12]). Finally, we study the hierarchy of theories IΔ n+1 (IΣ m ), m≥n, and prove a hierarchy theorem. (shrink)

We prove that: • if there is a model of I∆₀ + ¬ exp with cofinal Σ₁-definable elements and a Σ₁ truth definition for Σ₁ sentences, then I∆₀ + ¬ exp +¬BΣ₁ is consistent, • there is a model of I∆₀ Ω₁ + ¬ exp with cofinal Σ₁-definable elements, both a Σ₂ and a ∏₂ truth definition for Σ₁ sentences, and for each n > 2, a Σ n truth definition for Σ n sentences. The latter result is obtained by (...) constructing a model with a recursive truth-preserving translation of Σ₁ sentences into boolean combinations of $\exists \sum {\begin{array}{*{20}{c}} h \\ 0 \\ \end{array} } $ sentences. We also present an old but previously unpublished proof of the consistency of I∆₀ + ¬ exp + ¬BΣ₁ under the assumption that the size parameter in Lessan's ∆₀ universal formula is optimal. We then discuss a possible reason why proving the consistency of I∆₀ + ¬ exp + ¬BΣ₁ unconditionally has turned out to be so difficult. (shrink)

We present a comprehensive study of the axiom schemas IΣ - n , BΣ - n (induction and collection schemas for parameter free Σ n formulas) and some closely related schemas.

In this paper we continue the study of the theories IΔ n+1 (T), initiated in [7]. We focus on the quantifier complexity of these fragments and theirs (non)finite axiomatization. A characterization is obtained for the class of theories such that IΔ n+1 (T) is Π n+2 –axiomatizable. In particular, IΔ n+1 (IΔ n+1 ) gives an axiomatization of Th Π n+2 (IΔ n+1 ) and is not finitely axiomatizable. This fact relates the fragment IΔ n+1 (IΔ n+1 ) to induction (...) rule for Δ n+1 –formulas. Our arguments, involving a construction due to R. Kaye (see [9]), provide proofs of Parsons’ conservativeness theorem (see [16]) and (a weak version) of a result of L.D. Beklemishev on unnested applications of induction rules for Π n+2 and Δ n+1 formulas (see [2]). (shrink)

A well-known result states that, over basic Kalmar elementary arithmetic EA, the induction schema for ∑n formulas is equivalent to the uniform reflection principle for ∑n + 1 formulas . We show that fragments of arithmetic axiomatized by various forms of induction rules admit a precise axiomatization in terms of reflection principles as well. Thus, the closure of EA under the induction rule for ∑n formulas is equivalent to ω times iterated ∑n reflection principle. Moreover, for k < ω, k (...) times iterated ∑n reflection principle over EA precisely corresponds to the extension of EA by k nested applications of ∑n induction rule.The above relationship holds in greater generality than just stated. In fact, we give general formulas characterizing in terms of iterated reflection principles the extension of any given theory by k nested applications of ∑n or Πn induction rules. In particular, the closure of a theory T under just one application of ∑1 induction rule is equivalent to T together with ∑1 reflection principle for each finite Π2 axiomatized subtheory of T.These results have closely parallel ones in the theory of subrecursive function classes. The rules under study correspond, in a canonical way, to natural closure operators on the classes of provably recursive functions. Thus, ∑1 induction rule precisely corresponds to the primitive recursive closure operator, and ∑1 collection rule, introduced below, corresponds to the elementary closure operator. (shrink)

People have always been interested in numbers, in particular the natural numbers. Of course, we all have an intuitive notion of what these numbers are. In the late 19th century mathematicians, such as Grassmann, Frege and Dedekind, gave definitions for these familiar objects. Since then the development of axiomatic schemes for arithmetic have played a fundamental role in a logical understanding of mathematics. There has been a need for some time for a monograph on the metamathematics of first-order arithmetic. The (...) aim of the book by Hajek and Pudlak is to cover some of the most important results in the study of a first order theory of the natural numbers, called Peano arithmetic and its fragments (subtheories). The field is quite active, but only a small part of the results has been covered in monographs. This book is divided into three parts. In Part A, the authors develop parts of mathematics and logic in various fragments. Part B is devoted to incompleteness. Part C studies systems that have the induction schema restricted to bounded formulas (Bounded Arithmetic). One highlight of this section is the relation of provability to computational complexity. The study of formal systems for arithmetic is a prerequisite for understanding results such as Gödel's theorems. This book is intended for those who want to learn more about such systems and who want to follow current research in the field. The book contains a bibliography of approximately 1000 items. (shrink)

A notion called Herbrand saturation is shown to provide the model-theoretic analogue of a proof-theoretic method, Herbrand analysis, yielding uniform model-theoretic proofs of a number of important conservation theorems. A constructive, algebraic variation of the method is described, providing yet a third approach, which is finitary but retains the semantic flavor of the model-theoretic version.

By a result of Paris and Friedman, the collection axiom schema for $\Sigma_{n+1}$ formulas, $B\Sigma_{n+1}$ , is $\Pi_{n+2}$ conservative over $I\Sigma_n$ . We give a new proof-theoretic proof of this theorem, which is based on a reduction of $B\Sigma_n$ to a version of collection rule and a subsequent analysis of this rule via Herbrand's theorem. A generalization of this method allows us to improve known results on reflection principles for $B\Sigma_n$ and to answer some technical questions left open by Sieg (...) [23] and Hájek [9]. We also give a new proof of independence of $B\Sigma_{n+1}$ over $I\Sigma_n$ by a direct recursion-theoretic argument and answer an open problem formulated by Gaifman and Dimitracopoulos [8]. (shrink)