Computable covers for arithmetical collections of programming systems
https://doi.org/10.26907/2949-3919.2026.1.47-66
Abstract
We obtain sufficient conditions for the existence of non-acceptable covers (with respect to the reducibility of numberings) for classes of numberings computable in the arithmetical hierarchy. These conditions, among other things, imply that the class of all Friedberg computable numberings has a non-acceptable computable cover and allow us to clarify the question of possible cardinalities of Rogers quotient semilattices with respect to arithmetical ideals. We also prove that the ideal in the Rogers semilattice of the family of all unary partial recursive functions generated by the direct sums of infinite sequences of its Friedberg-atoms is a proper subideal of the ideal of all its non-greatest elements.
Keywords
Supporting agencies: This work was supported by the Science and Technology Fund of the Republic of Tatarstan grant for the implementation of fundamental and applied scientific research in scientific and educational organizations, enterprises and organizations of the real sector of the economy of the Republic of Tatarstan
About the Author
M. Kh. Faizrahmanov
Kazan Federal University, Volga Region Mathematical Center
Russian Federation
Russian Federation
Marat Khaidarovich Faizrahmanov
18 Kremlyovskaya str., Kazan 420008
References
1. S.A. Badaev, S.S. Goncharov, A. Sorbi, Completeness and universality of arithmetical numberings, in: Computability and models, Springer US, Boston, MA, 2003, 11–44. DOI: https://doi.org/10.1007/978-1-4615-0755-0_2
2. Yu.L. Ershov, Completely enumerated sets, Siberian Math. J. 10 (5), 773–784 (1969). DOI: https://doi.org/10.1007/BF00971653
3. Yu.L. Ershov, Theorie der numerierungen I, Z. Math. Logik Grundlagen Math. 19, 289–388 (1973) [in German]. DOI: https://doi.org/10.1002/malq.19730191901
4. Yu.L. Ershov, Theory of numberings, Nauka, M., 1977 [in Russian].
5. Yu.L. Ershov, Theory of numberings, in: E.R. Griffor (ed.), Handbook of computability theory (Stud. Logic Found. Math., 140), Amsterdam, Elsevier, 1999, 473–503. DOI: https://doi.org/10.1016/S0049-237X(99)80030-5
6. Yu.L. Ershov, Rogers semilattices of finite partially ordered sets, Algebra Logic 45 (1), 26–48 (2006). DOI: https://doi.org/10.1007/s10469-006-0004-9
7. M. Faizrahmanov, Embedding of the first nonconstructive ordinal into the Rogers semilattices of families of arithmetic sets, Siberian Math. J. 64 (4), 927–935 (2023). DOI: https://doi/org/10.1134/S0037446623040146
8. M. Faizrahmanov, Decomposition of Godel numberings into minimal numberings, J. Symb. Log. (published online, 2025). DOI: https://doi.org/10.1017/jsl.2025.10167
9. M. Faizrahmanov, Khutoretskii’s theorem for generalized computable families, Algebra Logic 58 (4), 256–365 (2019). DOI: https://doi.org/10.1007/s10469-019-09557-9
10. R.M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symb. Log. 23 (3), 309–316 (1958). DOI: https://doi.org/10.2307/2964290
11. S.S. Goncharov, A. Sorbi, Generalized computable numerations and nontrivial Rogers semilattices, Algebra Logic 36 (6), 359–369 (1997). DOI: https://doi.org/10.1007/bf02671553
12. K. Harris, η-representation of sets and degrees, J. Symb. Log. 73 (4), 1097–1121 (2008). DOI: https://doi.org/10.2178/jsl/1230396908
13. A.B. Khutoretskii, On nonprincipal enumerations, Algebra Logic 8 (6), 412–415 (1969). DOI: https://doi.org/10.1007/bf02219655
14. A.B. Khutoretskii, On the cardinality of the upper semilattice of computable enumerations, Algebra Logic 10 (5), 348–352 (1971). DOI: https://doi.org/10.1007/bf02219842
15. M. Kummer, A note on direct sums of Friedbergnumberings, J. Symb. Log. 54 (3), 1009–1010 (1989). DOI: https://doi.org/10.2307/2274760
16. A.H. Lachlan, A note on universal sets, J. Symb. Log. 31 (4), 574–574 (1966). DOI: https://doi.org/10.2307/2269692
17. S.S. Marchenkov, The computable enumerations of families of general recursive functions, Algebra Logic 11 (5), 326–336 (1972). DOI: https://doi.org/10.1007/bf02330746
18. S. Nodirov, M. Faizrahmanov, Some properties of classes of minimal numberings of arithmetical set families, Mathematics and Theoretical Computer Sciences 2 (1), 94–108 (2024) [in Russian]. DOI: https://doi.org/10.26907/2949-3919.2024.1.94-108
19. S.Y. Podzorov, Dual covers of the greatest element of the Rogers semilattice, Siberian Adv. Math. 15 (2), 104–114 (2005). URL: https://zbmath.org/?q=an:1095.03027
20. S.Y. Podzorov, Arithmetical D-degrees, Siberian Math. J. 49 (6), 1109–1123 (2008). DOI: https://doi.org/10.1007/s11202-008-0107-8
21. M.B. Pour-El, G¨odel numberings versus Friedberg numberings, Proc. AMS 15 (2), 252–256 (1964). DOI: https://doi.org/10.2307/2034045
22. J.S. Royer, A connotational theory of program structure, Springer-Verlag, Berlin, 1987.
23. B. Schinzel, On decomposition of Godelnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982). DOI: https://doi.org/10.2307/2273141
24. V.L. Selivanov, Index sets of quotient objects of the Post numeration, Algebra Logic 27 (3), 215–224 (1988). DOI: https://doi.org/10.1007/bf01978567
25. V.L. Selivanov, Precomplete numberings, J. Math. Sci. 256 (1), 96–124 (2021). DOI: https://doi.org/10.1007/s10958-021-05422-2
26. R.I. Soare, Turing computability. Theory and applications of computability, Springer-Verlag, Berlin, 2016. DOI: https://doi.org/10.1007/978-3-642-31933-4
27. S.A. Terwijn, Fixed point theorems in computability theory, in: Logics and type systems in theory and practice – essays dedicated to Herman Geuvers on the occasion of his 60th birthday, Springer, Cham, 2024, 214–224. DOI: https://doi.org/10.1007/978-3-031-61716-4_14
Review
For citations:
Faizrahmanov M.Kh. Computable covers for arithmetical collections of programming systems. Mathematics and Theoretical Computer Science. 2026;4(1):47-66. https://doi.org/10.26907/2949-3919.2026.1.47-66
Views:
53
JATS XML
Email this article 