Об универсальных нумерациях обобщенно вычислимых семейств
DOI:
https://doi.org/10.26577/JMMCS.2022.v113.i1.03Ключевые слова:
полурешётка Роджреса, иерархия Ершова, вычислимая нумерация, универсальная нумерация, гипериммунное множествоАннотация
В работе исследуется вопросы существования универсальных обобщенновычислимых нумерации различных семейтв множеств и всюду определенных функций. Было известно, что для любого множество A такого, что ∅ 0 ≤T A, конечное семейство A -в.п. множеств S имеет A -вычислимую универсальную нумерацию тогда и только тогда, когда S содержит наименьшее по включению множество. Данный критерий не верно для бесконечных семейств. Для любого множества A существует бесконечное A-вычислимое семейство множеств S без наименьшего по включению элемента имеющий A-вычислимую универсальную нумерацию, более того в семействе S все элементы попарно не пересекаются. Если A — гипериммунное множество, тогда A-вычислимое семейство F всюду определенных функций содержащий не менее двух элементов не имеет универсальной A-вычислимой нумерации. А если degT (A) гипериммунно-свободно, тогда каждое A-вычислимое конечное семейство всюду определенных функций имеет A-вычислимую универсальную нумерацию. В данной работе показывается, что любое бесконечное эффективно дискретное семейство множеств с гипериммунно-свободным оракулом A имеет A-вычислимую универсальную нумерацию. Также доказывается, что если семейство S содержит все ко-конечные множества и не содержит хотябы один ко-в.п. множество, тогда данное семейство не имеет универсальную Σ −1 2 -вычислимую нумерацию
Библиографические ссылки
[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
