A model $M$ is decidable if the set of all first-order formulas which are true in $M$ is a recursive set. And a model is $1$-decidable if the set of all existential formulas which are true in $M$ is a recursive set. This paper gives an example of a linear order which is $1$-decidable (in fact $n$-decidable for all $n$) but not decidable. As pointed out by Laurent Moret-Bailly in the comments, by this MO answer, the field $\mathbb{R}(t)$ is 1-decidable but not decidable.

My question is, are there any known examples of algebraic extensions of $\mathbb{Q}$ which are $1$-decidable but not decidable?

  • 7
    $\begingroup$ See this post. $\endgroup$ – Laurent Moret-Bailly Mar 14 at 16:41
  • 1
    $\begingroup$ Seems indeed to be a duplicate of Laurent's question: First order decidability of rings vs Diophantine decidability. The question asked for any ring with this property, but the accepted answer yields a field. $\endgroup$ – YCor Mar 14 at 17:51
  • $\begingroup$ @YCor Do you know of any infinite algebraic extensions of Q with that property? $\endgroup$ – Keshav Srinivasan Mar 14 at 18:17
  • $\begingroup$ I guess to make the question not formally a duplicate you could edit it to ask only about infinite algebraic extensions of $\mathbb Q$ (or fields whose elements can be enumerated, or something else that avoids the answers to Laurent's question). $\endgroup$ – Will Sawin Mar 15 at 2:03
  • $\begingroup$ @WillSawin OK. I edited my question as you suggested. $\endgroup$ – Keshav Srinivasan Mar 15 at 2:17

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.