Some properties of classes of minimal numberings of arithmetical set families
https://doi.org/10.26907/2949-3919.2024.1.94-108
Abstract
We prove that for each u ⩾ 2 the class of all single-valued Σ0 ucomputable numberings of any infinite family of total functions is effectively infinite and the class of all its Σ0 u-1-computable numberings is generated by the downward closure with respect to the reducibility of the set of all infinite direct sums of uniformly Σ0 u-1-computable sequences of its single-valued numberings. It is established that if u > 2, then the class of all Σ0 u-computable numberings of any infinite family is generated by infinite direct sums of uniformly Σ0 u-computable and uniformly Σ0 u-minimal sequences of its numberings.
About the Authors
Sh. D. Nodirov
Karshi State University
Uzbekistan
Uzbekistan
Shohruh Dilmurodovich Nodirov
17 Kuchabag str., Karshi 180119
M. Kh. Faizrahmanov
Kazan Federal University, Volga Region Mathematical Center
Russian Federation
Russian Federation
Marat Khaidarovich Faizrahmanov
18 Kremlyovskaya str., Kazan 420008
References
1. Yu.L. Ershov, Theory of numberings, Nauka, M., 1977 [in Russian.].
2. 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
3. Yu.L. Ershov, Definability and computability (Siberian School of Algebra and Logic), Novosibirsk, Nauch. Kniga, M., Ekonomika, 2nd ed., 2000 [in Russian.].
4. 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
5. S.A. Badaev, S.S. Goncharov, Rogers semilattices of families of arithmetic sets, Algebra Logic 40 (5), 283–291 (2001). DOI: https://doi.org/10.1023/A:1012516217265
6. S.Yu. Podzorov, Local structure of Rogers semilattices of Σ0 n-computable numberings, Algebra Logic 44 (2), 82–94 (2005). DOI: https://doi.org/10.1007/s10469-005-0010-3
7. S.A. Badaev, S.S. Goncharov, A. Sorbi, Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy, Algebra Logic 45 (6), 361–370 (2006). DOI: https://doi.org/10.1007/s10469-006-0034-3
8. S.A. Badaev, S.S. Goncharov, Computability and numberings, in: S. B. Cooper (ed.) et al., New computational paradigms. Changing conceptions of what is computable, New York, Springer-Verlag, 19–34 (2008). DOI: https://doi.org/10.1007/978-0-387-68546-5_2
9. M.Kh. Faizrakhmanov, Khutoretskii’s theorem for generalized computable families, Algebra Logic 58 (4), 356–365 (2019). DOI: https://doi.org/10.1007/s10469-019-09557-9
10. S.A. Badaev, Minimal enumerations, Trudy Inst. Mat. SO RAN 25, 3–34 (1993) in Russian.. URL: https://www.mathnet.ru/eng/mt425
11. M.Kh. Faizrahmanov, Minimal generalized computable enumerations and high degrees, Sib. Math. J. 58 (3), 553–558 (2017). DOI: https://doi.org/10.1134/S0037446617030181
12. S.A. Badaev, A problem of S. S. Goncharov, Sib. Math. J. 32 (3), 532–534 (1991). DOI: https://doi.org/10.1007/BF00970493
13. S.S. Goncharov, A. Yakhnis, V. Yakhnis, Some effectively infinite classes of enumerations, Ann. Pure App. Log. 60 (3), 207–235 (1993). DOI: https://doi.org/10.1016/0168-0072(93)90076-P
14. B. Schinzel, On decomposition of G¨odelnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982). DOI: https://doi.org/10.2307/2273141
15. B. Schinzel, Complexity of decompositions of G¨odel numberings, Fundam. Inform. 5 (1), 15–33 (1982). DOI: https://doi.org/10.3233/FI-1982-5103
16. R.I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in mathematical logic. Springer-Verlag, Berlin, Heidelberg, New York, etc., 1987 URL: https://link.springer.com/book/9783540666813
17. J. Myhill, Creative sets, Z. Math. Logik und Grundlag. Math. 1 (2), 97–108 (1955). DOI: https://doi.org/10.1002/malq.19550010205
18. M.Kh. Faizrahmanov, Z. K. Shchedrikova, Effectively infinite classes of numberings and computable families of feals, Computability 12 (4), 339–350 (2023). DOI: https://doi.org/10.3233/COM-230461
19. M.Kh. Faizrahmanov, Extremal numberings and fixed point theorems, Math. Log. Q. 68 (4), 398–408 (2022). DOI: https://doi.org/10.1002/malq.202200035
20. M. Faizrahmanov, Fixed point theorems for minimal numberings, J. Log. Comput. (2023) DOI: https://doi.org/10.1093/logcom/exad074
21. M. Faizrahmanov, I. Kalimullin, The enumeration spectrum hierarchy of n-families, Math. Log. Quart. 64 (4–5), 420–426 (2016). DOI: https://doi.org/10.1002/malq.201500056
Review
For citations:
Nodirov Sh.D., Faizrahmanov M.Kh. Some properties of classes of minimal numberings of arithmetical set families. Mathematics and Theoretical Computer Science. 2024;2(1):94-108. (In Russ.) https://doi.org/10.26907/2949-3919.2024.1.94-108
Views:
263
Email this article 