О существовании семейств множеств без минимальных вычислимых нумераций в иерархии Ершова. On the existence of families of sets without minimal computable numberings in the Ershov hierarchy.
53 32
Keywords:
вычислимые нумерации, минимальные нумерации, иерархия Ершова, computable numbering, minimal numbering, Ershov hierarchy.Abstract
В данной статье рассматриваются проблема построения вычислимых семейств, не имеющих минимальных вычислимых нумерации. Вопрос о существовании семейств множеств без минимальных вычислимых нумераций естественно возникает и для иерархии Ершова. В работе установлено существование таких семейств в каждом классе множеств Σα−1 a иерархии Ершова для случая когда α является ординальным обозначением произвольного вычислимого непредельного ординала. This article discusses the problem of constructing a computable families without minimal computable numbering. The question of the existence of families of sets without minimal computable numberings naturally arises for Ershov hierarchy. In this paper, the existence of such families in each class of sets Σα−1 Ershov hierarchy for the case when α is an ordinal notation any computable successor ordinal.References
[1] Бадаев С.A. Минимальные нумерации. // Труды Института Математики СО РАН. – 1993. – В.25. – С. 3–34.
[2] Badaev S.A., Talasbaeva Zh.T. Computable numberings in the hierarchy of Ershov. – Mathematical Logic in Asia. – World Scientific Publishers. – 2006. – pp. 17–30.
[3] Badaev S.A., Lempp S. A decomposition of the Rogers semilattice of a family of d.c.e. sets. // The Journal of Symbolic Logic. – 2009. – V.74. – N.2. – pp. 618–640.
[4] Вьюгин В.В. О некоторых примерах верхних полурешеток вычислимых нумераций. // Алгебра и Логика. – 1973. – В.12. – №5. – С. 512–529.
[2] Badaev S.A., Talasbaeva Zh.T. Computable numberings in the hierarchy of Ershov. – Mathematical Logic in Asia. – World Scientific Publishers. – 2006. – pp. 17–30.
[3] Badaev S.A., Lempp S. A decomposition of the Rogers semilattice of a family of d.c.e. sets. // The Journal of Symbolic Logic. – 2009. – V.74. – N.2. – pp. 618–640.
[4] Вьюгин В.В. О некоторых примерах верхних полурешеток вычислимых нумераций. // Алгебра и Логика. – 1973. – В.12. – №5. – С. 512–529.
Downloads
How to Cite
Мустафа, М., & Абешев, К. Ш. (2013). О существовании семейств множеств без минимальных вычислимых нумераций в иерархии Ершова. On the existence of families of sets without minimal computable numberings in the Ershov hierarchy. Journal of Mathematics, Mechanics and Computer Science, 78(3), 83–86. Retrieved from https://bm.kaznu.kz/index.php/kaznu/article/view/109
Issue
Section
Mechanics, Mathematics, Computer Science
