A Note on Conservativity Relations among Bounded Arithmetic Theories

&
Mathematical Logic Quarterly 48 (3):375-377 (2002)
  Copy   BIBTEX

Abstract

For all i ≥ 1, Ti+11 is not ∀Σb2-conservative over Ti1

Categories

Keywords

Reprint years

DOI

10.1002/1521-3870(200204)48:3

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

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

Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem.Neil Thapen - 2011 - Archive for Mathematical Logic 50 (7):665-680.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Review: Jan Krajicek, Pavel Pudlak, Gaisi Takeuti, Bounded Arithmetic and the Polynomial Hierarchy; Samuel R. Buss, Relating the Bounded Arithmetic and Polynomial Time Hierarchies; Domenico Zambella, Notes on Polynomially Bounded Arithmetic. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
Separations of first and second order theories in bounded arithmetic.Masahiro Yasumoto - 2005 - Archive for Mathematical Logic 44 (6):685-688.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
On the Herbrand Notion of Consistency for Finitely Axiomatizable Fragments of Bounded Arithmetic Theories.Leszek Aleksander Kołodziejczyk - 2006 - Journal of Symbolic Logic 71 (2):624 - 638.
NP Search Problems in Low Fragments of Bounded Arithmetic.Jan Krajíček, Alan Skelley & Neil Thapen - 2007 - Journal of Symbolic Logic 72 (2):649 - 672.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
On the correspondence between arithmetic theories and propositional proof systems – a survey.Olaf Beyersdorff - 2009 - Mathematical Logic Quarterly 55 (2):116-137.
A note on propositional proof complexity of some Ramsey-type statements.Jan Krajíček - 2011 - Archive for Mathematical Logic 50 (1-2):245-255.
Regularity in models of arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
Two General Results on Intuitionistic Bounded Theories.Fernando Ferreira - 1999 - Mathematical Logic Quarterly 45 (3):399-407.
Tautologies from pseudo-random generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
Strict $${\Pi^1_1}$$ -reflection in bounded arithmetic.António M. Fernandes - 2010 - Archive for Mathematical Logic 49 (1):17-34.

Analytics

Added to PP
2013-12-01

Downloads
24 (#642,030)

6 months
6 (#512,819)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Incompleteness in the Finite Domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.
Towards NP – P via proof complexity and search.Samuel R. Buss - 2012 - Annals of Pure and Applied Logic 163 (7):906-917.

Add more citations

References found in this work

Lifting independence results in bounded arithmetic.Mario Chiari & Jan Krajíček - 1999 - Archive for Mathematical Logic 38 (2):123-138.

Add more references