4
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 7
    $\begingroup$ See this post. $\endgroup$
    – Laurent Moret-Bailly
    Commented Mar 14, 2021 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
    Commented Mar 14, 2021 at 17:51
  • $\begingroup$ @YCor Do you know of any infinite algebraic extensions of Q with that property? $\endgroup$
    – Keshav Srinivasan
    Commented Mar 14, 2021 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
    Commented Mar 15, 2021 at 2:03
  • $\begingroup$ @WillSawin OK. I edited my question as you suggested. $\endgroup$
    – Keshav Srinivasan
    Commented Mar 15, 2021 at 2:17

0

Reset to default

You must log in to answer this question.