Toward the limits of the Tennenbaum phenomenon
type: Item
instance of: scholarly article
title: Toward the limits of the Tennenbaum phenomenon
zbMATH Open document ID: 0889.03052
author: Paola D'Aquino
published in: Notre Dame Journal of Formal Logic
publication date: 1998-02-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 03H15
Mathematics Subject Classification ID: 03C57
zbMATH DE Number: 1109540
zbMATH Keywords: Tennenbaum phenomenon
zbMATH Keywords: nonstandard models of arithmetic
zbMATH Keywords: weak fragments of arithmetic
reviewed by: Roman Kossak
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1305/ndjfl/1039700698
OpenAlex ID: W1964137622
cites work: Q5442501
cites work: A recursive nonstandard model of normal open induction
cites work: Combinatorial principles in elementary number theory
cites work: Q3794177
cites work: Pell equations and exponentiation in fragments of arithmetic
cites work: Q3962995
cites work: Q4001935
cites work: Diophantine induction
cites work: Q4160889
cites work: On the complexity of models of arithmetic
cites work: Q4726219
cites work: Provability of the pigeonhole principle and the existence of infinitely many primes
cites work: Q5341750
cites work: On the scheme of induction for bounded arithmetic formulas
cites work: Bounded existential induction
DOI: 10.1305/NDJFL/1039700698
Recommended article: Q3118397
Recommended article: A recursive model for arithmetic with weak induction
Recommended article: An Effective Conservation Result for Nonstandard Arithmetic
Recommended article: On the structure of models of bounded $E\sb 1$-induction
Recommended article: Q3118401
Recommended article: Tennenbaum's theorem and unary functions
Recommended article: Recursive models and the divisibility poset
Recommended article: On a Problem of J. Paris
Recommended article: Bounded existential induction
Recommended article: Q4001935
description: scientific article; zbMATH DE number 1109540