Tennenbaum's theorem

Not to be confused with Tennenbaum's construction of a computable copy of ${\displaystyle \omega +\omega ^{*}}$ having no computable infinite ascending or descending chains.

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

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

where ${\displaystyle \cong }$ indicates isomorphism and ${\displaystyle \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 ${\displaystyle x\in M}$ can be viewed as a code for a set ${\displaystyle S_{x}}$ of elements of M. In particular, if we let ${\displaystyle p_{i}}$ be the ith prime in M, then ${\displaystyle z\in S_{x}\leftrightarrow M\vDash p_{z}|x}$. Each set ${\displaystyle S_{x}}$ will be bounded in M, but if x is nonstandard then the set ${\displaystyle S_{x}}$ may contain infinitely many standard natural numbers. The standard system of the model is the collection ${\displaystyle \{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 ${\displaystyle A,B\subseteq \mathbb {N} }$ so that there is no recursive set ${\displaystyle C\subseteq \mathbb {N} }$ with ${\displaystyle A\subseteq C}$ and ${\displaystyle 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 ${\displaystyle i\in A}$ then ${\displaystyle p_{i}|y}$ and if ${\displaystyle i\in B}$ then ${\displaystyle 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 ${\displaystyle m\in M}$ with ${\displaystyle m<_{M}x}$, we have

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

Let ${\displaystyle 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 ${\displaystyle A\subseteq S}$ and ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \oplus }$ of M as an oracle. In particular, if ${\displaystyle n_{0}}$ is the element of M corresponding to 0, and ${\displaystyle n_{1}}$ is the element of M corresponding to 1, then for each ${\displaystyle i\in \mathbb {N} }$ we can compute ${\displaystyle 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 ${\displaystyle \mathbb {N} }$. Then, search for an element y of M so that

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

for some ${\displaystyle i<p}$. This search will halt because the Euclidean algorithm can be applied to any model of PA. Finally, we have ${\displaystyle 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.^[1]

References