RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2016 Number 6, Pages 15–26 (Mi ivm9119)

This article is cited in 4 papers

Initial segments of computable linear orders with computable natural relations

R. I. Bikmukhametov

Kazan (Volga Region) Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia

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.

UDC: 510.532

Received: 17.10.2014
Revised: 19.01.2015


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2016, 60:6, 12–20

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024