The theorem known as Tennenbaum's Theorem
was given by Stanley Tennenbaum in a paper at the
April meeting in Monterey, California, 1959, and
published as a one-page abstract in the Notices of the
American Mathematical Society (tennenbaum1959).
It is easily stated as saying that there is no
nonstandard recursive model of Peano Arithmetic,
and is an attractive and rightly often-quoted result.
This paper celebrates Tennenbaum's Theorem; we state the result fully and give a proof of it and other related results later. This introduction is in the main historical. The goals of the latter parts of this paper are: to set out the connections between Tennenbaum's Theorem for models of arithmetic and the Gödel–Rosser Theorem and recursively inseparable sets; and to investigate stronger versions of Tennenbaum's Theorem and their relationship to some diophantine problems in systems of arithmetic.
Tennenbaum's theorem was discovered in a period of
foundational studies, associated particularly with Mostowski,
where it still seemed conceivable that useful independence
results for arithmetic could be achieved by a hands-on
approach to building nonstandard models of arithmetic.
Mostowski's own aspirations for the programme are clearly
set out in his address to the 8th Congress of Polish
mathematicians in September 1953 (MR0066288).
Mostowski called for an axiomatic treatment of arithmetic and
its models, and cites Ryll-Nardzewski (MR0054546)
and Rosser and Wang (MR0038307) as early proponents
of the theory of models of arithmetic.
Mostowski places problems of induction and inductive definitions
at the forefront of studies in arithmetic, but lists
several secondary but nevertheless important and
interesting problems connected with the axioms of arithmetic of
natural numbers
:
What kind of structure have the models of Peano's arithmetic differing from a model composed of natural numbers; in particular, what is their ordinal [i.e., order] type like? After Rosser and Wang (MR0038307) we term such models non-standard. Some initial results on these lines have been published by Kemeny (MR0024400).
To find out whether by using non-standard models it would be possible to obtain proofs for the independence of classical number-theoretical problems of the system of arithmetical axioms.
To prove the incompleteness of axiomatic arithmetic without applying the method of arithmetization by giving suitable models showing the consistency and independence of an appropriately chosen number-theoretical axiom.
Mostowski's questions are good ones. Although the order-type of a
countable model of
Skolem had, of course, already built nonstandard models of arithmetic by an ultrapower-like construction. His 1955 paper (MR0075150) is the most accessible and widely quoted, and was written for the proceedings of a symposium in Amsterdam in 1954, but is essentially just a translation of an earlier (1934) paper (skolem1934). Skolem had raised the question of recursiveness of nonstandard models, and Mostowski answered his question, using recursively inseparable r.e. sets to show that no nonstandard model of primitive recursive arithmetic with predicates for all primitive recursive functions can be recursive (MR0093483). Kreisel's review [MR0093483] of this paper is illuminating:
The proof [of Mostowki's main theorem] shows that there is no recursive non-standard model in which all theorems of (quantifier-free) primitive recursive arithmetic are valid. In other words, recursive models are useless for independence problems in full primitive recursive arithmetic. This answers a question raised by Skolem at Amsterdam in 1954 [...]. It is not known if elementary arithmetic with addition and multiplication as the sole non-logical constants has a recursive non-standard model.
Mostowski's theorem was not an isolated event, but followed from a number of earlier papers constructing theories with no recursive models (MR0060423) (MR0072081), and Kreisel (MR0060431) and Putnam (Putnam1957) had independently obtained similar results to Mostowski's.
As for independence results, Kemeny did produce a model that addressed some questions of independence in 1958 (MR0098685). As one in hindsight would expect, Kemeny's model was shown soon afterwards to fail to satisfy any particularly interesting induction axioms for arithmetic (Gandy (MR0098686)). To my mind, the highlight of this period of building recursive models for the purposes of independence results was the results of the early 1960s by Shepherdson, who, using algebraic methods, produced beautiful nonstandard models of quantifier-free arithmetic in which he showed number theoretic results such as the infinitude of primes and Fermat's Last Theorem (in fact, for exponent 3) are false (MR0161798). By this time Tennenbaum's theorem was already well known, and Shepherdson and others were certainly aware of the limitations of this approach.
Further results along the same lines as Tennenbaum's appeared soon afterwards. Feferman (MR0147397) presented a detailed examination of arithmetization, including the result quoted by Tennenbaum in his abstract that no nonstandard model of full arithmetic can be arithmetically defined. Dana Scott (MR0152445) also investigated constructions of models of arithmetic, including an elegant algebraic construction and a proof of Tennenbaum's theorem.
In the following sections, we shall go into more detail, stating and proving Tennenbaum's theorem, and then discussing what theory of arithmetic is actually needed in the model for it to hold. This will bring us on to more recent questions connected with diophantine problems and the solution to Hilbert's 10th problem.