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

References[]