Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.