# Ultimate limits of Tennenbaum's Theorem

This is version 2 of a question about the ultimate limits of Tennenbaum's Theorem. The attempt to find these limits by moving up the induction heirarchy, as in Wilmer's Theorem, seems somehow indecisive. I suggested that maybe there is a Theory $T$ extending open induction such that

1) $T$ has a recursively presentable nonstandard model.

2) If the sentence $\phi$ is not provable from $T$, then $T+\phi$ has no recursively presentable nonstandard model.

François G. Dorais immediately replied that this just amounts to $T$ being complete.

So... What about asking for the maximum $n$ such that the theory of all true (in the integers) all-2 sentences with n existential quantifiers has a recursive nonstandard model? What is known about this? Is it known that $n<2$?

-

This is equivalent to saying that $T$ is complete. Let $M$ be a recursively presentable model of $T$. If $T$ is not complete, then we can find $\phi$ which is not provable from $T$ but is true in $M$. Of course, $M$ is then a recursively presentable model of $T+\phi$. If $T$ is complete then $T+\phi$ has no model at all if $\phi$ is not provable from $T$. So the complete theory of a recursively presentable model of open induction will do.