On the Complexity of Models of Arithmetic
McAloon, Kenneth
J. Symbolic Logic, Tome 47 (1982) no. 1, p. 403-415 / Harvested from Project Euclid
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.
Publié le : 1982-06-14
Classification: 
@article{1183741006,
     author = {McAloon, Kenneth},
     title = {On the Complexity of Models of Arithmetic},
     journal = {J. Symbolic Logic},
     volume = {47},
     number = {1},
     year = {1982},
     pages = { 403-415},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183741006}
}
McAloon, Kenneth. On the Complexity of Models of Arithmetic. J. Symbolic Logic, Tome 47 (1982) no. 1, pp.  403-415. http://gdmltest.u-ga.fr/item/1183741006/