Geodesic
Algorithmic independence of natural relations on computable linear orders
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 155 (2013) no. 3, pp. 80-90 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We study the dependence of various algorithmic relations on linear orders. We prove that successor relation, block relation, density relation, and limit from above and limit from below relations are algorithmically independent. We introduce new relations defined in a signature of linear order, such that they are not algorithmically independent, and study their properties.
Keywords: linear order, successor relation, block relation, density relation, limit from above relation, limit from below relation, algorithmic independence. 
@article{UZKU_2013_155_3_a8,
     author = {R. I. Bikmukhametov},
     title = {Algorithmic independence of natural relations on computable linear orders},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {80--90},
     year = {2013},
     volume = {155},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2013_155_3_a8/}
}
TY  - JOUR
AU  - R. I. Bikmukhametov
TI  - Algorithmic independence of natural relations on computable linear orders
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2013
SP  - 80
EP  - 90
VL  - 155
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2013_155_3_a8/
LA  - ru
ID  - UZKU_2013_155_3_a8
ER  - 
%0 Journal Article
%A R. I. Bikmukhametov
%T Algorithmic independence of natural relations on computable linear orders
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2013
%P 80-90
%V 155
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2013_155_3_a8/
%G ru
%F UZKU_2013_155_3_a8
R. I. Bikmukhametov. Algorithmic independence of natural relations on computable linear orders. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 155 (2013) no. 3, pp. 80-90. http://geodesic.mathdoc.fr/item/UZKU_2013_155_3_a8/

[1] Soar R. I., Vychislimo perechislimye mnozhestva i stepeni, Kazan. matem. o-vo, Kazan, 2000, 576 pp. | MR | Zbl

[2] Rosenstein J. G., Linear orderings, Acad. Press, N.Y., 1982, 487 pp. | MR | Zbl

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

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

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

[6] Downey R. G., Lempp S., Wu G., “On the complexity of the successivity relation in computable linear orderings”, J. Math. Logic, 10:1–2 (2010), 83–99 | DOI | MR | Zbl

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

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

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

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

[11] Downey R. G., “Computability theory and linear orderings”, Handbook of Recursive Mathematics, v. 2, Elsevier, Amsterdam, 1998, 823–976 | MR | Zbl