О существовании семейств множеств без минимальных вычислимых нумераций в иерархии Ершова. On the existence of families of sets without minimal computable numberings in the Ershov hierarchy.
58 34
Ключевые слова:
вычислимые нумерации, минимальные нумерации, иерархия Ершова, computable numbering, minimal numbering, Ershov hierarchy.Аннотация
В данной статье рассматриваются проблема построения вычислимых семейств, не имеющих минимальных вычислимых нумерации. Вопрос о существовании семейств множеств без минимальных вычислимых нумераций естественно возникает и для иерархии Ершова. В работе установлено существование таких семейств в каждом классе множеств Σα−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.Библиографические ссылки
[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.
Загрузки
Как цитировать
Мустафа, М., & Абешев, К. Ш. (2013). О существовании семейств множеств без минимальных вычислимых нумераций в иерархии Ершова. On the existence of families of sets without minimal computable numberings in the Ershov hierarchy. Вестник КазНУ. Серия математика, механика, информатика, 78(3), 83–86. извлечено от https://bm.kaznu.kz/index.php/kaznu/article/view/109
Выпуск
Раздел
Механика, Математика, Информатика
