Annals of Pure and Applied Logic 162 (12):981-990 (2011)

The theory , axiomatized by the induction scheme for sharply bounded formulae in Buss’ original language of bounded arithmetic , has recently been unconditionally separated from full bounded arithmetic S2. The method used to prove the separation is reminiscent of those known from the study of open induction.We make the connection to open induction explicit, showing that models of can be built using a “nonstandard variant” of Wilkie’s well-known technique for building models of IOpen. This makes it possible to transfer many results and methods from open to sharply bounded induction with relative ease.We provide two applications: the Shepherdson model of IOpen can be embedded into a model of , which immediately implies some independence results for ; extended by an axiom which roughly states that every number has a least 1 bit in its binary notation, while significantly stronger than plain , does not prove the infinity of primes
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2011.06.003
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: 53,688
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

The Strength of Sharply Bounded Induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
Multifunction Algebras and the Provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
Bootstrapping, Part I.Sedki Boughattas & J. -P. Ressayre - 2010 - Annals of Pure and Applied Logic 161 (4):511-533.

View all 11 references / Add more references

Citations of this work BETA

Open Induction in a Bounded Arithmetic for TC0.Emil Jeřábek - 2015 - Archive for Mathematical Logic 54 (3-4):359-394.

Add more citations

Similar books and articles

Herbrand Consistency of Some Arithmetical Theories.Saeed Salehi - 2012 - Journal of Symbolic Logic 77 (3):807-827.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Agent Connectedness and Backward Induction.Christian W. Bach & Conrad Heilmann - 2011 - International Game Theory Review 13 (2):195-208.
Discouraging Results for Ultraimaginary Independence Theory.Itay Ben-Yaacov - 2003 - Journal of Symbolic Logic 68 (3):846-850.
Independence Results.Saharon Shelah - 1980 - Journal of Symbolic Logic 45 (3):563-573.
Kreisel's Conjecture with Minimality Principle.Pavel Hrubeš - 2009 - Journal of Symbolic Logic 74 (3):976-988.
Semi-Bounded Relations in Ordered Modules.Oleg Belegradek - 2004 - Journal of Symbolic Logic 69 (2):499 - 517.
On the Induction Schema for Decidable Predicates.Lev D. Beklemishev - 2003 - Journal of Symbolic Logic 68 (1):17-34.


Added to PP index

Total views
15 ( #625,438 of 2,349,561 )

Recent downloads (6 months)
5 ( #148,363 of 2,349,561 )

How can I increase my downloads?


My notes