|
This article is cited in 4 scientific papers (total 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.
Received: 04.02.2022 Revised: 03.10.2022 Accepted: 10.10.2022
Citation:
M. Kh. Faizrahmanov, “Enumeration reducibility and positive reducibility of the numberings of families of arithmetic sets”, Sibirsk. Mat. Zh., 64:1 (2023), 204–212; Siberian Math. J., 64:1 (2023), 174–180
Linking options:
https://www.mathnet.ru/eng/smj7756 https://www.mathnet.ru/eng/smj/v64/i1/p204
|
Statistics & downloads: |
Abstract page: | 112 | Full-text PDF : | 17 | References: | 34 | First page: | 6 |
|