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