Geodesic
Minimal generalized computable numberings and families of positive preorders
Algebra i logika, Tome 61 (2022) no. 3, pp. 280-307.

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

We study $A$-computable numberings for various natural classes of sets. For an arbitrary oracle $A\geq_T \mathbf{0'}$, an example of an $A$-computable family $S$ is constructed in which each $A$-computable numbering of $S$ has a minimal cover, and at the same time, $S$ does not satisfy the sufficient conditions for the existence of minimal covers specified by S. A. Badaev and S. Yu. Podzorov in [Sib. Math. J., 43, No. 4, 616–622 (2002)]. It is proved that the family of all positive linear preorders has an $A$-computable numbering iff $A' \geq_T \mathbf{0}''$. We obtain a series of results on minimal $A$-computable numberings, in particular, Friedberg numberings and positive undecidable numberings.
Keywords: $A$-computable numbering, positive linear preorder, Rogers semilattice, Friedberg numbering, positive numbering, minimal cover. 
@article{AL_2022_61_3_a1,
     author = {F. Rakymzhankyzy and N. A. Bazhenov and A. A. Issakhov and B. S. Kalmurzayev},
     title = {Minimal generalized computable numberings and families of positive preorders},
     journal = {Algebra i logika},
     pages = {280--307},
     publisher = {mathdoc},
     volume = {61},
     number = {3},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2022_61_3_a1/}
}
TY  - JOUR
AU  - F. Rakymzhankyzy
AU  - N. A. Bazhenov
AU  - A. A. Issakhov
AU  - B. S. Kalmurzayev
TI  - Minimal generalized computable numberings and families of positive preorders
JO  - Algebra i logika
PY  - 2022
SP  - 280
EP  - 307
VL  - 61
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2022_61_3_a1/
LA  - ru
ID  - AL_2022_61_3_a1
ER  - 
%0 Journal Article
%A F. Rakymzhankyzy
%A N. A. Bazhenov
%A A. A. Issakhov
%A B. S. Kalmurzayev
%T Minimal generalized computable numberings and families of positive preorders
%J Algebra i logika
%D 2022
%P 280-307
%V 61
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2022_61_3_a1/
%G ru
%F AL_2022_61_3_a1
F. Rakymzhankyzy; N. A. Bazhenov; A. A. Issakhov; B. S. Kalmurzayev. Minimal generalized computable numberings and families of positive preorders. Algebra i logika, Tome 61 (2022) no. 3, pp. 280-307. http://geodesic.mathdoc.fr/item/AL_2022_61_3_a1/

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

[2] S. A. Badaev, S. S. Goncharov, “O polureshetkakh Rodzhersa semeistv arifmeticheskikh mnozhestv”, Algebra i logika, 40:5 (2001), 507–522 | MR | Zbl

[3] S. A. Badaev, S. Yu. Podzorov, “Minimalnye nakrytiya v polureshetkakh Rodzhersa $\Sigma^0_n$-vychislimykh numeratsii”, Sib. matem. zh., 43:4 (2002), 769–778 | MR | Zbl

[4] S. Yu. Podzorov, “Nachalnye segmenty v polureshetkakh Rodzhersa $\Sigma^0_n$-vychislimykh numeratsii”, Algebra i logika, 42:2 (2003), 211–226 | MR | Zbl

[5] S. Yu. Podzorov, “O predelnosti naibolshego elementa polureshetki Rodzhersa”, Matem. tr., 7:2 (2004), 98–108 | MR | Zbl

[6] S. Yu. Podzorov, “O lokalnom stroenii polureshetok Rodzhersa $\Sigma^0_n$-vychislimykh numeratsii”, Algebra i logika, 44:2 (2005), 148–172 | MR | Zbl

[7] S. A. Badaev, S. S. Goncharov, A. Corbi, “Tipy izomorfizmov polureshetok Rodzhersa semeistv iz razlichnykh urovnei arifmeticheskoi ierarkhii”, Algebra i logika, 45:6 (2006), 637–654 | MR | Zbl

[8] S. Yu. Podzorov, “Arifmeticheskie $m$-stepeni”, Sib. matem. zh., 49:6 (2008), 1391–1410 | MR | Zbl

[9] S. A. Badaev, S. S. Goncharov, “Obobschenno vychislimye universalnye numeratsii”, Algebra i logika, 53:5 (2014), 555–569 | MR

[10] A. A. Isakhov, “Idealy bez minimalnykh elementov v polureshetkakh Rodzhersa”, Algebra i logika, 54:3 (2015), 305–314 | MR

[11] M. Kh. Faizrakhmanov, “Universalnye obobschenno vychislimye numeratsii i giperimmunnost”, Algebra i logika, 56:4 (2017), 506–521 | MR | Zbl

[12] M. Kh. Faizrakhmanov, “O polureshetkakh Rodzhersa obobschenno vychislimykh numeratsii”, Sib. matem. zh., 58:6 (2017), 1418–1427 | MR

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

[14] 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

[15] 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

[16] S. Badaev, S. Goncharov, “Computability and 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

[17] B. S. Kalmurzaev, N. A. Bazhenov, M. A. Torebekova, “Ob indeksnykh mnozhestvakh dlya klassov pozitivnykh predporyadkov”, Algebra i logika, 61:1 (2022), 42–76 | MR | Zbl

[18] 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 | DOI | MR | MR

[19] W. Miller, D. A. Martin, “The degrees of hyperimmune sets”, Z. Math. Logik. Grundlagen Math., 14 (1968), 159–166 | DOI | MR | Zbl

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

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

[22] A. A. Issakhov, F. Rakymzhankyzy, U. Ostemirova, “Infinite families of total functions with principal numberings”, Herald Kazakh-British Tech. Univ., 18:2 (2021), 53–58 | DOI

[23] A. A. Issakhov, F. Rakymzhankyzy, “Friedberg numberings with a hyperimmune oracle”, Herald Kazakh-British Tech. Univ., 16:1 (2019), 68–72

[24] C. G. Jockusch, jun., “Degrees in which the recursive sets are uniformly recursive”, Can. J. Math., 24:6 (1972), 1092–1099 | DOI | MR | Zbl

[25] N. A. Bazhenov, B. S. Kalmurzaev, “Polureshetki Rodzhersa semeistv otnoshenii ekvivalentnosti v ierarkhii Ershova”, Sib. matem. zh., 60:2 (2019), 290–305 | MR | Zbl

[26] A. B. Khutoretskii, “Dve teoremy suschestvovaniya dlya vychislimykh numeratsii”, Algebra i logika, 8:4 (1969), 483–492 | MR