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 Peano arithmetic (PA) can be recursive.

Recursive structures for PA

A structure $scriptstyle\; M$ in the language of PA is recursive if there are recursive functions + and &times; from $scriptstyle\; N\; imes\; N$ to $scriptstyle\; N$ a recursive two-place relation < on $scriptstyle\; N$, and distinguished constants $scriptstyle\; n\_0,n\_1$ such that

:

where $scriptstyle\; equiv$ indicates isomorphism and $scriptstyle\; 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.

tatement 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

References

* Boolos, George; Burgess, John P. and Jeffrey, Richard. 2002. Computability and Logic, Fourth Edition. Cambridge: Cambridge University Press. ISBN 0-521-00758-5
* Richard Kaye (1991). Models of Peano arithmetic. Oxford University Press. ISBN 0-19-853213-X.

External links

* "Tennenbaum's Theorem for Models of Arithmetic" by R. W. Kaye [http://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennenbaum]