The strength of sharply bounded induction requires M S P

&
Annals of Pure and Applied Logic 161 (4):504-510 (2010)
  Copy   BIBTEX

Abstract

We show that the arithmetical theory -INDx5, formalized in the language of Buss, i.e. with x/2 but without the MSP function x/2y, does not prove that every nontrivial divisor of a power of 2 is even. It follows that this theory proves neither NP=coNP nor

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2009.03.002

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 105,131

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The strength of sharply bounded induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
Pell equations and exponentiation in fragments of arithmetic.Paola D'Aquino - 1996 - Annals of Pure and Applied Logic 77 (1):1-34.
Multifunction algebras and the provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
Consequences of the Provability of NP ⊆ P/poly.Stephen Cook & Jan Krajíček - 2007 - Journal of Symbolic Logic 72 (4):1353 - 1371.
Independence results for variants of sharply bounded induction.Leszek Aleksander Kołodziejczyk - 2011 - Annals of Pure and Applied Logic 162 (12):981-990.
Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Kreisel's Conjecture with minimality principle.Pavel Hrubeš - 2009 - Journal of Symbolic Logic 74 (3):976-988.
Enumerations of the Kolmogorov Function.Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet - 2006 - Journal of Symbolic Logic 71 (2):501 - 528.
On Grzegorczyk induction.Ch Cornaros - 1995 - Annals of Pure and Applied Logic 74 (1):1-21.
Some conservation results on weak König's lemma.Stephen G. Simpson, Kazuyuki Tanaka & Takeshi Yamazaki - 2002 - Annals of Pure and Applied Logic 118 (1-2):87-114.

Analytics

Added to PP
2013-12-18

Downloads
90 (#249,169)

6 months
4 (#1,011,530)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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

View all 8 citations / Add more citations

References found in this work

Multifunction algebras and the provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
The strength of sharply bounded induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.

Add more references