Skip to main content
added 418 characters in body; added 47 characters in body
Source Link
Sidney Raffer
  • 6.2k
  • 1
  • 27
  • 42

Can anyone suggestThis is version 2 of a reasonquestion about the ultimate limits of Tennenbaum's Theorem. The attempt to believe or disbelieve find these limits by moving up the following assertion:

Thereinduction heirarchy, as in Wilmer's Theorem, seems somehow indecisive. I suggested that maybe there is a theoryTheory $T$ extendingextending 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$?

Can anyone suggest a reason to believe or disbelieve the following assertion:

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.

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

Source Link
Sidney Raffer
  • 6.2k
  • 1
  • 27
  • 42

Ultimate limits of Tennenbaum's Theorem

Can anyone suggest a reason to believe or disbelieve the following assertion:

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.