ON THE EXISTENCE OF UNIVERSAL NUMBERINGS

The paper is devoted to research existence property of universal numberings for different computable families. A numbering α is reducible to a numbering β if there is computable function ƒ such that α = β ◦ ƒ.  A computable numbering α for some family S is universal if any computable numbering β for the family S is reducible to α. It is well known that the family of all computably enumerable (c.e.) sets has a computable universal numbering. In this paper, we study families of almost all c.e. sets, recursive sets, and almost all differences of c.e. sets, namely questions about the existence of universal numberings for given families. We proved that there is no universal numbering for the family of all recursive sets. For families of c.e. sets without an empty set or a finite number of finite sets, there still exists a universal numbering. However, for families of all c.e. sets without an infinite set, there is no universal numbering. Also, we proved that family ∑₂^-1 \ Β and the family ∑₁^-1 has no universal ∑₂^-1-computable numbering for any Β ∈ ∑₂^-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.