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.