Computable presentability of countable linear orders

A. N. Frolov

Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, Tome 158 (2018), pp. 81-115.

Résumé

The main goal of this paper is to study algorithmic properties of countable linear orders by constructing effective presentations of these structures on the set of natural numbers. In 1991, C. Jockusch and R. Soare constructed a low linear order without computable presentations. Before in 1989, R. Downey and M. Moses showed that each low discrete linear order has a computable copy. It is natural to ask for which order types of low presentations it is sufficient the existence of a computable presentation. This question (namely, research program) was stated by R. Downey in 1998: Describe the order property $P$ such that, for any low linear order $L$, $P(L)$ implies the existence of a computable presentation of $L$. In this paper, we give a detailed review of the main results in this direction. These results are mostly obtained by the author or in co-authorship.

Détail

Keywords: countable linear orders, computable structures, computable presentability, low degrees.

Bibliographie

[1] Alaev P., Terber Dzh., Frolov A., “Vychislimost na lineinykh poryadkakh, obogaschennykh predikatami”, Algebra i logika, 48:5 (2009), 549–563 | MR | Zbl

[2] Goncharov S. S., Ershov Yu. L., Konstruktivnye modeli., Nauchnaya kniga, Novosibirsk, 1999 | MR

[3] Zubkov M. V., Frolov A. N., “Vychislimye lineinye poryadki i predelno monotonnye funktsii”, Itogi nauki i tekhn. Ser. Sovr. mat. prilozh. Tematich. obzory, 157 (2018), 70–105

[4] Maltsev A. I., “Konstruktivnye algebry, I”, Usp. mat. nauk, 16:3 (99) (1961), 3–60 | MR | Zbl

[5] Maltsev A. I., “O rekursivnykh abelevykh gruppakh”, Dokl. AN SSSR, 146:5 (1962), 1009–1012 | Zbl

[6] Novikov P. S., “Ob algoritmicheskoi nerazreshimosti problemy tozhdestva”, Dokl. AN SSSR, 85:4 (1952), 709–712 | MR | Zbl

[7] Peretyatkin M. G., “Kazhdoe rekursivno perechislimoe rasshirenie teorii lineinykh poryadkov imeet konstruktivnuyu model”, Algebra i logika, 12:2 (1973), 211–219

[8] Pinus A. G., “Effektivnye lineinye poryadki”, Sib. mat. zh., 16 (1975), 956–962

[9] Soar R. I., Vychislimo perechislimye mnozhestva i stepeni., Kazan. mat. ob-vo, Kazan, 2000

[10] Frolov A. N., “$\Delta_2^0$ kopii lineinykh poryadkov”, Algebra i logika, 45:3 (2006), 354–370 | MR | Zbl

[11] Frolov A. N., “Lineinye poryadki nizkoi stepeni”, Sib. mat. zh., 51:5 (2010), 1147–1162 | MR | Zbl

[12] Khisamiev N. G., “Arifmeticheskaya ierarkhiya abelevykh grupp”, Sib. mat. zh., 29:6 (1988), 144–159 | MR

[13] Ash C. J., Knight J., “Computable structures and the hyperarithmetical hierarchy”, Stud. Logic Found. Math., 144 (2000), North-Holland, Amsterdam | MR

[14] Coles R. J., Downey R., Khoussainov B., “On initial segments of computable linear orders”, Order., 14 (1997/98), 107–124 | DOI | MR

[15] Downey R. G., “On presentations of algebraic structures”, Complexity, Logic, and Recursion Theory, eds. Sorbi A. (ed.)., Dekker, New York, 1997, 157–205 | MR | Zbl

[16] Downey R. G., “Computability theory and linear orders”, Stud. Logic Found. Math., 138 (1998) | MR

[17] Downey R. G., Jockusch C. G., “Every low Boolean algebra is isomorphic to a recursive one”, Proc. Am. Math. Soc., 122:3 (1994), 871–880 | DOI | MR | Zbl

[18] Downey R. G., Knight J. F., “Orderings with $\alpha$-th jump degree $0^{(\alpha)}$”, Proc. Am. Math. Soc., 114:2 (1992), 545–552 | MR | Zbl

[19] Downey R. G., Moses M. F., “On choice sets and strongly nontrivial self-embeddings of recursive linear orderings”, Z. Math. Logik Grund. Math., 35 (1989), 237–246 | DOI | MR | Zbl

[20] Downey R., Remmel J. B., Questions in computable algebra and combinatorics, Victoria Univ. of Wellington, Wellington, New Zealand, 1999 | MR

[21] Feiner L. J., Orderings and Boolean algebras not isomoprhic to recursive ones, Thesis, MIT, 1967 | MR

[22] Feiner L. J., “The strong homogeneity conjecture”, J. Symb. Logic, 35 (1970), 373–377 | MR

[23] Fellner S., Recursive and finite axiomatizability of linear orderings, Ph.D. Thesis, Rutgers Univ., New Brunswick, New Jersey, 1976 | MR

[24] Fröhlich A., Shepherdson J., “Effective procedure in field theory”, Philos. Trans. Ros. Soc. London, Ser. A., 248 (1959), 407–432 | MR

[25] Frolov A. N., “Low linear orderings”, J. Logic Comput., 22:4 (2012), 745–754 | DOI | MR | Zbl

[26] Frolov A., Zubkov M., “Increasing $\eta$-representable degrees”, Math. Logic Q., 55:6 (2009), 633–636 | DOI | MR | Zbl

[27] Frolov A., “Scattered linear orderings with no computable presentation”, Lobachevskii J. Math., 35:1 (2014), 19–22 | DOI | MR | Zbl

[28] Goncharov S. S., “Computability and computable models”, Mathematical Problems from Applied Logic. II. Logics for the XXIst Century, eds. Gabbay D. M., Goncharov S. S., Zakharyaschev M., eds., Springer, New York, 2007, 99–216 | MR | Zbl

[29] Jockusch C. G., Soare R. I., “Degrees of orderings not isomorphic to recursive linear orderings”, Ann. Pure Appl. Logic, 52 (1991), 39–61 | DOI | MR

[30] Kach A., Montalbán A., “Cuts of linear orders”, Order., 28 (2011), 593–600 | DOI | MR | Zbl

[31] Khisamiev N. G., “A criterion for constructivizability of a direct sum of cyclic $p$-groups”, Izv. Akad. Nauk Kaz. SSR Ser. Fiz.-Mat., 98:1 (1981), 51–55 | MR

[32] Montalbán A., “Notes on the jump of a structure”, Lect. Notes Comp. Sci., 5635 (2009), 372–378 | DOI | MR | Zbl

[33] Knight J. F., Stob M., “Computable Boolean algebras”, J. Symb. Logic, 65:4 (2000), 1605–1623 | DOI | MR | Zbl

[34] Rabin M. O., “Effective computability of winning strategies”, Contributions of the Theory of Games. Vol. 3, Princeton Univ. Press, Princeton, 1957, 147–157 | MR

[35] Rice H., “Recursive and recursively enumerable orders”, Trans. Am. Math. Soc., 83 (1956), 277–300 | DOI | MR | Zbl

[36] Rosenstein J. G., Linear orderings, Academic Press, New York, 1982 | MR | Zbl

[37] Soare R. I., “Constructive order types on cuts”, J. Symb. Logic, 34 (1969), 285–289 | DOI | MR | Zbl

[38] Thurber J., “Every low$_{2}$ Boolean algebra has a recursive copy”, Proc. Am. Math. Soc., 123:12 (1995), 3859–3866 | MR | Zbl

[39] Vaught R. L., “Sentences true in all constructive models”, J. Symb. Logic, 25:1 (1960), 39–58 | DOI | MR

[40] Watnick R., “A generalization of Tennenbaum's theorem on effectively finite linear orderings”, J. Symb. Logic, 49:2 (1984), 563–569 | DOI | MR | Zbl

[41] Young D. R., “Linear orderings under 1-1 reducibility”, J. Symb. Logic, 31 (1966), 70–85 | DOI | MR | Zbl