Geodesic
Computable linear orders and the Ershov hierarchy
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2022), pp. 85-89.

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

This work corrects the inaccuracy of the authors' previous work. Namely, we correctly prove that there exists a computable linear order and a series of natural relations on it, the spectrum of which consist of exactly all $n$-c.e. degrees (for any natural number $n$).
Keywords: computable linear orders, the degree spectrum of relations, $n$-computable enumerable ($n$-c.e.) degrees. 
@article{IVM_2022_1_a7,
     author = {Y. A. Michailovskaya and A. N. Frolov},
     title = {Computable linear orders and the {Ershov} hierarchy},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {85--89},
     publisher = {mathdoc},
     number = {1},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2022_1_a7/}
}
TY  - JOUR
AU  - Y. A. Michailovskaya
AU  - A. N. Frolov
TI  - Computable linear orders and the Ershov hierarchy
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2022
SP  - 85
EP  - 89
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2022_1_a7/
LA  - ru
ID  - IVM_2022_1_a7
ER  - 
%0 Journal Article
%A Y. A. Michailovskaya
%A A. N. Frolov
%T Computable linear orders and the Ershov hierarchy
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2022
%P 85-89
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2022_1_a7/
%G ru
%F IVM_2022_1_a7
Y. A. Michailovskaya; A. N. Frolov. Computable linear orders and the Ershov hierarchy. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2022), pp. 85-89. http://geodesic.mathdoc.fr/item/IVM_2022_1_a7/

[1] Mikhailovskaya Ya. A., Frolov A. N., “Vychislimye lineinye poryadki i ierarkhiya Ershova”, Izv. vuzov. Matem., 2018, no. 1, 67–74 | MR | Zbl

[2] Moses M., “Recursive linear orders with recursive successivities”, Ann. Pure and Appl. Logic, 27 (1984), 253–264 | DOI | MR | Zbl

[3] Moses M., Recursive Properties of Isomophism Types, Ph.D. Thesis, Monash Univ., Clayton, Victoria, Australia, 1983 | MR | Zbl

[4] Moses M., “Relations intrinsically recursive in linear orders”, Z. Math. Logik Grundlag. Math., 32 (1986), 467–472 | DOI | MR | Zbl

[5] Chubb J., Frolov A., Harizanov V., “Degree spectra of the successor relation of computable linear orderings”, Archive Math. Logic, 48:1 (2009), 7–13 | DOI | MR | Zbl

[6] Frolov A. N., “Predstavleniya otnosheniya sosedstva vychislimogo lineinogo poryadka”, Izv. vuzov. Matem., 2010, no. 7, 73–85 | Zbl

[7] Frolov A. N., “Zametka o $\Delta^0_2$-spektrakh lineinykh poryadkov i spektrakh otnosheniya sosedstva na nikh”, Izv. vuzov. Matem., 2013, no. 11, 74–78 | Zbl

[8] Zubkov M. V., “Initial segments of computable linear orders with additional computable predicates”, Algebra and Logic, 48:5 (2009), 321–329 | DOI | MR | Zbl

[9] Turner W. P., Computable linear orders and Turing reductions, Master's Thesis, Univ. Connecticut, 2012

[10] Bikmukhametov R. I., “Nachalnye segmenty vychislimykh lineinykh poryadkov s vychislimymi estestvennymi otnosheniyami”, Izv. vuzov. Matem., 2016, no. 6, 15–26 | MR | Zbl

[11] Bikmukhametov R. I., “O $\Sigma^0_2$-nachalnykh segmentakh vychislimykh lineinykh poryadkov”, Algebra i logika, 53:3 (2014), 413–415 | MR | Zbl

[12] Bikmukhametov R. I., “Codings on Linear Orders and Algorithmic Independence of Natural Relations”, Lobachevskii J. Math., 35:4 (2014), 326–331 | DOI | MR

[13] Bikmukhametov R. I., “Algoritmicheskaya nezavisimost estestvennykh otnoshenii na vychislimykh lineinykh poryadkakh”, Uchen. zap. Kazan. un-ta. Ser. Fiz.-matem. nauki, 155:3 (2013), 80–90 | MR

[14] Bikmukhametov R. I., Eryashkin M. S., Frolov A. N., “Spektr otnosheniya bloka 1-vychislimykh lineinykh poryadkov”, Uchen. zap. Kazansk. un-ta. Ser. Fiz.-matem. nauki, 159, no. 3, 2017, 296–305 | MR

[15] Remmel J. B., “Recursively categorical linear orderings”, Proc. Amer. Math. Soc., 83 (1981), 387–391 | DOI | MR | Zbl

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

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

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

[19] Montalban A., “Notes on the jump of a structure”, Lect. Notes in Computer Sci., 5635, 2009, 372–378 | DOI | MR | Zbl

[20] Frolov A. N., “$\Delta_2^0$-copies of linear orderings”, Algebra and Logic, 45:3 (2006), 201–209 | DOI | MR | Zbl

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

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

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

[24] Frolov A. N., “Computable Presentability of Countable Linear Orders”, J. Math. Sci. (United States), 256:2 (2021), 199–233 | DOI | Zbl

[25] Alaev P. E., Frolov A. N., Thurber J., “Computability on linear orderings enriched with predicates”, Algebra and Logic, 48:5 (2009), 313–320 | DOI | MR | Zbl

[26] Hirschfeldt D. R., “Degree spectra of intrinsically c.e. relations”, J. Symbolic Logic, 66 (2001), 441–469 | DOI | MR | Zbl