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.
@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},
publisher = {mathdoc},
number = {6},
year = {2016},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/IVM_2016_6_a1/}
}
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/