Tennenbaum's Theorem and Unary Functions

Notre Dame Journal of Formal Logic 49 (2):177-183 (2008)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 94,726

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

Solovay's theorem cannot be simplified.Andrew Arana - 2001 - Annals of Pure and Applied Logic 112 (1):27-41.
Definability of Initial Segments.Akito Tsuboi & Saharon Shelah - 2002 - Notre Dame Journal of Formal Logic 43 (2):65-73.
Models of Peano Arithmetic.Richard Kaye - 1991 - Clarendon Press.
A Nonstandard Counterpart of WWKL.Stephen G. Simpson & Keita Yokoyama - 2011 - Notre Dame Journal of Formal Logic 52 (3):229-243.


Added to PP

22 (#718,087)

6 months
9 (#454,638)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Toward the Limits of the Tennenbaum Phenomenon.Paola D'Aquino - 1997 - Notre Dame Journal of Formal Logic 38 (1):81-92.
Recursive Models and the Divisibility Poset.James H. Schmerl - 1998 - Notre Dame Journal of Formal Logic 39 (1):140-148.

Add more references