On the complexity of models of arithmetic
- 1 June 1982
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 47 (2) , 403-415
- https://doi.org/10.2307/2273150
Abstract
Let P0 be the subsystem of Peano arithmetic obtained by restricting induction to bounded quantifier formulas. Let M be a countable, nonstandard model of P0 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.Keywords
This publication has 5 references indexed in Scilit:
- Some conservation results for fragments of arithmeticPublished by Springer Nature ,1981
- Theorie elementaire de la multiplication des entiers naturelsPublished by Springer Nature ,1981
- The additive structure of models of arithmeticProceedings of the American Mathematical Society, 1978
- Initial segments of models of Peano's axiomsLecture Notes in Mathematics, 1977
- Experimental logics and Δ inf2 sup0 - theoriesJournal of Philosophical Logic, 1975