This seems like a question I should know the answer to, but I don't; and I can't find an answer online.

Usually the way we prove that a theory of arithmetic (Presburger, Skolem, . . .) is decidable is via quantifier elimination. I'm curious about whether there are examples of (reasonably natural) theories of arithmetic which are decidable, but not even model complete (ideally, whose quantifier hierarchy never collapses).

Context: I've shown that a certain second-order theory, built off a first-order subtheory $T$ of $PA$, is non-set-theoretically absolute in a specific way. But currently, the only way I know how to do this is via an undecidable $T$. Since decidability isn't actually part of the problem I'm approaching, it seems like I should be able to make do with a decidable $T$; but the obstacle I'm running into is that I need $\mathbb{N}$ (as a model of this theory) to have a definable, non-existentially-definable subset.

I've used the complexity theory tag, even though this isn't directly a complexity-theoretic question, since I suspect an affirmative answer will be related to some complexity-theoretic concerns.

  • $\begingroup$ I might be missing something entirely or this might be exactly what you are not looking for, but if we replace $+$ in Presburger arithmetic with a trinary relation symbol ($\gamma(x,y,z)$ which holds iff $x + y = z$) should remain decidable and should not be model complete. However, If you are asking for extensions of $(\mathbb{N}; +)$, I have bupkis. $\endgroup$ – Kyle Dec 24 '16 at 3:59
  • $\begingroup$ @KyleGannon: And I have learnt a new word! $\endgroup$ – user21820 Dec 24 '16 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.