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

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,553

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

An unexpected separation result in Linearly Bounded Arithmetic.Arnold Beckmann & Jan Johannsen - 2005 - Mathematical Logic Quarterly 51 (2):191-200.
Tautologies from pseudo-random generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
On the correspondence between arithmetic theories and propositional proof systems – a survey.Olaf Beyersdorff - 2009 - Mathematical Logic Quarterly 55 (2):116-137.
Jan Krajíček, Pavel Pudlák, and Gaisi Takeuti. Bounded arithmetic and the polynomial hierarchy. Ibid., vol. 52 , pp. 143–153. - Samuel R. Buss. Relating the bounded arithmetic and polynomial time hierarchies. Ibid., vol. 75 , pp. 67–77. - Domenico Zambella. Notes on polynomially bounded arithmetic. The journal of symbolic logic, vol. 61 , pp. 942–966. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem.Neil Thapen - 2011 - Archive for Mathematical Logic 50 (7):665-680.
A Remark on Independence Results for Sharply Bounded Arithmetic.Jan Johannsen - 1998 - Mathematical Logic Quarterly 44 (4):568-570.

Analytics

Added to PP
2013-12-01

Downloads
32 (#719,031)

6 months
5 (#1,094,893)

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