Geodesic
Friedberg numbering of the family of All $\Sigma^{1}_{2}$-sets
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 18 (2018) no. 2, pp. 47-52 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: enumeration, minimal enumeration, Friedberg enumeration, analytical hierarchy. 
@article{VNGU_2018_18_2_a3,
     author = {M. V. Dorzhieva},
     title = {Friedberg numbering of the family of {All} $\Sigma^{1}_{2}$-sets},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {47--52},
     year = {2018},
     volume = {18},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2018_18_2_a3/}
}
TY  - JOUR
AU  - M. V. Dorzhieva
TI  - Friedberg numbering of the family of All $\Sigma^{1}_{2}$-sets
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2018
SP  - 47
EP  - 52
VL  - 18
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VNGU_2018_18_2_a3/
LA  - ru
ID  - VNGU_2018_18_2_a3
ER  - 
%0 Journal Article
%A M. V. Dorzhieva
%T Friedberg numbering of the family of All $\Sigma^{1}_{2}$-sets
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2018
%P 47-52
%V 18
%N 2
%U http://geodesic.mathdoc.fr/item/VNGU_2018_18_2_a3/
%G ru
%F VNGU_2018_18_2_a3
M. V. Dorzhieva. Friedberg numbering of the family of All $\Sigma^{1}_{2}$-sets. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 18 (2018) no. 2, pp. 47-52. http://geodesic.mathdoc.fr/item/VNGU_2018_18_2_a3/

[1] S. Goncharov, J. F. Knight, “Computable structure and non-structure theorems”, Algebra Logika, 41:6 (2002), 639–681 (in Russian) | MR | Zbl

[2] Friedberg R. M., “Three theorems on recursive enumeration”, J. of Symbolic Logic, 23:3 (1958), 309–316 | DOI | MR

[3] Yu. L. Ershov, Numeration Theory, Nauka, M., 1977 (in Russian) | MR

[4] Kummer M., “Some Applications of Computable One-One Numberings”, Arch. Math. Logic, 30:4 (1990), 219–230 | DOI | MR | Zbl

[5] Kummer M., “Recursive Enumeration without Repetition Revisited”, Recursion Theory Week (Oberwolfach, 1989), Lecture Notes in Math., 1432, Springer, Berlin, 1990, 255–275 | DOI | MR

[6] S. S. Goncharov, A. Sorbi, “Generalised computable numerations and non-trival Rogers semilattices”, Algebra and Logic, 36:6 (1997), 359–369 | DOI | MR | Zbl

[7] Badaev S., Goncharov S., “Computability and Numberings”, New Computational Paradigms, Springer, N. Y., 2008, 19–34 | DOI | MR | Zbl

[8] S. Goncharov, S. Lempp, D. R. Solomon, “Friedberg numberings of families of $n$-computably enumerable sets”, Algebra i Logika, 41:2 (2002), 143–154 (in Russian) | MR | Zbl

[9] Badaev S., Manat M., Sorbi A., “Friedberg Numberings in the Ershov Hierarchy”, Arch. Math. Logic, 54:1–2 (2015), 59–73 | DOI | MR | Zbl

[10] Owings J. C., jr., “The Meta-$r.e.$ Sets, but not the $\Pi_{1}^{1}$ Sets, Can be Enumerated without Repetition”, J. of Symbolic Logic, 35:2 (1970), 223–229 | DOI | MR | Zbl

[11] M. V. Dorzhieva, “Metarecursion elimination from Owings theorem”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 14:1 (2014), 35–43 (in Russian) | Zbl

[12] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, N. Y., 1967 | MR | Zbl