Geodesic
A class of low linear orders having computable presentations
Algebra i logika, Tome 61 (2022) no. 5, pp. 552-570.

Voir la notice de l'article provenant de la source Math-Net.Ru

It is shown that any low linear order of the form $\mathcal{L}+\omega^*$, where $\mathcal{L}$ is some $\eta$-presentation, has a computable copy. This result contrasts with there being low $\eta$-presentations not having a computable copy.
Keywords: low linear order, $\eta$-presentation, computable linear order. 
@article{AL_2022_61_5_a2,
     author = {M. V. Zubkov},
     title = {A class of low linear orders having computable presentations},
     journal = {Algebra i logika},
     pages = {552--570},
     publisher = {mathdoc},
     volume = {61},
     number = {5},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2022_61_5_a2/}
}
TY  - JOUR
AU  - M. V. Zubkov
TI  - A class of low linear orders having computable presentations
JO  - Algebra i logika
PY  - 2022
SP  - 552
EP  - 570
VL  - 61
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2022_61_5_a2/
LA  - ru
ID  - AL_2022_61_5_a2
ER  - 
%0 Journal Article
%A M. V. Zubkov
%T A class of low linear orders having computable presentations
%J Algebra i logika
%D 2022
%P 552-570
%V 61
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2022_61_5_a2/
%G ru
%F AL_2022_61_5_a2
M. V. Zubkov. A class of low linear orders having computable presentations. Algebra i logika, Tome 61 (2022) no. 5, pp. 552-570. http://geodesic.mathdoc.fr/item/AL_2022_61_5_a2/

[1] L. Feiner, “Hierarchies of Boolean algebras”, J. Symb. Log., 35:3 (1970), 365–374 | DOI | MR

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

[3] L. Feiner, Orderings and Boolean algebras not isomorphic to recursive ones, Ph. D. Thesis, MIT, Cambridge, MA, 1967 http://hdl.handle.net/1721.1/60738

[4] C. G. Jockusch, jun., R. I. Soare, “Degrees of orderings not isomorphic to recursive linear orderings”, Ann. Pure Appl. Logic, 52:1/2 (1991), 39–64 | DOI | MR | Zbl

[5] R. G. Downey, M. F. Moses, “On choice sets and strongly non-trivial self-embeddings of recursive linear orders”, Z. Math. Logik Grundlagen Math., 35:3 (1989), 237–246 | DOI | MR | Zbl

[6] R. G. Downey, “Computability theory and linear orderings”, Handbook of recursive mathematics, v. 2, Stud. Logic Found. Math., 139, Recursive algebra, analysis and combinatorics, eds. Y. L. Ershov et al., Elsevier, Amsterdam, 1998, 823–976 | DOI | MR | Zbl

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

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

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

[10] M. V. Zubkov, “Dostatochnye usloviya suschestvovaniya $\mathbf{0}^{\prime}$-predelno monotonnykh funktsii dlya vychislimykh $\eta$-skhozhikh lineinykh poryadkov”, Sib. matem. zh., 58:1 (2017), 107–121 | MR | Zbl

[11] A. N. Frolov, “Vychislimaya predstavimost schetnykh lineinykh poryadkov”, Trudy seminara kafedry algebry i matematicheskoi logiki Kazanskogo (Privolzhskogo) federalnogo universiteta, Itogi nauki i tekhn. Ser. Sovrem. matem. i ee pril. Temat. obz., 158, VINITI RAN, M., 2018, 81–115 | MR

[12] A. N. Frolov, M. V. Zubkov, “The simplest low linear order with no computable copies”, J. Symb. Log. | DOI

[13] R. J. Coles, R. Downey, B. Khoussainov, “On initial segments of computable linear orders”, Order, 14:2 (1998), 107–124 | DOI | MR | Zbl

[14] M. V. Zubkov, “O nachalnykh segmentakh vychislimykh lineinykh poryadkov s dopolnitelnymi vychislimymi predikatami”, Algebra i logika, 48:5 (2009), 564–579 | MR | Zbl

[15] R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspect. Math. Log., Omega Series, Springer-Verlag, Berlin etc., 1987 ; R. I. Soar, Vychislimo perechislimye mnozhestva i stepeni. Izuchenie vychislimykh funktsii i vychislimo perechislimykh mnozhestv, Kazanskoe matem. ob-vo, Kazan, 2000 | DOI | MR

[16] J. G. Rosenstein, Linear orderings, Pure Appl. Math., 98, Academic Press, New York etc., 1982 | MR | Zbl

[17] M. V. Zubkov, A. N. Frolov, “Vychislimye lineinye poryadki i predelno monotonnye funktsii, v sb. Trudy seminara kafedry algebry i matematicheskoi logiki Kazanskogo (Privolzhskogo) federalnogo universiteta”, Itogi nauki i tekhn. Ser. Sovrem. matem. i ee pril. Temat. obz., 157, VINITI RAN, M., 2018, 70–105

[18] K. Harris, “$\eta$-Representation of sets and degrees”, J. Symb. Log., 73:4 (2008), 1097–1121 | DOI | MR | Zbl

[19] M. V. Zubkov, “Odna teorema o silno $\eta$-predstavimykh mnozhestvakh”, Izv. vuzov. Matem., 2009, no. 7, 77–81 | Zbl

[20] M. V. Zubkov, “Silno $\eta$-predstavimye stepeni i predelno monotonnye funktsii”, Algebra i logika, 50:4 (2011), 504–520 | MR | Zbl

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

[22] A. M. Kach, D. Turetsky, “Limitwise monotonic functions, sets and degrees on computable domains”, J. Symb. Log., 75:1 (2010), 131–154 | DOI | MR | Zbl

[23] R. G. Downey, A. M. Kach, D. Turetsky, “Limitwise monotonic functions and their applications”, Proc. 11th Asian logic conf. in honor of Prof. Chong Chitat on his 60th birthday (National Univ. Singapore, Singapore, June 22-27, 2009), eds. T. Arai et al., World Scientific, Hackensack, NJ, 2012, 59–85 | MR | Zbl