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 {\displaystyle M} in the language of PA is recursive if there are recursive functions ⊕ {\displaystyle \oplus } and ⊗ {\displaystyle \otimes } from N × N {\displaystyle \mathbb {N} \times \mathbb {N} } to N {\displaystyle \mathbb {N} } , a recursive two-place relation <M on N {\displaystyle \mathbb {N} } , and distinguished constants n 0 , n 1 {\displaystyle n_{0},n_{1}} such that
( N , ⊕ , ⊗ , < M , n 0 , n 1 ) ≅ M , {\displaystyle (\mathbb {N} ,\oplus ,\otimes ,<_{M},n_{0},n_{1})\cong M,}
where ≅ {\displaystyle \cong } indicates isomorphism and N {\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. Equivalently, M {\displaystyle M} is recursive iff there exists a bijection f : M → N {\displaystyle f:M\to \mathbb {N} } , such that the relationships f ( m ) + M f ( n ) = f ( k ) {\displaystyle f(m)+_{M}f(n)=f(k)} , f ( m ) × M f ( n ) = f ( k ) {\displaystyle f(m)\times _{M}f(n)=f(k)} , and f ( m ) < M f ( n ) {\displaystyle 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 ∈ M {\displaystyle x\in M} can be viewed as a code for a set S x {\displaystyle S_{x}} of elements of M. In particular, if we let p i {\displaystyle p_{i}} be the ith prime in M, then z ∈ S x ↔ M ⊨ p z | x {\displaystyle z\in S_{x}\leftrightarrow M\vDash p_{z}|x} . Each set S x {\displaystyle S_{x}} will be bounded in M, but if x is nonstandard then the set S x {\displaystyle S_{x}} may contain infinitely many standard natural numbers. The standard system of the model is the collection { S x ∩ N : x ∈ M } {\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. These are disjoint r.e. sets A , B ⊆ N {\displaystyle A,B\subseteq \mathbb {N} } so that there is no recursive set C ⊆ N {\displaystyle C\subseteq \mathbb {N} } with A ⊆ C {\displaystyle A\subseteq C} and B ∩ C = ∅ {\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 i ∈ A {\displaystyle i\in A} then p i | y {\displaystyle p_{i}|y} and if i ∈ B {\displaystyle i\in B} then p i ∤ y {\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 m ∈ M {\displaystyle m\in M} with m < M x {\displaystyle m<_{M}x} , we have
M ⊨ ( m ∈ A → p m | y ) ∧ ( m ∈ B → p m ∤ y ) {\displaystyle M\vDash (m\in A\to p_{m}|y)\land (m\in B\to p_{m}\nmid y)}
Let S = N ∩ S y {\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 A ⊆ S {\displaystyle A\subseteq S} and B ∩ S = ∅ {\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 S = N ∩ S a {\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 n 0 {\displaystyle n_{0}} is the element of M corresponding to 0, and n 1 {\displaystyle n_{1}} is the element of M corresponding to 1, then for each i ∈ N {\displaystyle i\in \mathbb {N} } we can compute n i = n 1 ⊕ ⋯ ⊕ n 1 {\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 N {\displaystyle \mathbb {N} } . Then, search for an element y of M so that
a = y ⊕ y ⊕ ⋯ ⊕ y ⏟ p times ⊕ n i {\displaystyle a=\underbrace {y\oplus y\oplus \cdots \oplus y} _{p{\text{ times}}}\oplus n_{i}}
for some i < p {\displaystyle i<p} . This search will halt because the Euclidean algorithm can be applied to any model of PA. Finally, we have n ∈ S {\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.
References
Bibliography