Enumeration Reducibility and Positive Reducibility of the Numberings of Families of Arithmetic Sets
M. Kh. Faĭzrahmanov · Siberian Mathematical Journal · 2023
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.