matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университет10.26907/2949-3919.2024.1.94-108matatecs-41Research ArticleСТАТЬИНекоторые свойства классов минимальных нумераций семейств арифметических множествSome properties of classes of minimal numberings of arithmetical set familiesНодировШ. Д.NodirovSh. D.

Шохрух Дилмуродович Нодиров 

ул. Кучабаг, д. 17, г. Карши, 180119 

Shohruh Dilmurodovich Nodirov 

17 Kuchabag str., Karshi 180119 

shoh0809@mail.ruФайзрахмановМ. Х.FaizrahmanovM. Kh.

Марат Хайдарович Файзрахманов 

ул. Кремлевская, д. 18, г. Казань, 420008 

Marat Khaidarovich Faizrahmanov 

18 Kremlyovskaya str., Kazan 420008 

marat.faizrahmanov@gmail.comКаршинский государственный университетУзбекистанKarshi State UniversityUzbekistanКазанский (Приволжский) федеральный университет, Научно-образовательный математический центр ПФОРоссияKazan Federal University, Volga Region Mathematical CenterRussian Federation2024150420242194108Copyright © Нодиров Ш.Д., Файзрахманов М.Х., 20242024Нодиров Ш.Д., Файзрахманов М.Х.Nodirov S.D., Faizrahmanov M.K.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/41

Доказано, что для каждого u ⩾ 2 класс всех однозначных Σ0 uвычислимых нумераций любого бесконечного семейства всюду определенных функций эффективно бесконечен и класс всех его Σ0 u-1-вычислимых нумераций порождается замыканием вниз относительно сводимости множества всех бесконечных прямых сумм равномерно Σ0 u-1-вычислимых последовательностей его однозначных нумераций. Установлено, что если u > 2, то класс всех Σ0 u-вычислимых нумераций любого бесконечного семейства порождается бесконечными прямыми суммами равномерно Σ0 u-вычислимых и равномерно Σ0 uминимальных последовательностей его нумераций.

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.

вычислимая нумерацияоднозначная нумерацияминимальная нумерацияcomputable numberingsingle-valued numberingminimal numberingReferencesЮ.Л. Ершов, Теория нумераций, Наука, М., 1977.Yu.L. Ershov, Theory of numberings, Nauka, M., 1977 [in Russian.].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-5Yu.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Ю.Л. Ершов, Определимость и вычислимость (Сибирская школа алгебры и логики), Новосибирск, Науч. кн., М., Экономика, 2-е изд., испр. и доп., 2000.Yu.L. Ershov, Definability and computability (Siberian School of Algebra and Logic), Novosibirsk, Nauch. Kniga, M., Ekonomika, 2nd ed., 2000 [in Russian.].С.С. Гончаров, А. Сорби, Обобщенно-вычислимые нумерации и нетривиальные полурешетки Роджерса, Алгебра и логика 36 (6), 621–641 (1997). URL: http://mi.mathnet.ru/al2412S.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С.А. Бадаев, С.С. Гончаров, О полурешетках Роджерса семейств арифметических множеств, Алгебра и логика 40 (5), 507–522 (2001). URL: http://mi.mathnet.ru/al233S.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С.Ю. Подзоров, О локальном строении полурешёток Роджерса Σ0 n-вычислимых нумераций, Алгебра и логика 44 (2), 148–172 (2005). URL: http://mi.mathnet.ru/al99S.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С.А. Бадаев, С.С. Гончаров, А. Сорби, Типы изоморфизмов полурешёток Роджерса семейств из различных уровней арифметической иерархии, Алгебра и логика 45 (6), 637–654 (2006). URL: http://www.mathnet.ru/rus/al163S.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-3S.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_2S.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М.Х. Файзрахманов, О теореме Хуторецкого для обобщённо вычислимых семейств, Алгебра и логика 58 (4), 528–541 (2019). DOI: https://doi.org/10.33048/alglog.2019.58.408M.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С.А. Бадаев, Минимальные нумерации, Тр. Ин-та математики СО РАН 25, 3–34 (1993). URL: https://www.mathnet.ru/rus/mt425S.A. Badaev, Minimal enumerations, Trudy Inst. Mat. SO RAN 25, 3–34 (1993) in Russian.. URL: https://www.mathnet.ru/eng/mt425М.Х. Файзрахманов, Минимальные обобщенно вычислимые нумерации и высокие степени, Сиб. матем. журн. 58 (3), 710–716 (2017). DOI: https://doi.org/10.17377/smzh.2017.58.318M.Kh. Faizrahmanov, Minimal generalized computable enumerations and high degrees, Sib. Math. J. 58 (3), 553–558 (2017). DOI: https://doi.org/10.1134/S0037446617030181С.А. Бадаев, Об одной проблеме С.С. Гончарова, Сиб. матем. журн. 32 (3), 212–214 (1991). URL: https://www.mathnet.ru/rus/smj3338S.A. Badaev, A problem of S. S. Goncharov, Sib. Math. J. 32 (3), 532–534 (1991). DOI: https://doi.org/10.1007/BF00970493S.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-PS.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-PB. Schinzel, On decomposition of G¨odelnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982). DOI: https://doi.org/10.2307/2273141B. Schinzel, On decomposition of G¨odelnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982). DOI: https://doi.org/10.2307/2273141B. Schinzel, Complexity of decompositions of G¨odel numberings, Fundam. Inform. 5 (1), 15–33 (1982). DOI: https://doi.org/10.3233/FI-1982-5103B. Schinzel, Complexity of decompositions of G¨odel numberings, Fundam. Inform. 5 (1), 15–33 (1982). DOI: https://doi.org/10.3233/FI-1982-5103R.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/9783540666813R.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/9783540666813J. Myhill, Creative sets, Z. Math. Logik und Grundlag. Math. 1 (2), 97–108 (1955). DOI: https://doi.org/10.1002/malq.19550010205J. Myhill, Creative sets, Z. Math. Logik und Grundlag. Math. 1 (2), 97–108 (1955). DOI: https://doi.org/10.1002/malq.19550010205M.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-230461M.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-230461M.Kh. Faizrahmanov, Extremal numberings and fixed point theorems, Math. Log. Q. 68 (4), 398–408 (2022). DOI: https://doi.org/10.1002/malq.202200035M.Kh. Faizrahmanov, Extremal numberings and fixed point theorems, Math. Log. Q. 68 (4), 398–408 (2022). DOI: https://doi.org/10.1002/malq.202200035M. Faizrahmanov, Fixed point theorems for minimal numberings, J. Log. Comput. (2023) DOI: https://doi.org/10.1093/logcom/exad074M. Faizrahmanov, Fixed point theorems for minimal numberings, J. Log. Comput. (2023) DOI: https://doi.org/10.1093/logcom/exad074M. 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.201500056M. 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

The authors declare that there are no conflicts of interest present.