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 Peano arithmetic (PA) can be recursive.
Recursive structures for PA
A structure in the language of PA is recursive if there are recursive functions + and × from to , a recursive two-place relation < on , and distinguished constants such that
where indicates isomorphism and 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. The strategy for proving Tennenbaum's Theorem is to assume that there exists a recursive non-standard model of PA and then show that this leads to a contradiction. This may be achieved by constructing a non-recursive set S and then showing - under the assumption that such a recursive non-standard model exists - that S is recursive, leading to a contradiction. Such a non-recursive set S must involve non-standard elements and be constructible for any non-standard model of PA
- George Boolos, John P. Burgess, and Richard Jeffrey (2002) Computability and Logic, 4th ed. Cambridge University Press. ISBN 0-521-00758-5
- Richard Kaye (1991) Models of Peano arithmetic. Oxford University Press. ISBN 0-19-853213-X.
- "Tennenbaum's Theorem for Models of Arithmetic" by R. W. Kaye