MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.