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

Sibirsk. Mat. Zh., 2022 Volume 63, Number 2, Pages 427–436 (Mi smj7667)

This article is cited in 4 papers

On $p$-universal and $p$-minimal numberings

M. Kh. Faizrahmanov

Kazan (Volga Region) Federal University

Abstract: We study the $p$-reducibility of numberings which was introduced and first studied by Degtev. $p$-Reducibility is an effectively bounded version of the $e$-reducibility of numberings. Also, we prove that for every set $A$ there exists an $A$-computable family without universal numberings but admitting $p$-universal numberings and obtain a criterion for the existence of $p$-universal numberings of finite families of $A$-c.e. sets. Finally, we show that every $A$-computable family, with $\emptyset''\leq _TA$, has infinitely many pairwise non-$p$-equivalent $p$-minimal $A$-computable numberings.

Keywords: computable numbering, $A$-computable numbering, $p$-reducibility, universal numbering, $p$-universal numbering, $p$-minimal numbering.

UDC: 510.57

Received: 31.03.2021
Revised: 31.03.2021
Accepted: 10.12.2021

DOI: 10.33048/smzh.2022.63.213


 English version:
Siberian Mathematical Journal, 2022, 63:2, 365–373

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024