On numberings for classes of families of total functions

M. Kh. Faizrahmanov

Matematičeskie trudy, Tome 25 (2022) no. 1, pp. 177-197.

Résumé

In the present article, we study computable numberings and the Rogers semilattices for classes of families of everywhere defined (total) computable functions. We prove that the isomorphism type of the Rogers semilattice for a finite class $\mathfrak{F}$ of computable families of total functions depends only on the order with respect to inclusion on the class $\mathfrak{F}$ itself and the class $C(\mathfrak{F})$ of the closures of its elements regarded as subsets of a Baire space. We obtain necessary and sufficient conditions for existence of universal numberings for finite classes of computable families of total functions. We also consider a question whether a class of families of total functions admitting a universal numbering is closed under the union of computable increasing sequences of its elements. For a computable class $\mathfrak{F}$ such that $C(\mathfrak{F})$ is finite, we prove that the Rogers semilattice is either trivial or infinite; moreover, in the latter case, this semilattice is not a lattice.

Bibliographie

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

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

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

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

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

[6] Kalimullin I.Sh., Puzarenko V.G., “O svodimosti na semeistvakh”, Algebra i logika, 48:1 (2009), 31–53 | MR | Zbl

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

[8] Selivanov V.L., “Dve teoremy o vychislimykh numeratsiyakh”, Algebra i logika, 15:4 (1976), 470–484 | MR | Zbl

[9] Faizrakhmanov M.Kh., “Universalnye vychislimye numeratsii konechnykh klassov semeistv totalnykh funktsii”, Izv. vuzov. Matem., 60:12 (2016), 96–100 | MR | Zbl

[10] Khutoretskii A.B., “O moschnosti verkhnei polureshetki vychislimykh numeratsii”, Algebra i logika, 10:5 (1971), 561–569 | MR

[11] Badaev S., Goncharov S., Sorbi A., “Completeness and Universality of Arithmetical Numberings”, Computability and Models, The University Series in Mathematics, Springer, Boston, 2003 | MR

[12] Cooper S.B., “Partial degrees and the density problem. Part 2: The enumeration degrees of the $\Sigma^0_2$ sets are dense”, J. Symbolic Logic, 49 (1984), 503–513 | DOI | MR | Zbl

[13] Faizrahmanov M., Kalimullin I., “The enumeration spectrum hierarchy of $n$-families”, Math. Log. Q, 62:4 (2016), 420–426 | DOI | MR | Zbl

[14] Faizrahmanov M., Kalimullin I., “The enumeration spectrum hierarchy of $\alpha$-families and Low$_{\alpha}$ degrees”, J. Univ. Comp. Sci., 22:7 (2016), 943–955 | MR

[15] Lachlan A.H., “Standard classes of recursively enumerable sets”, Z. Math. Logik Grundlagen Math., 10:1 (1964), 23–42 | DOI | MR | Zbl

[16] Odifreddi P., Classical recursion theory: The theory of functions and sets of natural number, v. 1, Elsevier, Amsterdam, 1992 | MR

[17] Soare R.I., Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer–Verlag, Berlin–Heidelberg–New York–London–Paris–Tokyo, 1987 | MR