О СУЩЕСТВОВАНИИ УНИВЕРСАЛЬНЫХ НУМЕРАЦИЙ

Данная статья посвящена исследованию свойства существования универсальных нумераций для различных семейств. Говорят, что нумерация α сводится к нумерации β, если существует вычислимая функция ƒ такая, что α = β ◦ ƒ. Вычислимая нумерация α для некоторого семейства S универсальна, если любая вычислимая нумерация β для семейства S сводится к α. Хорошо известно, что семейство всех вычислимо перечислимых (в.п.) множеств имеет вычислимую универсальную нумерацию. В данной работе мы изучаем семейства почти всех в.п. множеств, рекурсивные множества и почти все разности в.п. множеств, а именно вопросы о существовании универсальных нумераций для данных семейств. Мы доказали, что для семейства всех рекурсивных множеств не существует универсальной нумерации. Также для семейств в.п. множества без пустого элемента, без конечного числа конечных множеств, все еще есть универсальная нумерация. Что касается семейств всех в.п. множества без бесконечного множества, то в этом случае универсальной нумерации не будет. Также мы доказываем, что семейство ∑₂^-1 \ Β и семейство ∑₁^-1 не имеют универсальной ∑₂^-1-вычислимой нумерации для любой  Β ∈ ∑₂^-1.

1. Yu. L. Ershov. (1977) Theory of Numerations, Nauka, Moscow. (In Russian)

2. Badaev S.A., Goncharov S.S. Theory of numberings: open problems. // Computability Theory and Its Applications, Amer. Math. Soc., Providences, 2000, pp. 23–38.

3. Friedberg, R.M. Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication. J. Symb. Log. 23, 309–316 (1958)/

4. Badaev S.A. On minimal enumerations, Siberian Adv. Math., 1992, v. 2, no. 1, pp. 1–30.

5. Badaev S.A. On cardinality of semilattices of numberings of non-discrete families, Sib. Math. J., 1993, v. 34, no. 5, pp. 795–800.

6. Badaev S.A. Minimal numberings of positively computable families/ Algebra and Logic, 1994, v. 33, no. 2, pp. 131–141.

7. Goncharov S.S., Badaev S.A. Families with one-element Rogers semi-lattice. Algebra and Logic, 1998, v. 37, no. 1, pp. 21–34.

8. Khutoretsky A.B. Two existence theorems for computable numerations. Algebra i Logika, 1969, v. 8, no. 4, pp. 484–492. (In Russian).

9. Khutoretsky A.B. On the cardinality of the upper semilattice of computable numberings, Algebra and Logic, 1971, v. 10, no. 5, pp. 348–352.

10. Rogers H. Godel numberings of partial computable functions. J. Symbolic Logic, 1958, v. 23, no. 3, pp. 49–57.

11. Selivanov V.L. Enumerations of families of general recursive functions. Algebra and Logic, 1976, v. 15, no. 2, pp. 128–141.

12. Selivanov V.L. Two theorems on computable enumerations. Algebra and Logic, 1976, v. 15, no. 4, pp. 297–306.

13. Badaev S.A., Goncharov S.S., Sorbi.A "Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy. Algebra and Logic, 45:6 (2006), 361–370.

14. Goncharov S.S. and Sorbi A. Generalized computable numerations and nontrivial Rogers semilattices. Algebra and Logic, 36, no. 6, 359–369 (1997).

15. Abeshev K.Sh. On the existence of universal numberings for finite families of d.c.e. sets, Math. Log. Quart. 60, no. 3, 161–167 (2014).

16. Badaev S.A., Lempp S. A decomposition of the Rogers semilattice of a family of d.c.e. sets, The Journal of Symbolic Logic, v. 74, no 2, 2009.

17. I. Herbert, S. Jain, S. Lempp, M. Mustafa, and F. Stephan. Reductions between types of numberings, Ann. Pure Appl. Log., 170, no. 12 (2019), article 102716, pp. 1–25.

18. Abeshev K.Sh., Badaev S.A., Mustafa M. Families without minimal numberings, Algebra and Logic, v. 53, no 4, 2014.

19. Badaev S.A., Kalmurzayev B.S., Mukash N., Mustafa M. One-element Rogers semilattices in the Ershov hierarchy, Algebra and Logic, v. 60, no 4, 2021.

20. Badaev S.A., Mustafa M., Sorbi A. Friedberg numberings in the Ershov hierarchy, Arch. Math. Logic, v. 54, 2015.

21. Badaev S.A., Mustafa M., Sorbi A. Rogers semilattices of families of two embedded sets in the Ershov hierarchy, Mathematical Logic Quarterly, v. 58, no 4–5, 2012.

22. Badaev S.A. and Talasbaeva Zh.T. Computable numberings in the hierarchy of Ershov, Mathematical Logic in Asia, S. S. Goncharov (Ed.), World Scientific, NJ, 17–30 (2006).

23. Kalmurzayev B.S. Embeddability of the semilattice $L_m^0$ in Rogers semilattices, Algebra and Logic, v. 55, no 3, 2016.

24. Mustafa M., Sorbi A. Positive undecidable numberings in the Ershov hierarchy, Algebra and Logic, v. 50, no 6, 2012.

25. Ospichev S.S. Properties of numberings in various levels of the Ershov hierarchy, Journal of Mathematical Sciences, v. 188, no 4, 2013.

26. Ospichev S.S. Friedberg numberings in the Ershov hierarchy, Algebra and Logic, v. 54, no 4, 2015.

27. Odifreddi P. Classical Recursion Theory, Elsevier, Amsterdam, 1989.