О существовании семейств множеств без минимальных вычислимых нумераций в иерархии Ершова. On the existence of families of sets without minimal computable numberings in the Ershov hierarchy.

Authors

  • М. Мустафа Казахский Национальный Университет имени аль-Фараби
  • К. Ш. Абешев Казахский Национальный Университет имени аль-Фараби

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.

Downloads

Issue

Section

Mechanics, Mathematics, Computer Science