# 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