Geodesic
Boolean algebras realized by c.e. equivalence relations
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 848-855.

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

Let $E$ be a computably enumerable (c.e.) equivalence relation on the set of natural numbers $\omega$. We consider countable structures where basic functions are computable and respect $E$. If the corresponding quotient structure is a Boolean algebra $B$, then we say that the c.e. relation $E$ realizes $B$. In this paper we study connections between algorithmic properties of $E$ and algebraic properties of Boolean algebras realized by $E$. Also we compare these connections with the corresponding results for linear orders and groups realized by c.e. equivalence relations.
Keywords: computability theory, Boolean algebras, computably enumerable structures.
Mots-clés : equivalence relations 
@article{SEMR_2017_14_a23,
     author = {N. Bazhenov and M. Mustafa and F. Stephan and M. Yamaleev},
     title = {Boolean algebras realized by c.e. equivalence relations},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {848--855},
     publisher = {mathdoc},
     volume = {14},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2017_14_a23/}
}
TY  - JOUR
AU  - N. Bazhenov
AU  - M. Mustafa
AU  - F. Stephan
AU  - M. Yamaleev
TI  - Boolean algebras realized by c.e. equivalence relations
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2017
SP  - 848
EP  - 855
VL  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2017_14_a23/
LA  - en
ID  - SEMR_2017_14_a23
ER  - 
%0 Journal Article
%A N. Bazhenov
%A M. Mustafa
%A F. Stephan
%A M. Yamaleev
%T Boolean algebras realized by c.e. equivalence relations
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2017
%P 848-855
%V 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2017_14_a23/
%G en
%F SEMR_2017_14_a23
N. Bazhenov; M. Mustafa; F. Stephan; M. Yamaleev. Boolean algebras realized by c.e. equivalence relations. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 848-855. http://geodesic.mathdoc.fr/item/SEMR_2017_14_a23/

[1] P. S. Novikov, “On the algorithmic unsolvability of the word problem in group theory”, Proceedings of the Steklov Institute of Mathematics, 44, 1955, 1–143 (In Russian) | MR

[2] E. Noether, “Idealtheorie in Ringbereichen”, Mathematische Annalen, 83:1–2 (1921), 24–66 | DOI | MR | Zbl

[3] W. Baur, “Rekursive Algebren mit Kettenbedingungen”, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 20 (1974), 37–46 | DOI | MR | Zbl

[4] A. Gavruskin, S. Jain, B. Khoussainov, F. Stephan, “Graphs realized by r.e. equivalence relations”, Ann. Pure Appl. Logic, 165:7–8 (2014), 1263–1290 | DOI | MR | Zbl

[5] E. Fokina, B. Khoussainov, P. Semukhin, D. Turetsky, “Linear orders realized by c.e. equivalence relations”, J. Symb. Logic, 81:2 (2016), 463–482 | DOI | MR | Zbl

[6] S. S. Goncharov, Countable Boolean algebras and decidability, Consultants Bureau, New York, 1997 | MR

[7] Yu. L. Ershov, Theory of numberings, Nauka, M., 1977 (In Russian) | MR

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

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

[10] U. Andrews, S. Badaev, A. Sorbi, “A survey on universal computably enumerable equivalence relations”, Lect. Notes Comput. Sci., 10010, 2016, 418–451 | DOI | MR

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

[12] L. Feiner, “Hierarchies of Boolean algebras”, J. Symb. Log., 35:3 (1970), 365–374 | DOI | MR

[13] S. P. Odintsov, V. L. Selivanov, “The arithmetical hierarchy and ideals of enumerated Boolean algebras”, Siberian Math. J., 30:6 (1990), 952–960 | DOI | MR

[14] S. A. Badaev, “On weakly precomplete positive equivalences”, Siberian Math. J., 32:2 (1991), 321–323 | DOI | MR | Zbl

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

[16] R. I. Soare, Recursively enumerable sets and degrees, Springer, Berlin, 1987 | MR