On the complexity of models of arithmetic
Journal of Symbolic Logic 47 (2):403-415 (1982)
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 recursiveDOI
10.2307/2273150
My notes
Similar books and articles
Some remarks on initial segments in models of peano arithmetic.Henryk Kotlarski - 1984 - Journal of Symbolic Logic 49 (3):955-960.
Theories of arithmetics in finite models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
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.
The strength of nonstandard methods in arithmetic.C. Ward Henson, Matt Kaufmann & H. Jerome Keisler - 1984 - Journal of Symbolic Logic 49 (4):1039-1058.
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.
The complexity of classification problems for models of arithmetic.Samuel Coskey & Roman Kossak - 2010 - Bulletin of Symbolic Logic 16 (3):345-358.
Analytics
Added to PP
2009-01-28
Downloads
77 (#159,106)
6 months
1 (#449,220)
2009-01-28
Downloads
77 (#159,106)
6 months
1 (#449,220)
Historical graph of downloads
Citations of this work
Computational Structuralism &dagger.Volker Halbach & Leon Horsten - 2005 - Philosophia Mathematica 13 (2):174-186.
Every countable model of set theory embeds into its own constructible universe.Joel David Hamkins - 2013 - Journal of Mathematical Logic 13 (2):1350006.
Hierarchical incompleteness results for arithmetically definable extensions of fragments of arithmetic.Rasmus Blanck - 2021 - Review of Symbolic Logic 14 (3):624-644.
On Gödel incompleteness and finite combinatorics.Akihiro Kanamori & Kenneth McAloon - 1987 - Annals of Pure and Applied Logic 33 (C):23-41.
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.