Geodesic
Positive preorders
Algebra i logika, Tome 57 (2018) no. 3, pp. 279-284.

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

We consider positive preorders, i.e., computably enumerable equivalences, endowed with the structure of a partial order between equivalence classes. On positive preorders, a computable reducibility relation and the corresponding notion of degree of a positive preorder are introduced in the natural way. It is proved that the degree of any positive preorder contains either exactly one computable isomorphism class or an infinite set of computable isomorphism classes.
Keywords: computably enumerable equivalence, computable reducibility, computable isomorphism classes. 
@article{AL_2018_57_3_a1,
     author = {D. K. Kabylzhanova},
     title = {Positive preorders},
     journal = {Algebra i logika},
     pages = {279--284},
     publisher = {mathdoc},
     volume = {57},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2018_57_3_a1/}
}
TY  - JOUR
AU  - D. K. Kabylzhanova
TI  - Positive preorders
JO  - Algebra i logika
PY  - 2018
SP  - 279
EP  - 284
VL  - 57
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2018_57_3_a1/
LA  - ru
ID  - AL_2018_57_3_a1
ER  - 
%0 Journal Article
%A D. K. Kabylzhanova
%T Positive preorders
%J Algebra i logika
%D 2018
%P 279-284
%V 57
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2018_57_3_a1/
%G ru
%F AL_2018_57_3_a1
D. K. Kabylzhanova. Positive preorders. Algebra i logika, Tome 57 (2018) no. 3, pp. 279-284. http://geodesic.mathdoc.fr/item/AL_2018_57_3_a1/

[1] Yu. L. Ershov, “Pozitivnye ekvivalentnosti”, Algebra i logika, 10:6 (1971), 620–650

[2] S. Gao, P. Gerdes, “Computably enumerable equivalence relations”, Stud. Log., 67:1 (2001), 27–59 | DOI | MR | Zbl

[3] U. Andrews, S. Lempp, J. S. Miller, K. M. Ng, L. S. Mauro, A. Sorbi, “Universal computably enumerable equivalence relations”, J. Symb. Log., 79:1 (2014), 60–88 | DOI | MR | Zbl

[4] A. Gavrushkin, B. Khoussainov, F. Stephan, “Reducibilities among equivalence relations induced by recursively enumerable structures”, Theor. Comput. Sci., 612 (2016), 137–152 | DOI | MR

[5] S. Badaev, A. Sorbi, “Weakly precomplete computably enumerable equivalence relations”, Math. Log. Q., 62:1/2 (2016), 111–127 | DOI | MR | Zbl

[6] N. Kh. Kasymov, B. M. Khusainov, “Pozitivnye ekvivalentnosti s konechnymi klassami i algebry nad nimi”, Sib. matem. zh., 33:5 (1992), 196–200 | MR | Zbl

[7] N. Kh. Kasymov, B. M. Khusainov, “Pozitivnye i negativnye numeratsii algebr”, Teoriya vychislimosti i yazyki spetsifikatsii, Vychisl. sist., 139, In-t matem. SO AN SSSR, Novosibirsk, 1991, 103–110 | Zbl

[8] C. P. Odintsov, V. L. Selivanov, “Arifmeticheskaya ierarkhiya i idealy numerovannykh bulevykh algebr”, Sib. matem. zh., 30:6 (1989), 140–149 | MR | Zbl

[9] E. B. Fokina, S. D. Friedman, “Equivalence relations on classes of computable structures”, Mathematical theory and computational practice, Proc. 5th conf. comput. Europe, CiE 2009 (Heidelberg, Germany, July 19–24, 2009), Lect. Notes Comput. Sci., 5635, eds. K. Ambos-Spies et al., Springer-Verlag, Berlin, 2009, 198–207 | MR

[10] S. D. Friedman, L. Motto Ros, “Analytic equivalence relations and bi-embeddability”, J. Symb. Log., 76:1 (2011), 243–266 | DOI | MR | Zbl