On the complexity of models of arithmetic

Journal of Symbolic Logic 47 (2):403-415 (1982)
  Copy   BIBTEX

Abstract

Let P 0 be the subsystem of Peano arithmetic obtained by restricting induction to bounded quantifier formulas. Let M be a countable, nonstandard model of P 0 whose domain we suppose to be the standard integers. Let T be a recursively enumerable extension of Peano arithmetic all of whose existential consequences are satisfied in the standard model. Then there is an initial segment M ' of M which is a model of T such that the complete diagram of M ' is Turing reducible to the atomic diagram of M. Moreover, neither the addition nor the multiplication of M is recursive

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,480

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

Theories of Arithmetics in Finite Models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
Torre Models in the Isols.Joseph Barback - 1994 - Journal of Symbolic Logic 59 (1):140-150.
On Certain Types and Models for Arithmetic.Andreas Blass - 1974 - Journal of Symbolic Logic 39 (1):151-162.
A Model of Peano Arithmetic with No Elementary End Extension.George Mills - 1978 - Journal of Symbolic Logic 43 (3):563-567.
Regularity in Models of Arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
Model-Theoretic Properties Characterizing Peano Arithmetic.Richard Kaye - 1991 - Journal of Symbolic Logic 56 (3):949-963.
Models Without Indiscernibles.Fred G. Abramson & Leo A. Harrington - 1978 - Journal of Symbolic Logic 43 (3):572-600.

Analytics

Added to PP
2009-01-28

Downloads
77 (#155,610)

6 months
1 (#417,474)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Computational Structuralism &Dagger.Volker Halbach & Leon Horsten - 2005 - Philosophia Mathematica 13 (2):174-186.
Diophantine Induction.Richard Kaye - 1990 - Annals of Pure and Applied Logic 46 (1):1-40.
On Gödel Incompleteness and Finite Combinatorics.Akihiro Kanamori & Kenneth McAloon - 1987 - Annals of Pure and Applied Logic 33 (C):23-41.

View all 10 citations / Add more citations

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Some Applications of Kleene's Methods for Intuitionistic Systems.Harvey Friedman - 1973 - In A. R. D. Mathias & H. Rogers (eds.), Cambridge Summer School in Mathematical Logic. New York: Springer Verlag. pp. 113--170.

Add more references