Fragments of bounded arithmetic and the lengths of proofs

Journal of Symbolic Logic 73 (4):1389-1406 (2008)
  Copy   BIBTEX

Abstract

We consider the problem whether the $\forall \Sigma _{1}^{b}$ theorems of the fragments $T_{2}^{a}$ form a strictly increasing hierarchy. We shall show a link to some results about the lengths of proofs in predicate logic that supports the conjecture that the hierarchy is strictly increasing

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,642

External links

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

Through your library

Similar books and articles

Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Multifunction algebras and the provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
Examining fragments of the quantified propositional calculus.Steven Perron - 2008 - Journal of Symbolic Logic 73 (3):1051-1080.

Analytics

Added to PP
2010-09-12

Downloads
6 (#711,559)

6 months
18 (#821,922)

Historical graph of downloads
How can I increase my downloads?

References found in this work

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.
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.
Herbrandizing search problems in Bounded Arithmetic.Jiří Hanika - 2004 - Mathematical Logic Quarterly 50 (6):577-586.

View all 6 references / Add more references