Initial segments of computable linear orders with computable natural relations
R. I. Bikmukhametov · Russian Mathematics · 2016
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 Π 1 0 -initial segment has no computable presentation with a computable density relation. We also prove that the same holds for a right limit and a left limit relations.