Toward the limits of the Tennenbaum phenomenon (Q1377555): Difference between revisions

According to Tennenbaum's theorem, if \(M\) is a nonstandard model of PA, then neither \(+\) nor \(\times\) of \(M\) have recursive presentations. It is an important open problem to determine the weakest fragment of PA for which the same phenomenon holds. The best result so far is due to \textit{R.Kaye} [Ann. Pure Appl. Log. 46, No. 1, 1-40 (1990; Zbl 0693.03038)], who showed that \(+\) and \(\times\) of models of existential parameter free induction which are not models of \(\forall E_{1}({\mathbf N})\), have no recursive representations. D'Aquino proves a stronger result, but for the theory in the language of arithmetic with an additional function symbol \(\sharp\), representing the function \(\sharp(x,y)=x^{[\log_2y]}\), with appropriate axiomatization. Separate proofs are given for PA\(^{\sharp}\) and for weak fragments \(\forall E^{\sharp}_{1}({\mathbf N})\) and \(IE^{-\sharp}_{1}\). The paper is concluded with a result giving a general condition under which a \textit{unary} function in a nonstandard model of PA can have a recursive representation. Examples include the functions \(2^n\), \(n!\) and \(p_n\) -- the \(n\)-th prime.