PhD, ассоциированный профессор.
Алматы
PhD, Associate Professor.
Almaty
Докторант.
Алматы
PhD student.
Almaty
Кандидат физико-математических наук.
Новосибирск
PhD in Mathematical Logic, Algebra and Number Theory.
Novosibirsk
Изучение локальных и глобальных инвариантов полурешетки Роджерса является важной и фундаментальной задачей в теории нумерации и теории вычислимости. Глобальные инварианты включают такие свойства, как существование универсальной нумерации, число минимальных нумераций, мощность всей полурешетки и критерий определения того, является ли полурешетка решеткой. Локальные инварианты, в свою очередь, описывают структуры, такие как начальные сегменты или интервалы внутри полурешетки. Мы говорим, что нумерация является универсальной, если любая другая нумерация сводится к . Изучение универсальных нумераций важно для понимания структуры полурешеток и их классификации. В данной работе рассматривается существование универсальных нумераций для конечных семейств вычислимо перечислимых множеств, расположенных на конечных уровнях иерархии Ершова. Основной результат заключается в том, что для любого семейства вычислимо перечислимых множеств , состоящего из двух элементов, его полурешетка Роджерса, рассматриваемая на третьем уровне иерархии Ершова, имеет универсальную нумерацию.
The study of local and global invariants of the Rogers semilattice is an important and fundamental problem in numbering theory and computability theory. Global invariants include properties such as an existence of a universal numbering, the number of minimal numberings, the cardinality of the entire semilattice, and a criterion for determining whether a semilattice is a lattice. Local invariants, in turn, describe structures, such as initial segments or intervals within the semilattice. We say that a numbering is universal if any other numbering reduces to . The study of universal numberings is important for understanding the structure of semilattices and their classification. In this paper, an existence of universal numberings is considered for finite families of computably enumerable sets located at finit levels of the Ershov hierarchy. The main result is that for any two-element family of computably enumerable sets , its Rogers semilattice, considered at the third level of the Ershov hierarchy, has universal numberings.
The authors declare that there are no conflicts of interest present.