Punctual numberings for families of sets
Askarbekkyzy A. Bagaviev R. Isakov V. Kalmurzayev B. Nurlanbek D. Rakymzhankyzy F. Slobozhanin A.
2024E.A. Buketov Karaganda University Publish house
Bulletin of the Karaganda University. Mathematics Series
2024#116Issue 431 - 40 pp.
This work investigates the structure of punctual numberings for families of punctually enumerable sets with respect to primitive recursively reducibility. We say that a numbering of a certain family is primitive recursively reducible to another numeration of the same family if there exists a primitive recursively procedure (an algorithm not employing unbounded search) mapping the numbers of objects in the first numbering to the numbers of the same objects in the second numbering. This study was motivated by the work of Bazhenov, Mustafa, and Ospichev on punctual Rogers semilattices for families of primitive recursively enumerable functions. The concept of punctually enumerable sets was introduced in the paper, and it was proven that not all recursively enumerable sets are punctually enumerable, but in all m-degrees, recursively enumerable sets include punctually enumerable sets. For two-element families of punctual sets, it was demonstrated that punctual Rogers semilattices can be of at least three types: (1) one-element family, (2) isomorphic to the upper semilattice of recursively enumerable sets with respect to primitive recursively m-reducibility, (3) without the greatest element. It was also proven that the set of all punctually enumerable sets does not have a punctual numbering, and punctual families with a Friedberg numbering do not have the least numbering.
primitive recursive functions , punctual numberings , punctually enumerable sets , quick functions , Rogers semilattice
Text of the article Перейти на текст статьи
Kazakh-British Technical University, Almaty, Kazakhstan
Kazan Federal University, Kazan, Russian Federation
Novosibirsk State University, Novosibirsk, Russian Federation
Kazakh-British Technical University
Kazan Federal University
Novosibirsk State University
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026