RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2023 Volume 64, Number 1, Pages 204–212 (Mi smj7756)

This article is cited in 4 papers

Enumeration reducibility and positive reducibility of the numberings of families of arithmetic sets

M. Kh. Faizrahmanov

Regional Scientific and Educational Mathematical Center of Kazan Federal University

Abstract: We study the structures of the numberings of the families of arithmetic sets defined by $e$- and $p$-reducibilities of numberings. We prove that each finite family of $\Sigma^0_{d+1}$-sets admits a $\Sigma^0_{d+1}$-computable $e$-universal numbering. Examples are given of the $\Sigma^0_{d+2}$-computable families that have $\Sigma^0_{d+2}$-computable $e$-universal numberings but lack $p$-universal numberings. Some $\Sigma^0_{d+1}$-computable families of total functions are constructed without $\Sigma^0_{d+1}$-computable $e$-universal numberings. We establish that each infinite $\Sigma^0_{d+2}$-computable family has infinitely many $e$-minimal as well as $p$-minimal $\Sigma^0_{d+2}$-computable numberings. In conclusion, we prove that each nonsingleton $\Sigma^0_{d+2}$-computable family has infinitely many pairwise non-$e$-equivalent $\Sigma^0_{d+2}$-computable numberings.

Keywords: numbering, $\Sigma^0_{d+1}$-computable numbering, $e$-reducibility, $p$-reducibility, $e$-universal numbering, $p$-universal numbering, $e$-minimal numbering, $p$-minimal numbering.

UDC: 510.57

MSC: 35R30

Received: 04.02.2022
Revised: 03.10.2022
Accepted: 10.10.2022

DOI: 10.33048/smzh.2023.64.117


 English version:
Siberian Mathematical Journal, 2023, 64:1, 174–180

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024