Rogers semilattices of punctual numberings
Bazhenov N. Mustafa M. Ospichev S.
28 February 2022Cambridge University Press
Mathematical Structures in Computer Science
2022#32Issue 2164 - 188 pp.
The paper works within the framework of punctual computability, which is focused on eliminating unbounded search from constructions in algebra and infinite combinatorics. We study punctual numberings, that is, uniform computations for families S of primitive recursive functions. The punctual reducibility between numberings is induced by primitive recursive functions. This approach gives rise to upper semilattices of degrees, which are called Rogers pr-semilattices. We show that any infinite, uniformly primitive recursive family S induces an infinite Rogers pr-semilattice R. We prove that the semilattice R does not have minimal elements, and every nontrivial interval inside R contains an infinite antichain. In addition, every non-greatest element from R is a part of an infinite antichain. We show that the -fragment of the theory Th(R) is decidable.
decidability , Friedberg numbering , Keywords: Theory of numberings , online computation , primitive recursion , punctual structure , Rogers semilattice , upper semilattice
Text of the article Перейти на текст статьи
Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, Novosibirsk, 630090, Russian Federation
Department of Mathematics, School of Sciences and Humanities, Nazarbayev University, 53 Qabanbay Batyr Avenue, Nur-Sultan, 010000, Kazakhstan
Sobolev Institute of Mathematics
Department of Mathematics
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026