Abstract:
We study the existence of a single-valued $\Sigma^{1}_{2}$-computable enumeration of the family of all $\Sigma^{1}_{2}$-sets. Friedberg proved that there is a numbering of the family of all computably enumerated sets without repetition. The same statement holds for all levels of arithmetical hierarchy, as well as for the Ershov hierarchy. However, J. Owings showed that $\Pi^{1}_{1}$-sets cannot be enumerated without repetition. In this paper, we continue to study the Friedberg numbering in analytical hierarchy. The main result is that there is no Friedberg numbering of the family of all $\Sigma^{1}_{2}$-sets.
Fulltext:
PDF file (113 kB)