On Non-principal Arithmetical Numberings and Families

The paper studies \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable families ( \(\varvec{n\geqslant 2}\) $\mathit{n}\mathbf{⩾}\mathbf{2}$ ) and their numberings. It is proved that any non-trivial \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable family has a complete with respect to any of its elements \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable non-principal numbering. It is established that if a \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable family is not principal, then any of its \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable numberings has a minimal cover and, if the family is infinite, is incomparable with one of its minimal \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable numberings. It is also shown that for any \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable numbering \(\varvec{\nu }\) $\mathit{\nu }$ of a \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable non-principal family there exists its \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable numbering that is incomparable with \(\varvec{\nu }\) $\mathit{\nu }$ . If a non-trivial \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable family contains the least and greatest elements under inclusion, then for any of its \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable non-principal non-least numberings \(\varvec{\nu }\) $\mathit{\nu }$ there exists a \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable numbering of the family incomparable with \(\varvec{\nu }\) $\mathit{\nu }$ . In particular, this is true for the family of all \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -sets and for the families consisting of two inclusion-comparable \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -sets (semilattices of the \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -computable numberings of such families are isomorphic to the semilattice of \(\varvec{m}\) $\mathit{m}$ -degrees of \(\varvec{\Sigma ^0_n}\) ${\mathbf{\Sigma }}_{\mathit{n}}^{\mathbf{0}}$ -sets).