Notes on Classes of Minimal Numberings of Arithmetical Set Families

The paper studies $$\Sigma^{0}_{u}$$ -computable families ( $$u\geqslant 2$$ ) and their minimal numberings. It is proved that the class of all single-valued $$\Sigma^{0}_{u}$$ -computable numberings of any $$\Sigma^{0}_{u}$$ -computable infinite family of total functions is effectively infinite. It is established that for every $$\Sigma^{0}_{u-1}$$ -computable numbering $$\nu$$ of an infinite family of total functions there exists a uniformly $$\Sigma^{0}_{u-1}$$ -computable sequence of its single-valued numberings such that $$\nu$$ is reducible to their direct sum. It is also shown that if $$u>2$$ , then every $$\Sigma^{0}_{u}$$ -computable numbering of any infinite family is reducible to the direct sum of some uniformly $$\Sigma^{0}_{u}$$ -computable and uniformly $$\Sigma^{0}_{u}$$ -minimal sequence of numberings of the family.

Перевод пока недоступен