Abstract:
If $\nu$ and $\mu$ are some $\Delta^0_2$-computable numberings of families of sets of the naturals then $P(x,y)\Leftrightarrow\nu(x)'\not=\mu(y)$ is a $\Sigma^0_2$-predicate. Deriving corollaries from this result, we obtain a sufficient condition for existence of a $\Delta^0_2$-computable numbering of the subfamily of all sets in a given family with the Turing jumps belonging to a fixed level of the Ershov hierarchy, and we deduce existence of a $\Sigma^{-1}_\omega$-computable numbering of the family of all superlow sets.