End extensions of models of linearly bounded arithmetic

Annals of Pure and Applied Logic 88 (2-3):263-277 (1997)
  Copy   BIBTEX

Abstract

We show that every model of IΔ0 has an end extension to a model of a theory where log-space computable function are formalizable. We also show the existence of an isomorphism between models of IΔ0 and models of linear arithmetic LA

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(97)00026-2

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

An unexpected separation result in Linearly Bounded Arithmetic.Arnold Beckmann & Jan Johannsen - 2005 - Mathematical Logic Quarterly 51 (2):191-200.
On End‐Extensions of Models of ¬exp.Fernando Ferreira - 1996 - Mathematical Logic Quarterly 42 (1):1-18.
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.
Subsets of models of arithmetic.Roman Kossak & Jeffrey B. Paris - 1992 - Archive for Mathematical Logic 32 (1):65-73.
Forcing in Finite Structures.Domenico Zambella - 1997 - Mathematical Logic Quarterly 43 (3):401-412.
On cofinal extensions of models of arithmetic.Henryk Kotlarski - 1983 - Journal of Symbolic Logic 48 (2):253-262.
Regularity in models of arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
Algebraic Methods and Bounded Formulas.Domenico Zambella - 1997 - Notre Dame Journal of Formal Logic 38 (1):37-48.
A note on sharply bounded arithmetic.Jan Johannsen - 1994 - Archive for Mathematical Logic 33 (2):159-165.
Finite reverse mathematics.Harvey Friedman - manuscript
Binary models generated by their tally part.Fernando Ferreira - 1994 - Archive for Mathematical Logic 33 (4):283-289.
On certain types and models for arithmetic.Andreas Blass - 1974 - Journal of Symbolic Logic 39 (1):151-162.
Infinite substructure lattices of models of Peano Arithmetic.James H. Schmerl - 2010 - Journal of Symbolic Logic 75 (4):1366-1382.

Analytics

Added to PP
2014-01-16

Downloads
23 (#664,515)

6 months
10 (#251,846)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Iterated multiplication in $$ VTC ^0$$.Emil Jeřábek - forthcoming - Archive for Mathematical Logic.
A theory for log-space and NLIN versus co-NLIN.Chris Pollett - 2003 - Journal of Symbolic Logic 68 (4):1082-1090.
Iterated multiplication in $$ VTC ^0$$ V T C 0. [REVIEW]Emil Jeřábek - 2022 - Archive for Mathematical Logic 61 (5-6):705-767.

View all 7 citations / 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.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.

View all 6 references / Add more references