Geodesic
Initial segments of computable linear orders with computable natural relations
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2016), pp. 15-26

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

We study the algorithmic complexity of natural relations on initial segments of computable linear orders. We prove that there exists a computable linear order with computable density relation such that its $\Pi^0_1$-initial segment has no computable presentation with computable density relation. We also prove that the same holds for right limit and left limit relations.
Keywords: linear orders, initial segments, density relation, right limit relation, left limit relation. 
R. I. Bikmukhametov. Initial segments of computable linear orders with computable natural relations. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2016), pp. 15-26. http://geodesic.mathdoc.fr/item/IVM_2016_6_a1/
@article{IVM_2016_6_a1,
     author = {R. I. Bikmukhametov},
     title = {Initial segments of computable linear orders with computable natural relations},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {15--26},
     year = {2016},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2016_6_a1/}
}
TY  - JOUR
AU  - R. I. Bikmukhametov
TI  - Initial segments of computable linear orders with computable natural relations
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2016
SP  - 15
EP  - 26
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/IVM_2016_6_a1/
LA  - ru
ID  - IVM_2016_6_a1
ER  - 
%0 Journal Article
%A R. I. Bikmukhametov
%T Initial segments of computable linear orders with computable natural relations
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2016
%P 15-26
%N 6
%U http://geodesic.mathdoc.fr/item/IVM_2016_6_a1/
%G ru
%F IVM_2016_6_a1

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

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

[3] Goncharov S. C., Dzgoev V. D., “Avtoustoichivost modelei”, Algebra i logika, 19:1 (1980), 45–58 | MR | Zbl

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

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

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

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

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

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

[10] Raw M. J. S., Complexity of automorphisms of recursive linear orders, Ph. D. Thesis, Univ. of Wisconsin-Madison, 1995 | MR | Zbl

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

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