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).
in the language of PA is recursive if there are recursive functions
, a recursive two-place relation 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. 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 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). For the latter construction, begin with a pair of recursively inseparable r.e. For natural number x there is a y such that, for all i < x, if 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 be the corresponding set in the standard system of M. Because A and B are r.e., one can show that 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 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 To decide if a number n is in S, first compute p, the nth prime in 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. 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). Jockush and Soare have shown there exists a model of PA with low degree.