Tennenbaum's theorem

From Wikipedia, the free encyclopedia

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.

Contents

[edit] 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.

[edit] 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.

[edit] Proof

 Please help improve this section by expanding it.
Further information might be found on the talk page or at requests for expansion.


[edit] 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.

[edit] External links

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