Geodesic
Weakly precomplete equivalence relations in the Ershov hierarchy
Algebra i logika, Tome 58 (2019) no. 3, pp. 297-319.

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

We study the computable reducibility $\leq_c$ for equivalence relations in the Ershov hierarchy. For an arbitrary notation $a$ for a nonzero computable ordinal, it is stated that there exist a $\Pi^{-1}_a$-universal equivalence relation and a weakly precomplete $\Sigma^{-1}_a$-universal equivalence relation. We prove that for any $\Sigma^{-1}_a$ equivalence relation $E$, there is a weakly precomplete $\Sigma^{-1}_a$ equivalence relation $F$ such that $E\leq_c F$. For finite levels $\Sigma^{-1}_m$ in the Ershov hierarchy at which $m=4k+1$ or $m=4k+2$, it is shown that there exist infinitely many $\leq_c$-degrees containing weakly precomplete, proper $\Sigma^{-1}_m$ equivalence relations.
Keywords: Ershov hierarchy, equivalence relation, computable reducibility, universal equivalence relation, weakly precomplete equivalence relation. 
@article{AL_2019_58_3_a0,
     author = {N. A. Bazhenov and B. S. Kalmurzaev},
     title = {Weakly precomplete equivalence relations in the {Ershov} hierarchy},
     journal = {Algebra i logika},
     pages = {297--319},
     publisher = {mathdoc},
     volume = {58},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2019_58_3_a0/}
}
TY  - JOUR
AU  - N. A. Bazhenov
AU  - B. S. Kalmurzaev
TI  - Weakly precomplete equivalence relations in the Ershov hierarchy
JO  - Algebra i logika
PY  - 2019
SP  - 297
EP  - 319
VL  - 58
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2019_58_3_a0/
LA  - ru
ID  - AL_2019_58_3_a0
ER  - 
%0 Journal Article
%A N. A. Bazhenov
%A B. S. Kalmurzaev
%T Weakly precomplete equivalence relations in the Ershov hierarchy
%J Algebra i logika
%D 2019
%P 297-319
%V 58
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2019_58_3_a0/
%G ru
%F AL_2019_58_3_a0
N. A. Bazhenov; B. S. Kalmurzaev. Weakly precomplete equivalence relations in the Ershov hierarchy. Algebra i logika, Tome 58 (2019) no. 3, pp. 297-319. http://geodesic.mathdoc.fr/item/AL_2019_58_3_a0/

[1] Yu. L. Eršov, “Theorie der Numerierungen. I”, Z. Math. Logik Grundl. Math., 19:4 (1973), 289–388 | MR

[2] Yu. L. Eršov, “Theorie der Numerierungen. II”, Z. Math. Logik Grundl. Math., 21:6 (1975), 473–584 | MR | Zbl

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

[4] A. I. Maltsev, “Polno numerovannye mnozhestva”, Algebra i logika, 2:2 (1963), 4–29 | MR | Zbl

[5] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977 | MR

[6] C. Bernardi, A. Sorbi, “Classifying positive equivalence relations”, J. Symb. Log., 48:3 (1983), 529–538 | DOI | MR | Zbl

[7] A. H. Lachlan, “A note on positive equivalence relations”, Z. Math. Logik Grundlagen Math., 33 (1987), 43–46 | DOI | MR | Zbl

[8] U. Andrews, S. Badaev, A. Sorbi, “A survey on universal computably enumerable equivalence relations”, Computability and complexity, Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday, Lect. Notes Comput. Sci., 10010, eds. A. Day et al., Springer, Cham, 2017, 418–451 | DOI | MR | Zbl

[9] S. A. Badaev, “O slabo predpolnykh pozitivnykh ekvivalentnostyakh”, Sib. matem. zh., 32:2 (1991), 166–169 | MR | Zbl

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

[11] N. A. Bazhenov, B. S. Kalmurzaev, “O temnykh vychislimo perechislimykh otnosheniyakh ekvivalentnosti”, Sib. matem. zh., 59:1 (2018), 29–40 | MR | Zbl

[12] K. M. Ng, H. Yu, “On the degree structure of equivalence relations under computable reducibility”, Notre Dame J. Form. Log., 2018 (to appear) | MR

[13] U. Andrews, A. Sorbi, Joins and meets in the structure of Ceers, 2018, arXiv: 1802.09249 | MR

[14] U. Andrews, A. Sorbi, “Jumps of computably enumerable equivalence relations”, Ann. Pure Appl. Logic, 169:3 (2018), 243–259 | DOI | MR | Zbl

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

[16] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv. I”, Algebra i logika, 7:1 (1968), 47–74 | MR | Zbl

[17] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv. II”, Algebra i logika, 7:4 (1968), 15–47 | MR | Zbl

[18] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv. III”, Algebra i logika, 9:1 (1970), 34–51 | MR

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

[20] Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

[21] S. S. Goncharov, A. Sorbi, “Obobschenno vychislimye numeratsii i netrivialnye polureshetki Rodzhersa”, Algebra i logika, 36:6 (1997), 621–641 | MR | Zbl

[22] S. Badaev, S. Goncharov, “Computability, numberings”, New computational paradigms. Changing conceptions of what is computable, eds. S. B. Cooper et al., Springer-Verlag, New York, NY, 2008, 19–34 | MR | Zbl

[23] S. A. Badaev, S. S. Goncharov, “Theory of numberings: open problems”, Computability theory and its applications, Contemp. Math., 257, eds. P. Cholak et al., Am. Math. Soc., Providence, RI, 2000, 23–38 | DOI | MR | Zbl

[24] Yu. L. Ershov, “Theory of numberings”, Handbook of computability theory, Stud. Logic Found. Math., 140, ed. E. R. Griffor, Elsevier, Amsterdam, 1999, 473–503 | DOI | MR | Zbl

[25] S. Ospichev, “Computable family of $\Sigma^{-1}_a$-sets without Friedberg numberings”, CiE 2010, 6th Conf. Comput. Europe (Ponta Delgada, Univ. Azores), eds. F. Ferreira et al., 2010, 311–315

[26] E. Ianovski, R. Miller, K. M. Ng, A. Nies, “Complexity of equivalence relations and preorders from computability theory”, J. Symb. Log., 79:3 (2014), 859–881 | DOI | MR | Zbl

[27] V. L. Selivanov, “Ob ierarkhii Ershova”, Sib. matem. zh., 26:1 (1985), 134–149 | MR | Zbl