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.

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
Full Text: DOI
[1] 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
[2] Ehrenfeucht, A., “An application of games to the completeness problem for formalized theories,” Fundamenta Mathematicæ , vol. 49 (1961), pp. 129–41. · Zbl 0096.24303
[3] 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
[4] 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
[5] 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
[6] 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
[7] 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
[8] 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.