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

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,854

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

The Structural Complexity of Models of Arithmetic.Antonio Montalbán & Dino Rossegger - 2024 - Journal of Symbolic Logic 89 (4):1703-1719.
Marginalia on a theorem of Woodin.Rasmus Blanck & Ali Enayat - 2017 - Journal of Symbolic Logic 82 (1):359-374.
A note on standard systems and ultrafilters.Fredrik Engström - 2008 - Journal of Symbolic Logic 73 (3):824-830.
Nondiversity in substructures.James H. Schmerl - 2008 - Journal of Symbolic Logic 73 (1):193-211.
Omega‐ and Beta‐Models of Alternative Set Theory.Athanassios Tzouvaras - 1994 - Mathematical Logic Quarterly 40 (4):547-569.

Analytics

Added to PP
2009-01-28

Downloads
99 (#214,821)

6 months
4 (#1,272,377)

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 9 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 & Hartley Rogers (eds.), Cambridge Summer School in Mathematical Logic. New York,: Springer Verlag. pp. 113--170.

Add more references