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.

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.

Equivalently, $M$ is recursive iff there exists a bijection $f:M\to \mathbb{N}$, such that the relationships $f(m){+}_{M}f(n)=f(k)$, $f(m){\times }_{M}f(n)=f(k)$, and $f(m){<}_{M}f(n)$ are computationally decidable.

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\models 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. 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=\mathrm{\varnothing }$.

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\models (m\in A\to p_m|y)\wedge (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=\mathrm{\varnothing }$. 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=\underset{p\text{ times}}{\underbrace{y\oplus y\oplus \cdots \oplus y}}\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).

Turing degrees of models of PA

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

Bibliography

• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite journal