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

A structure M in the language of PA is recursive if there are recursive functions \oplus and \otimes from to \mathbb{N}, a recursive two-place relation <M on \mathbb{N}, and distinguished constants n_0,n_1 such that where \cong indicates isomorphism and \mathbb{N} 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.

Proof sketch

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 x \in M can be viewed as a code for a set S_x of elements of M. In particular, if we let p_i be the ith prime in M, then. Each set S_x will be bounded in M, but if x is nonstandard then the set S_x 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 i \in A then p_i | y and if i \in B then p_i \nmid y. 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 m \in M with m <_M x, 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 \oplus of M as an oracle. In particular, if n_0 is the element of M corresponding to 0, and n_1 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 \mathbb{N}. Then, search for an element y of M so that for some i < p. This search will halt because the Euclidean algorithm can be applied to any model of PA. Finally, we have n \in S 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).

Turing degrees of models of PA

Jockush and Soare have shown there exists a model of PA with low degree.