Tuesday, 26 September 2006

lo.logic - 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$?

No comments:

Post a Comment