Two theorems on minimal generally-computable numberings

M. Kh. Faizrahmanov

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2023), pp. 28-35

Résumé

The paper proves that for any set $A$ that computes a non-computable computably enumerable set, any infinite $A$-computable family has an infinite number of pairwise nonequivalent minimal $A$-computable numberings. It is established that an arbitrary set $A\leqslant_T\emptyset '$ is low if and only if any infinite $A$-computable family with the greatest set under inclusion has an infinite number of pairwise nonequivalent positive $A$-computable numberings.

Bibliographie

[1] Uspenskii V.A., “Kolmogorov, kakim ya ego pomnyu”, Kolmogorov v vospominaniyakh uchenikov, Sost. A.N. Shiryaev, MTsNMO, M., 2006, 272–371 | MR

[2] Uspenskii V.A., “Neskolko zamechanii o perechislimykh mnozhestvakh”, Z. math. Log. und Grundl. Math., 3:12 (1957), 157–170 | DOI | Zbl

[3] Uspenskii V.A., Lektsii o vychislimykh funktsiyakh, Fizmatgiz, M., 1960

[4] Uspenskii V.A., “O svodimosti vychislimykh i potentsialno vychislimykh numeratsii”, Matem. zametki, 6:1 (1969), 3–9 | Zbl

[5] Maltsev A.I., “Konstruktivnye algebry, I”, Uspekhi matem. nauk, 16:3 (1961), 3–60 | MR | Zbl

[6] Ershov Yu.L., “Numeratsii semeistv obscherekursivnykh funktsii”, Sib. matem. zhurn., 8:5 (1967), 1015–1025

[7] Vyugin V.V., “O nekotorykh primerakh verkhnikh polureshetok vychislimykh numeratsii”, Algebra i logika, 12:3 (1973), 512–529

[8] Badaev S.A., “O pozitivnykh numeratsiyakh”, Sib. matem. zhurn., 18:3 (1977), 483–496 | MR | Zbl

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

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

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

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

[13] Vyugin V.V., “O minimalnykh numeratsiyakh vychislimykh klassov rekursivno-perechislimykh mnozhestv”, Dokl. AN SSSR, 212:2 (1973), 273–275 | Zbl

[14] Marchenkov S.S., “O suschestvovanii semeistv bez pozitivnykh numeratsii”, Matem. zametki, 13:4 (1973), 597–604 | Zbl

[15] Badaev S.A., “Minimalnye numeratsii”, Tr. In-ta matematiki SO RAN, 25 (1993), 3–34 | MR | Zbl

[16] Friedberg R.M., “Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication”, J. Symb. Log., 23:3 (1958), 309–316 | DOI | MR

[17] Goncharov S.S., Lempp S., Solomon D., “Fridbergovskie numeratsii semeistv $n$-vychislimo perechislimykh mnozhestv”, Algebra i logika, 41:2 (2002), 143–154 | MR | Zbl

[18] Goncharov S.S., “Semeistva s edinstvennoi pozitivnoi numeratsiei”, Vychisl. sistemy, 146 (1992), 96–104

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

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

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

[22] Soare R.I., Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in mathematical logic, Springer-Verlag, Berlin–Heidelberg–N.Y., etc., 1987 | DOI | MR

[23] Nies A., Computability and Randomness, Oxford Logic Guides, Oxford, 2009 | MR | Zbl

[24] Badaev S.A., Goncharov S.S., “On computable minimal enumerations”, Algebra, Proc. Third Int. Conf. on Algebra in memory of M.I. Kargopolov, Walter de Gruyter, Berlin–N.Y., 1995, 21–32 | MR

[25] Badaev S.A., Lempp S., “A decomposition of the Rogers semilattice of a family of d.c.e. sets”, J. Symb. Log., 74:2 (2009), 618–640 | DOI | MR | Zbl

[26] Goncharov S.S., “Vychislimye odnoznachnye numeratsii”, Algebra i logika, 19:5 (1980), 507–551 | MR

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

[28] Faizrakhmanov M.Kh., “Minimalnye obobschenno vychislimye numeratsii i vysokie stepeni”, Sib. matem. zhurn., 58:3 (2017), 710–716 | MR

[29] Faizrahmanov M.Kh., “Extremal numberings and fixed point theorems”, Math. Log. Quart., 68:4 (2022), 398–408 | DOI | MR