An Undecidable Linear Order That Is $n$-Decidable for All $n$
John Chisholm, Michael F. Moses · Notre Dame Journal of Formal Logic · 1998
A linear order is $n$-decidable if its universe is $\mathbb{N}$ and the relations defined by $\Sigma_{n}$ formulas are uniformly computable. This means that there is a computable procedure which, when applied to a $\Sigma_{n}$ formula $\varphi(\bar{x})$ and a sequence $\bar{a}$ of elements of the linear order, will determine whether or not $\varphi(\bar{a})$ is true in the structure. A linear order is decidable if the relations defined by all formulas are uniformly computable. These definitions suggest two questions. Are there, for each $n$, $n$-decidable linear orders that are not $(n+1)$-decidable? Are there linear orders that are $n$-decidable for all $n$ but not decidable? The former was answered in the positive by Moses in 1993. Here we answer the latter, also positively.