×

Minimal coverings in the Rogers semilattices of \(\Sigma^0_n\)-computable numberings. (Russian, English) Zbl 1008.03026

Sib. Mat. Zh. 43, No. 4, 769-778 (2002); translation in Sib. Math. J. 43, No. 4, 616-622 (2002).
The problem of the existence of a minimal covering is studied. The authors prove that if a numbering is not \(\emptyset'\)-principal then it possesses a minimal covering, and that if for a \(\Sigma_n^0\)-computable numbering \(\nu\) of a family of natural numbers there exists a \(\emptyset^{(n-1)}\)-computable total function \(f\) such that \(\nu x\neq\nu f(x)\), for all \(x\in N\), then it possesses a minimal covering which is a \(\Sigma_n^0\)-computable numbering. It follows that if \(S\) is finite and \(\langle S,\subseteq\rangle\) has no least element then each of its \(\Sigma_n^0\)-computable numberings possesses a minimal covering which is a \(\Sigma_n^0\)-computable numbering. A sufficient condition for the existence of strictly minimal coverings is also given.

MSC:

03D45 Theory of numerations, effectively presented structures