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/

[1] R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspect. Math. Log., Omega Series, Springer-Verlag, Berlin etc., 1987 ; R. I. Soar, Vychislimo perechislimye mnozhestva i stepeni. Izuchenie vychislimykh funktsii i vychislimo perechislimykh mnozhestv, Kazanskoe matem. ob-vo, Kazan, 2000 | MR | MR | Zbl

[2] R. O. Gandy, “General recursive functionals of finite type and hierarchies of functions”, Ann. Fac. Sci. Univ. Clermont-Ferrand, 35:4 (1967), 5–24 | MR

[3] J. Harrison, “Recursive pseudo-well orderings”, Trans. Am. Math. Soc., 131 (1968), 526–543 | DOI | MR | Zbl

[4] M. J. S. Raw, Complexity of automorphisms of recursive linear orders, Ph. D. Thesis, Univ. Wisconsin-Madison, 1995

[5] K. Ambos-Spies, S. B. Cooper, S. Lempp, “Initial segments of recursive linear orders”, Order, 14:2 (1998), 101–105 | DOI | MR | Zbl

[6] R. J. Coles, R. Downey, B. Khoussainov, “On initial segments of computable linear orders”, Order, 14:2 (1998), 107–124 | DOI | MR | Zbl

[7] N. G. Khisamiev, “Kriterii konstruktiviziruemosti pryamoi summy tsiklicheskikh $p$-grupp”, Izv. AN Kaz. SSR, ser. fiz.-mat., 98:1 (1981), 51–55 | MR