Geodesic
Initial segments of computable linear orders with additional computable predicates
Algebra i logika, Tome 48 (2009) no. 5, pp. 564-579

Voir la notice de l'article provenant de la source Math-Net.Ru

We study computable linear orders with computable neighborhood and block predicates. In particular, it is proved that there exists a computable linear order with a computable neighborhood predicate, having a $\Pi^0_1$-initial segment which is isomorphic to no computable order with a computable neighborhood predicate. On the other hand, every $\Sigma^0_1$-initial segment of such an order has a computable copy enjoying a computable neighborhood predicate. Similar results are stated for computable linear orders with a computable block predicate replacing a neighborhood relation. Moreover, using the results obtained, we give a simpler proof for the Coles–Downey–Khoussainov theorem on the existence of a computable linear order with $\Pi^0_2$-initial segment, not having a computable copy.
Keywords: computability, recursiveness, linear order, initial segment. 
@article{AL_2009_48_5_a1,
     author = {M. V. Zubkov},
     title = {Initial segments of computable linear orders with additional computable predicates},
     journal = {Algebra i logika},
     pages = {564--579},
     publisher = {mathdoc},
     volume = {48},
     number = {5},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2009_48_5_a1/}
}
TY  - JOUR
AU  - M. V. Zubkov
TI  - Initial segments of computable linear orders with additional computable predicates
JO  - Algebra i logika
PY  - 2009
SP  - 564
EP  - 579
VL  - 48
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2009_48_5_a1/
LA  - ru
ID  - AL_2009_48_5_a1
ER  - 
%0 Journal Article
%A M. V. Zubkov
%T Initial segments of computable linear orders with additional computable predicates
%J Algebra i logika
%D 2009
%P 564-579
%V 48
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2009_48_5_a1/
%G ru
%F AL_2009_48_5_a1
M. V. Zubkov. Initial segments of computable linear orders with additional computable predicates. Algebra i logika, Tome 48 (2009) no. 5, pp. 564-579. http://geodesic.mathdoc.fr/item/AL_2009_48_5_a1/