On End‐Extensions of Models of ¬exp

Mathematical Logic Quarterly 42 (1):1-18 (1996)
  Copy   BIBTEX

Abstract

Every model of IΔ0 is the tally part of a model of the stringlanguage theory Th-FO . We show how to “smoothly” introduce in Th-FO the binary length function, whereby it is possible to make exponential assumptions in models of Th-FO. These considerations entail that every model of IΔ0 + ¬exp is a proper initial segment of a model of Th-FO and that a modicum of bounded collection is true in these models

Categories

Keywords

Reprint years

DOI

10.1002/malq.19960420102

Links

PhilArchive



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

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

Two General Results on Intuitionistic Bounded Theories.Fernando Ferreira - 1999 - Mathematical Logic Quarterly 45 (3):399-407.
A note on the E1 collection scheme and fragments of bounded arithmetic.Zofia Adamowicz & Leszek Aleksander Kołodziejczyk - 2010 - Mathematical Logic Quarterly 56 (2):126-130.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
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.
Infinite substructure lattices of models of Peano Arithmetic.James H. Schmerl - 2010 - Journal of Symbolic Logic 75 (4):1366-1382.
Regularity in models of arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
Separations of first and second order theories in bounded arithmetic.Masahiro Yasumoto - 2005 - Archive for Mathematical Logic 44 (6):685-688.
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.
A note on sharply bounded arithmetic.Jan Johannsen - 1994 - Archive for Mathematical Logic 33 (2):159-165.
Algebraic Methods and Bounded Formulas.Domenico Zambella - 1997 - Notre Dame Journal of Formal Logic 38 (1):37-48.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Binary models generated by their tally part.Fernando Ferreira - 1994 - Archive for Mathematical Logic 33 (4):283-289.
End extensions of models of linearly bounded arithmetic.Domenico Zambella - 1997 - Annals of Pure and Applied Logic 88 (2-3):263-277.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.

Analytics

Added to PP
2013-12-01

Downloads
237 (#82,006)

6 months
2 (#1,263,261)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Groundwork for weak analysis.António M. Fernandes & Fernando Ferreira - 2002 - Journal of Symbolic Logic 67 (2):557-578.
On a Theory for AC0 and the Strength of the Induction Scheme.Satoru Kuroda - 1998 - Mathematical Logic Quarterly 44 (3):417-426.

Add more citations

References found in this work

On the scheme of induction for bounded arithmetic formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (C):261-302.
¹1-formulae on finite structures.M. Ajtai - 1983 - Annals of Pure and Applied Logic 24 (1):1.
Binary models generated by their tally part.Fernando Ferreira - 1994 - Archive for Mathematical Logic 33 (4):283-289.
Modèles non Standard en Arithmétique et théorie des Ensembles.Peter Clote - 1989 - Journal of Symbolic Logic 54 (1):284-287.

Add more references