Tennenbaum's celebrated 1959 theorem (see here for a reference) is certainly one of the key theorems in mathematical logic. Not so much for its proof, but because it helps "isolating" $N$ as something very special: *it is the only countable model of Peano arithmetic which is recursive*.

But, does it?

Suppose I live inside any countable model $M$ of Peano: I think I am actually living in the standard natural numbers, and addition/multiplication are the standard ones (and so are all the recursive function, etc). So, it would seem that from the point of view of $M$, other PA-models are not recursive. To be a bit more precise, let me state this:

**Internalized Tennenbaum Theorem (ITT): Let $M$ be a countable model of Peano. Then, for any other countable model $N$ not isomorphic to $M$, $N$ is not recursive in $M$, ie it is not $\Delta_1$-definable in M.**

Question: Can ITT be proved in, say, ZFC? If not, what is the obstruction?

Post Scriptum.

Thanks to Emil Jerabek for his suggestion: rather than the original misleading name, Derived Tennenbaum, use Internal (or Internalized). The original name generated some confusion, see the comments of Francois Dorais, thus I decided to rename the question. The recursivity required is IN the model, not FROM the model.

6more comments