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

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

We give the collection of relations on computable linear orders. For any natural number $n$, the degree spectrum of some such relation contains exactly all $n$-computable enumerable degrees. We also study interconnections of these relations among themselves.
Keywords: computable linear orders, the degree spectrum of relations, $n$-computable enumerable degrees. 
@article{IVM_2018_1_a7,
     author = {Ya. A. Mikhailovskaya 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 = {67--74},
     publisher = {mathdoc},
     number = {1},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2018_1_a7/}
}
TY  - JOUR
AU  - Ya. A. Mikhailovskaya
AU  - A. N. Frolov
TI  - Computable linear orders and the Ershov hierarchy
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2018
SP  - 67
EP  - 74
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2018_1_a7/
LA  - ru
ID  - IVM_2018_1_a7
ER  - 
%0 Journal Article
%A Ya. A. Mikhailovskaya
%A A. N. Frolov
%T Computable linear orders and the Ershov hierarchy
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2018
%P 67-74
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2018_1_a7/
%G ru
%F IVM_2018_1_a7
Ya. A. Mikhailovskaya; A. N. Frolov. Computable linear orders and the Ershov hierarchy. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2018), pp. 67-74. http://geodesic.mathdoc.fr/item/IVM_2018_1_a7/

[1] Soare R. I., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987 | MR

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

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

[4] Moses M., Recursive properties of isomophism types, Ph. D. Thesis, Monash Univ., Clayton, Victoria, Australia, 1983 | MR

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

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

[7] Montalban A., “Notes on the jump of a structure”, Mathematical theory and computational practice, 5th Conference on Computability in Europe, CiE, Lect. Notes in Comput. Sci., 5635, eds. K. Ambos-Spies, B. Löwe, W. Merkle, Springer-Verlag, Berlin, 2009, 372–378 | DOI | MR | Zbl

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

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

[10] Alaev P., Tërber Dzh., Frolov A., “Vychislimost na lineinykh algebrakh, obogaschennykh predikatami”, Algebra i logika, 48:5 (2009), 549–563 | MR | Zbl

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

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

[13] 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

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

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

[16] Bikmukhametov R. I., “Codings on linear orders and algorithmic independence of natural relations”, Lobachevskii J. Math., 35:4 (2014), 326–331 | DOI | MR

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

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

[19] Feiner L. J., Orderings and Boolean algebras not isomorphic to recursive ones, Ph. D. Thesis, MIT, Cambridge, MA, 1967