TY - JOUR

T1 - Punctual numberings for families of sets

AU - Askarbekkyzy, Aknur

AU - Bagaviev, Ramil

AU - Isakov, Valeriy

AU - Kalmurzayev, Birzhan

AU - Nurlanbek, Dias

AU - Rakymzhankyzy, Fariza

AU - Slobozhanin, Artyom

PY - 2024/12/30

Y1 - 2024/12/30

N2 - 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.

AB - 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.

KW - Rogers semilattice

KW - primitive recursive functions

KW - punctual numberings

KW - punctually enumerable sets

KW - quick functions

KW - primitive recursive functions

KW - punctual numberings

KW - punctually enumerable sets

KW - quick functions

KW - Rogers semilattice

UR - https://www.mendeley.com/catalogue/0f3b5004-8489-3d2a-bade-72159afe574c/

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85214448495&origin=inward&txGid=9af7f994c5ccbfbd9c6cc3fc99e94899

U2 - 10.31489/2024M4/31-40

DO - 10.31489/2024M4/31-40

M3 - Article

VL - 116

SP - 31

EP - 40

JO - Вестник Карагандинского университета. Серия Математика

JF - Вестник Карагандинского университета. Серия Математика

SN - 2518-7929

IS - 4

ER -