Tennenbaum's theorem and unary functions (Q929636)

The main theorem of the paper gives a general condition under which realizations of tuples of PA-provably total functions in a nonstandard model of PA cannot have simultaneous computable presentations. As a corollary, it is shown that the pairs of functions \(\{2x, 2x+1\}\), \(\{x^2,2x^2\}\), and \(\{2^x,3^x\}\) in a nonstandard model of PA do not have computable presentations. In the opposite direction, it is shown that for each computable injection \(f\) there is a nonstandard model whose \(f\) has a computable presentation. This is a strengthening of a result of \textit{P. D'Aquino} from ``Towards the limits of the Tennenbaum phenomenon'' [Notre Dame J. Formal Logic 38, No. 1, 81--92 (1997; Zbl 0889.03052)]. The result is optimal. There are primitive recursive functions whose nonstandard realizations do not admit computable presentations. An example is given in the paper.