Archive for Mathematical Logic 43 (4):505-541 (2004)

Felicity Martin
University of Sydney
Alexis Fernandez
Florida International University
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
Keywords Induction  Collection  formulas
Categories (categorize this paper)
Reprint years 2004
DOI 10.1007/s00153-003-0197-8
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 65,714
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On the Induction Schema for Decidable Predicates.Lev D. Beklemishev - 2003 - Journal of Symbolic Logic 68 (1):17-34.
On Σ1‐Definable Functions Provably Total in I ∏ 1−.Teresa Bigorajska - 1995 - Mathematical Logic Quarterly 41 (1):135-137.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Preservation Theorems for Bounded Formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
On Parameter Free Induction Schemas.R. Kaye, J. Paris & C. Dimitracopoulos - 1988 - Journal of Symbolic Logic 53 (4):1082-1097.
A New "Feasible" Arithmetic.Stephen Bellantoni & Martin Hofmann - 2002 - Journal of Symbolic Logic 67 (1):104-116.
A Note on a Theorem of Kanovei.Roman Kossak - 2004 - Archive for Mathematical Logic 43 (4):565-569.
Examining Fragments of the Quantified Propositional Calculus.Steven Perron - 2008 - Journal of Symbolic Logic 73 (3):1051-1080.
Remarks on Herbrand Normal Forms and Herbrand Realizations.Ulrich Kohlenbach - 1992 - Archive for Mathematical Logic 31 (5):305-317.
Finite Injury and Σ1-Induction.Michael Mytilinaios - 1989 - Journal of Symbolic Logic 54 (1):38 - 49.
On Normal Forms in Łukasiewicz Logic.A. Di Nola & A. Lettieri - 2004 - Archive for Mathematical Logic 43 (6):795-823.


Added to PP index

Total views
10 ( #882,927 of 2,462,601 )

Recent downloads (6 months)
1 ( #449,387 of 2,462,601 )

How can I increase my downloads?


My notes