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 × from $\scriptstyle N \times N$ to $\scriptstyle N$, a recursive two-place relation < on $\scriptstyle N$, and distinguished constants $\scriptstyle n_0,n_1$ such that

$(N,+,\times,<,n_{0},n_{1}) \equiv M, \,$

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.

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

References

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

External links

• "Tennenbaum's Theorem for Models of Arithmetic" by R. W. Kaye [1]