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)

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)

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 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.

We prove the following theorem: Let φ be a formula in the language of the theory PA− of discretely ordered commutative rings with unit of the form ∃yφ′ with φ′ and let ∈ Δ0 and let fφ: ℕ → ℕ such that fφ = y iff φ′ & < xK). Here I ∏math image1− denotes the theory PA− plus the scheme of induction for formulas φ of the form ∀yφ′ with φ′ ∈ Δ0.