Punctual numberings for families of sets

Abstract

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.