Archive for Mathematical Logic 59 (3):461-501 (2020)

We study variants of Buss’s theories of bounded arithmetic axiomatized by induction schemes disallowing the use of parameters, and closely related induction inference rules. We put particular emphasis on \ induction schemes, which were so far neglected in the literature. We present inclusions and conservation results between the systems and \ of a new form), results on numbers of instances of the axioms or rules, connections to reflection principles for quantified propositional calculi, and separations between the systems.
Keywords No keywords specified (fix it)
Categories No categories specified
(categorize this paper)
DOI 10.1007/s00153-019-00702-w
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Translate to english
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 54,385
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

Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Bounded Arithmetic and the Polynomial Hierarchy.Jan Krajíček, Pavel Pudlák & Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52 (1-2):143-153.
Relating the Bounded Arithmetic and Polynomial Time Hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
Quantified Propositional Calculi and Fragments of Bounded Arithmetic.Jan Krajíček & Pavel Pudlák - 1990 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 36 (1):29-46.

View all 14 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

The Strength of Sharply Bounded Induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
Dynamic Ordinal Analysis.Arnold Beckmann - 2003 - Archive for Mathematical Logic 42 (4):303-334.
Preservation Theorems for Bounded Formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Some Results on LΔ — N+1.Alejandro Fernández Margarit & F. Félix Lara Martin - 2001 - Mathematical Logic Quarterly 47 (4):503-512.
Open Induction in a Bounded Arithmetic for TC0.Emil Jeřábek - 2015 - Archive for Mathematical Logic 54 (3-4):359-394.
Sequence Encoding Without Induction.Emil Jeřábek - 2012 - Mathematical Logic Quarterly 58 (3):244-248.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.


Added to PP index

Total views
3 ( #1,267,372 of 2,362,031 )

Recent downloads (6 months)
1 ( #553,136 of 2,362,031 )

How can I increase my downloads?


My notes