On universal numberings of generalized computable families
DOI:
https://doi.org/10.26577/JMMCS.2022.v113.i1.03Keywords:
Rogers semilattice, Ershov hierarchy, computable numbering, universal numbering, hyperimmune setAbstract
The paper investigates the existence of universal generalized computable numberings of different families of sets and total functions. It was known that for every set A such that ∅ 0 ≤T A, a finite family S of A-c.e. sets has an A-computable universal numbering if and only if S contains the least set under inclusion. This criterion is not true for infinite families. For any set A there is an infinite A-computable family of sets S without the least element under inclusion that has an A-computable universal numbering; moreover, the family S consist pairwise not intersect sets. If A is a hyperimmune set, then an A-computable family F of total functions which contains at least two elements has no A-computable universal numbering. And if degT (A) is hyperimmune-free, then every A-computable finite family of total functions has an A-computable universal numbering. In this paper for a hyperimmune-free oracle A we show that any infinite effectively discrete family of sets has an A-computable universal numbering. It is also proved that if family S contains all co-finite sets and does not contain at least one co-c.e. set, then this family has no Σ −1 2 -computable universal numbering.
References
[2] Badaev S. A., Goncharov S. S. "Theory of numberings: open problems", Computability Theory
and Its Applications Amer. Math. Soc., Providences, (2000); 23–38.
[3] Korolkov Yu. D. "Evaluating the Complexity of Index Sets for Families of General Recursive
Functions in the Arithmetic Hierarchy", Algebra and Logic, (2002); 41(2): 87–92.
[4] Soare R. I. "Recursively enumerable sets and degrees", Perspect. Math. Log., Omega Series,
Heidelberg a.o., Springer-Verlag, (1987).
[5] Ershov Yu. L. "A hierarchy of sets, I", Algebra and Logic, (1968); 7(1): 15–47.
[6] Goncharov S. S., Sorbi A. "Generalized computable numerations and nontrivial Rogers
semilattices", Algebra and Logic, (1997); 36(6): 359–369.
[7] Badaev S. A., Goncharov S. S. "Generalized computable universal numberings", Algebra and
Logic, (2014); 53(5): 355–364.
[8] Issakhov A. A. I "Hyperimmunity and A-computable universal numberings", AIP Conference
Proceddings, (2016); 22(3): 402.
[9] Faizrakhmanov M. Kh. "Universal generalized computable numberings and hyperimmunity",
Algebra and Logic, (2017); 56(4): 337–347.
[10] Issakhov A. A., Rakymzhankyzy F, Ostemirova U. "Infinite families of total functions with
principal numberings", Herald of the Kazakh-British technical university, (2021; 18(2):53–58.
[11] Miller Webb, Martin D. A. "The degrees of hyperimmune sets", Z. Math. Logik Grundlagen
Math., (1968); 14: 159–166.
[12] Carl G., Jokush Jr., Soare Robert I. "Π0
1
classes and degrees of theories", Trans. Amer. Math.
Soc., (1972); 173: 33–56.
[13] Badaev S. A., Goncharov S. Sorbi S., A. "Completeness and universality of arithmetical
numberings", Computability and models, New York, Kluwer Academic/Plenum Publishers,
(2003); 11–44.
[14] Ershov Yu. L. "Complete numerations with an infinite number of special elements", Algebra
and Logic, (1970); 9(6): 396–399.
[15] Podzorov S. Yu. "The limit property of the greatest element in the Rogers semilattice", Math.
Trudy, (2004); 7(2): 98–108.
[16] Rakymzhankyzy F, Kalmurzayev B. S., Bazhenov N. A., Issakhov A. A. "Generalized
computable numberings of effectively discrete families", Maltsev Readings, (2021); 72
