Abstract:
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.