Tennenbaum's Theorem and Unary Functions
Yaegasi, Sakae
Notre Dame J. Formal Logic, Tome 49 (2008) no. 1, p. 177-183 / Harvested from Project Euclid
It is well known that in any nonstandard model of $\mathsf{PA}$ (Peano arithmetic) neither addition nor multiplication is recursive. In this paper we focus on the recursiveness of unary functions and find several pairs of unary functions which cannot be both recursive in the same nonstandard model of $\mathsf{PA}$ (e.g., $\{2x,2x+1\}$ , $\{x^2,2x^2\}$ , and $\{2^x,3^x\}$ ). Furthermore, we prove that for any computable injection $f(x)$ , there is a nonstandard model of $\mathsf{PA}$ in which $f(x)$ is recursive.
Publié le : 2008-04-15
Classification:  nonstandard models,  Tennenbaum's theorem,  Peano arithmetic,  03H15,  03C62,  03F30
@article{1210859926,
     author = {Yaegasi, Sakae},
     title = {Tennenbaum's Theorem and Unary Functions},
     journal = {Notre Dame J. Formal Logic},
     volume = {49},
     number = {1},
     year = {2008},
     pages = { 177-183},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1210859926}
}
Yaegasi, Sakae. Tennenbaum's Theorem and Unary Functions. Notre Dame J. Formal Logic, Tome 49 (2008) no. 1, pp.  177-183. http://gdmltest.u-ga.fr/item/1210859926/