# Tennenbaum's theorem

**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[edit]

A structure in the language of PA is **recursive** if there are recursive functions + and × from to , a recursive two-place relation < on , and distinguished constants such that

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[edit]

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[edit]

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 *i*th 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 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 *n*th 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).

## References[edit]

- 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.
*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