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

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 97,335

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

On End‐Extensions of Models of ¬exp.Fernando Ferreira - 1996 - Mathematical Logic Quarterly 42 (1):1-18.
Intuitionistic axiomatizations for bounded extension Kripke models.Mohammad Ardeshir, Wim Ruitenburg & Saeed Salehi - 2003 - Annals of Pure and Applied Logic 124 (1-3):267-285.
On certain types and models for arithmetic.Andreas Blass - 1974 - Journal of Symbolic Logic 39 (1):151-162.
A sharpened version of McAloon's theorem on initial segments of models of IΔ0.Paola D'Aquino - 1993 - Annals of Pure and Applied Logic 61 (1-2):49-62.
Translating IΔ0 + exp Proofs into Weaker Systems.Chris Pollett - 2000 - Mathematical Logic Quarterly 46 (2):249-256.
Structures interpretable in models of bounded arithmetic.Neil Thapen - 2005 - Annals of Pure and Applied Logic 136 (3):247-266.
Herbrand consistency of some finite fragments of bounded arithmetical theories.Saeed Salehi - 2013 - Archive for Mathematical Logic 52 (3-4):317-333.
Quadratic forms in models of IΔ0+ Ω1, Part II: Local equivalence.Paola D’Aquino & Angus Macintyre - 2011 - Annals of Pure and Applied Logic 162 (6):447-456.
End-extensions of models of weak arithmetic from complexity-theoretic containments.Leszek Aleksander Kołodziejczyk - 2016 - Journal of Symbolic Logic 81 (3):901-916.
Real closures of models of weak arithmetic.Emil Jeřábek & Leszek Aleksander Kołodziejczyk - 2013 - Archive for Mathematical Logic 52 (1):143-157.

Analytics

Added to PP
2014-01-16

Downloads
31 (#582,285)

6 months
17 (#232,263)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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

View all 6 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.

Add more references