Geodesic
Computable embeddings for pairs of linear orders
Algebra i logika, Tome 60 (2021) no. 3, pp. 251-285.

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

We study computable embeddings for pairs of structures, i.e., for classes containing precisely two nonisomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a nontrivial degree structure. Our main result shows that $\{\omega \cdot k,\omega^\star \cdot k\}$ is computably embeddable in $\{\omega \cdot t, \omega^\star \cdot t\}$ iff $k$ divides $t$.
Keywords: computable embedding, enumeration operator, computable linear order. 
@article{AL_2021_60_3_a0,
     author = {N. A. Bazhenov and H. Ganchev and S. Vatev},
     title = {Computable embeddings for pairs of linear orders},
     journal = {Algebra i logika},
     pages = {251--285},
     publisher = {mathdoc},
     volume = {60},
     number = {3},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2021_60_3_a0/}
}
TY  - JOUR
AU  - N. A. Bazhenov
AU  - H. Ganchev
AU  - S. Vatev
TI  - Computable embeddings for pairs of linear orders
JO  - Algebra i logika
PY  - 2021
SP  - 251
EP  - 285
VL  - 60
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2021_60_3_a0/
LA  - ru
ID  - AL_2021_60_3_a0
ER  - 
%0 Journal Article
%A N. A. Bazhenov
%A H. Ganchev
%A S. Vatev
%T Computable embeddings for pairs of linear orders
%J Algebra i logika
%D 2021
%P 251-285
%V 60
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2021_60_3_a0/
%G ru
%F AL_2021_60_3_a0
N. A. Bazhenov; H. Ganchev; S. Vatev. Computable embeddings for pairs of linear orders. Algebra i logika, Tome 60 (2021) no. 3, pp. 251-285. http://geodesic.mathdoc.fr/item/AL_2021_60_3_a0/

[1] N. Bazhenov, H. Ganchev, S. Vatev, “Effective embeddings for pairs of structures”, Computing with foresight and industry, 15th conf. comput. Europe, CiE 2019 (Durham, UK, July 15–19, 2019), Lect. Notes Comput. Sci., 11558, eds. F. Manea et al., Springer, Cham, 2019, 84–95 | DOI | Zbl

[2] U. Kalvert, D. Kammins, Dzh. F. Nait, S. Miller, “Sravnenie klassov konechnykh struktur”, Algebra i logika, 43:6 (2004), 666–701

[3] J. Chisholm, J. F. Knight, S. Miller, “Computable embeddings and strongly minimal theories”, J. Symb. Log., 72:3 (2007), 1031–1040 | DOI | Zbl

[4] E. B. Fokina, J. F. Knight, A. Melnikov, S. M. Quinn, C. M. Safranski, “Classes of Ulm type and coding rank-homogeneous trees in other structures”, J. Symb. Log., 76:3 (2011), 846–869 | DOI | Zbl

[5] J. F. Knight, S. Miller, M. Vanden Boom, “Turing computable embeddings”, J. Symb. Log., 72:3 (2007), 901–918 | DOI | Zbl

[6] Yu. L. Ershov, V. G. Puzarenko, A. I. Stukachev, “${\mathbb {HF}}$-Computability”, Computability in context. Computation and logic in the real world, eds. S. B. Cooper et al., Imperial College Press, London, 2011, 169–242 | DOI | Zbl

[7] V. G. Puzarenko, “Ob odnoi svodimosti na dopustimykh mnozhestvakh”, Sib. matem. zh., 50:2 (2009), 415–429

[8] M. Harrison-Trainor, A. Melnikov, R. Miller, A. Montalbán, “Computable functors and effective interpretability”, J. Symb. Log., 82:1 (2017), 77–97 | DOI | Zbl

[9] R. Miller, B. Poonen, H. Schoutens, A. Shlapentokh, “A computable functor from graphs to fields”, J. Symb. Log., 83:1 (2018), 326–348 | DOI | Zbl

[10] D. Rossegger, “On functors enumerating structures”, Sib. elektron. matem. izv., 14 (2017), 690–702 http://semr.math.nsc.ru/v14/p690-702.pdf | Zbl

[11] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, A. M. Slinko, “Degree spectra and computable dimensions in algebraic structures”, Ann. Pure Appl. Logic, 115:1–3 (2002), 71–113 | DOI | Zbl

[12] R. Miller, “Isomorphism and classification for countable structures”, Computability, 8:2 (2019), 99–117 | DOI | Zbl

[13] H. Friedman, L. Stanley, “On Borel reducibility theory for classes of computable structures”, J. Symb. Log., 54:3 (1989), 894–914 | DOI | Zbl

[14] C. J. Ash, J. F. Knight, “Pairs of recursive structures”, Ann. Pure Appl. Logic, 46:3 (1990), 211–234 | DOI | Zbl

[15] C. J. Ash, J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Stud. Logic Found. Math., 144, Elsevier Sci. B.V., Amsterdam etc., 2000 | Zbl

[16] N. Bazhenov, “Autostability spectra for decidable structures”, Math. Structures Comput. Sci., 28:3 (2018), 392–411 | DOI

[17] S. Goncharov, V. Harizanov, J. Knight, C. McCoy, R. Miller, R. Solomon, “Enumerations in computable structure theory”, Ann. Pure Appl. Logic, 136:3 (2005), 219–246 | DOI | Zbl

[18] I. Sh. Kalimullin, “Computable embeddings of classes of structures under enumeration and Turing operators”, Lobachevskii J. Math., 39:1 (2018), 84–88 | DOI | Zbl

[19] S. Vatev, Kh. Ganchev, I. Sh. Kalimullin, “Vychislimaya vlozhimost klassov algebraicheskikh struktur s otnosheniem kongruentnosti”, Uchen. zap. Kazan. un-ta. Ser. Fiz.-matem. nauki, 160, no. 4, 2018, 731–737

[20] N. Bazhenov, E. Fokina, L. San Mauro, “Learning families of algebraic structures from informant”, Inf. Comput., 275 (2020), 104590, 18 pp. | DOI | Zbl

[21] M. de Brecht, A. Yamamoto, “Topological properties of concept spaces (full version)”, Inf. Comput., 208:4 (2010), 327–340 | DOI | Zbl

[22] J. C. Rosenstein, Linear orderings, Pure Appl. Math., 98, Academic Press, New York etc., 1982 | Zbl