I will give a presentation of Tennenbaum's theorem and
some variations on it here. All models considered here will
be countable models of at least *Models of Peano Arithmetic* (MR1098499).

A structure

**Theorem** **2.1** (**Tennenbaum, 1959**)

Let

It turns out that the choice of theory here is rather inessential.
Indeed Tennenbaum doesn't bother state which theory
is taken here, simply writing in his abstract provable

,
which presumably meant provable in

.
The theory

Tennenbaum's theorem improved on Mostowski's attempts at proving similar results. The key technique was a suitable choice of coding mechanism in arithmetic.

I will present a proof of Tennenbaum's theorem shortly. Before I do so, I would like to indicate at least one aspect of what it says: in some precise sense Tennenbaum's theorem is a model-theoretic version of the Gödel–Rosser incompleteness theorem.

**Definition** **2.2**

For a theory

**Theorem** **2.3** (**Rosser**)

There is no consistent extension

**Proof**

I shall sketch a proof assuming Tennenbaum's theorem
as stated earlier but for the set of

First, assume that witnessing

constants

The assumption that

a question that can be effectively decided by looking at

This means that the resulting model

We conclude that if

The Gödel–Rosser Theorem is well-known to be related to the following classical result of recursion theory, which we will use to prove Theorem 2.1.

**Theorem** **2.4**

There exist r.e. sets

To prove Theorem 2.1, we will follow Tennenbaum and separate
the problem into two subproblems: firstly of saying something about which
sets *coded* in a model

**Definition** **2.5**

Let

for some formula

In most cases, we may fix a particular formula

This happens in the particular case when

This formulation of

The following lemma is a straightforward application of induction.

**Lemma** **2.6** (**Robinson's overspill lemma**)

Let

The traditional approach to Tennenbaum's theorem now splits into two parts.

**Theorem** **2.7**

Let

**Proof**

Let

So by the overspill lemma there is some nonstandard

Now let

**Theorem** **2.8**

Let

**Proof**

Let

for the formula

It is natural to ask how far this argument can be pushed, replacing
the theory *et al* (MR0673785)
and is essentially the proof given in my
*Models of Peano Arithmetic* (MR1098499).
Note too that the subtheory mentioned earlier,

A much sharper result using essentially the same ideas was achieved by
Wilmers (MR780526) who showed the same result for the subtheory

Two other methods for showing

. This formula behaves as expected, and
in particular is correct

on standard formulas, in all models of

The second method goes back to Scott (MR0141595), and uses overspill again.
By an overspill argument, *Models of Peano Arithmetic* (MR1098499).)
This argument works very well in contexts where overspill is available,
and Wilmers (MR780526) shows that

In closing this section, I should mention two other strengthenings of Tennenbaum's
theorem that have been considered. The first is to start with a nonstandard
model *et al* (MR0673785)
and for *et al* (MR0673785))
and for nonstandard