Tennenbaum's theorem, named for Stanley Tennenbaum who presented the theorem in 1959, is a result in mathematical logic that states that no countable nonstandard model of first-order Peano arithmetic (PA) can be recursive (Kaye 1991:153ff).
Recursive structures for PA
where indicates isomorphism and is the set of (standard) natural numbers. Because the isomorphism must be a bijection, every recursive model is countable. There are many nonisomorphic countable nonstandard models of PA.
Statement of the theorem
Tennenbaum's theorem states that no countable nonstandard model of PA is recursive. Moreover, neither the addition nor the multiplication of such a model can be recursive.
This sketch follows the argument presented by Kaye (1991). The first step in the proof is to show that, if M is any countable nonstandard model of PA, then the standard system of M (defined below) contains at least one nonrecursive set S. The second step is to show that, if either the addition or multiplication operation on M were recursive, then this set S would be recursive, which is a contradiction.
Through the methods used to code ordered tuples, each element can be viewed as a code for a set of elements of M. In particular, if we let be the ith prime in M, then . Each set will be bounded in M, but if x is nonstandard then the set may contain infinitely many standard natural numbers. The standard system of the model is the collection . It can be shown that the standard system of any nonstandard model of PA contains a nonrecursive set, either by appealing to the incompleteness theorem or by directly considering a pair of recursively inseparable r.e. sets (Kaye 1991:154). These are disjoint r.e. sets so that there is no recursive set with and .
For the latter construction, begin with a pair of recursively inseparable r.e. sets A and B. For natural number x there is a y such that, for all i < x, if then and if then . By the overspill property, this means that there is some nonstandard x in M for which there is a (necessarily nonstandard) y in M so that, for every with , we have
Let be the corresponding set in the standard system of M. Because A and B are r.e., one can show that and . Hence S is a separating set for A and B, and by the choice of A and B this means S is nonrecursive.
Now, to prove Tennenbaum's theorem, begin with a nonstandard countable model M and an element a in M so that is nonrecursive. The proof method shows that, because of the way the standard system is defined, it is possible to compute the characteristic function of the set S using the addition function of M as an oracle. In particular, if is the element of M corresponding to 0, and is the element of M corresponding to 1, then for each we can compute (i times). To decide if a number n is in S, first compute p, the nth prime in N. Then, search for an element y of M so that
for some . This search will halt because the Euclidean algorithm can be applied to any model of PA. Finally, we have if and only if the i found in the search was 0. Because S is not recursive, this means that the addition operation on M is nonrecursive.
A similar argument shows that it is possible to compute the characteristic function of S using the multiplication of M as an oracle, so the multiplication operation on M is also nonrecursive (Kaye 1991:154).
- George Boolos, John P. Burgess, and Richard Jeffrey (2002) Computability and Logic, 4th ed. Cambridge University Press. ISBN 0-521-00758-5
- Richard Kaye (1991) Models of Peano arithmetic. Oxford University Press. ISBN 0-19-853213-X.
- Richard Kaye (Sep 2011). "Tennenbaum's Theorem for Models of Arithmetic". In Juliette Kennedy and Roman Kossak (ed.). Set theory, arithmetic, and foundations of mathematics - theorems, philosophies (PDF). Lecture Notes in Logic. 36. ISBN 9781107008045.
- Stanley Tennenbaum (1959) Non-Archimedean models for arithmetic, In: Notices of the American Mathematical Society 6, p. 270