ON UNIVERSAL NUMBERINGS OF TWO-ELEMENT FAMILIES IN THE ERSHOV HIERARCHY

Herald of Kazakh-British technical university, 2026

Полный текст Открытый доступ: Gold Метаданные (CSL-JSON)
DOI 10.55452/1998-6688-2026-23-2-46-52
Достоверность данных 70 средняя
Как считается эта оценка

Складывается из проверяемых признаков самой записи: есть ли у статьи DOI, сколько независимых источников подтвердили её данные, заполнены ли обязательные поля и насколько свежо последнее подтверждение. Снижают оценку расхождения между источниками и отсутствие идентификатора. Значение от 80 означает, что запись опубликована без дополнительной проверки; от 60 до 79 — что она опубликована с пониженной достоверностью и ручная проверка желательна. Запись, выверенную редактором вручную, пересчёт не опускает ниже 90. Это оценка наших данных о статье, а не оценка самой статьи.

Аннотация

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.