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

A structure $M$ in the language of PA is recursive if there are recursive functions $\oplus$ and $\otimes$ from $\mathbb {N} \times \mathbb {N}$ to $\mathbb {N}$ , a recursive two-place relation <_M on $\mathbb {N}$ , and distinguished constants $n_{0},n_{1}$ such that

(\mathbb {N} ,\oplus ,\otimes ,<_{M},n_{0},n_{1})\cong M,

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 $z\in S_{x}\leftrightarrow M\vDash p_{z}|x$ . 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 $\{S_{x}\cap \mathbb {N} :x\in M\}$ . 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 $A,B\subseteq \mathbb {N}$ so that there is no recursive set $C\subseteq \mathbb {N}$ with $A\subseteq C$ and $B\cap C=\emptyset$ .

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

M\vDash (m\in A\to p_{m}|y)\land (m\in B\to p_{m}\nmid y)

Let $S=\mathbb {N} \cap S_{y}$ be the corresponding set in the standard system of M. Because A and B are r.e., one can show that $A\subseteq S$ and $B\cap S=\emptyset$ . 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 $S=\mathbb {N} \cap S_{a}$ 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 $i\in \mathbb {N}$ we can compute $n_{i}=n_{1}\oplus \cdots \oplus n_{1}$ (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

a=\underbrace {y\oplus y\oplus \cdots \oplus y} _{p{\text{ times}}}\oplus n_{i}

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

References

Boolos, George; Burgess, John P.; Jeffrey, Richard (2002). Computability and Logic (4th ed.). Cambridge University Press. ISBN 0-521-00758-5.
Kaye, Richard (1991). Models of Peano arithmetic. Oxford University Press. ISBN 0-19-853213-X.
Kaye, Richard (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. Vol. 36. ISBN 9781107008045.
Tennenbaum, Stanley (1959). "Non-Archimedean models for arithmetic". Notices of the American Mathematical Society. 6: 270.