# zbMATH — the first resource for mathematics

An undecidable linear order that is $$n$$-decidable for all $$n$$. (English) Zbl 0966.03043
Summary: 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 (\overline{x})$$ and a sequence $$\overline{a}$$ of elements of the linear order, will determine whether or not $$\varphi (\overline{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 M. Moses [in: J. N. Crossley et al. (eds.), Logical methods. In honor of A. Nerode’s 60th birthday. Basel: Birkhäuser. Prog. Comput. Sci. Appl. Log. 12, 572-592 (1993; Zbl 0824.03020)]. Here we answer the latter, also positively.

##### MSC:
 03D45 Theory of numerations, effectively presented structures 06A05 Total orders 03D35 Undecidability and degrees of sets of sentences 03B25 Decidability of theories and sets of sentences
##### Keywords:
computable linear order; $$n$$-decidable linear orders
Full Text:
##### References:
  Downey, R., “Computability theory and linear orderings,” pp. 823–976 in Handbook of Recursive Mathematics , vol. 2, edited by Yu. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, and V. W. Marek, Elsevier, New York, 1998. · Zbl 0941.03045  Ehrenfeucht, A., “An application of games to the completeness problem for formalized theories,” Fundamenta Mathematicæ , vol. 49 (1961), pp. 129–41. · Zbl 0096.24303  Fraï”ssé, R., “Sur quelques classifications des systèmes de relations,” Publications in Science and Universal Algebra , series A, vol. 1 (1954), pp. 35–182. · Zbl 0068.24302  Fröhlich, A., and J. C. Shepherdson, “Effective procedures in field theory,” Philosophical Transactions of the Royal Society of London , series A, vol. 248 (1955), pp. 407–32. JSTOR: · Zbl 0070.03502  Moses, M., “Relations intrinsically recursive in linear orders,” Zeitschrift für mathematische Logik und Grundlagen der Mathematik , vol. 32 (1986), pp. 467–72. · Zbl 0596.03038  Moses, M., “$$n$$–Recursive linear orders without $$(n+1)$$-recursive copies,” pp. 572–92 in Logical Methods: in Honor of Anil Nerode’s Sixtieth Birthday , edited by J. N. Crossley, J. B. Remmel, R. A. Shore, and M. E. Sweedler, Birkhäuser, Boston, 1993. · Zbl 0824.03020  Rabin, M., “Computable algebra, general theory and theory of computable fields,” Transactions of the American Mathematical Society , vol. 95 (1960), pp. 341–60. · Zbl 0156.01201  Rosenstein, J. G., Linear Orderings , Academic Press, New York, 1982. · Zbl 0488.04002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.