Geodesic
Computable numberings of families of infinite sets
Algebra i logika, Tome 58 (2019) no. 3, pp. 334-343.

Voir la notice de l'article provenant de la source Math-Net.Ru

We state the following results: the family of all infinite computably enumerable sets has no computable numbering; the family of all infinite $\Pi^{1}_{1}$ sets has no $\Pi^{1}_{1}$-computable numbering; the family of all infinite $\Sigma^{1}_{2}$ sets has no $\Sigma^{1}_{2}$-computable numbering. For $k>2$, the existence of a $\Sigma^{1}_{k}$-computable numbering for the family of all infinite $\Sigma^{1}_{k}$ sets leads to the inconsistency of $ZF$.
Keywords: computability, analytical hierarchy, computable numberings, Friedberg numbering, Gödel's axiom of constructibility. 
@article{AL_2019_58_3_a2,
     author = {M. V. Dorzhieva},
     title = {Computable numberings of families of infinite sets},
     journal = {Algebra i logika},
     pages = {334--343},
     publisher = {mathdoc},
     volume = {58},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2019_58_3_a2/}
}
TY  - JOUR
AU  - M. V. Dorzhieva
TI  - Computable numberings of families of infinite sets
JO  - Algebra i logika
PY  - 2019
SP  - 334
EP  - 343
VL  - 58
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2019_58_3_a2/
LA  - ru
ID  - AL_2019_58_3_a2
ER  - 
%0 Journal Article
%A M. V. Dorzhieva
%T Computable numberings of families of infinite sets
%J Algebra i logika
%D 2019
%P 334-343
%V 58
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2019_58_3_a2/
%G ru
%F AL_2019_58_3_a2
M. V. Dorzhieva. Computable numberings of families of infinite sets. Algebra i logika, Tome 58 (2019) no. 3, pp. 334-343. http://geodesic.mathdoc.fr/item/AL_2019_58_3_a2/

[1] M. V. Dorzhieva, “Eliminatsiya metarekursii iz teoremy Ouinsa”, Vestn. NGU. Ser. matem., mekh., inform., 14:1 (2014), 35–43 | Zbl

[2] M. V. Dorzhieva, “Odnoznachnaya numeratsiya dlya semeistva vsekh $\Sigma^{1}_{2}$-mnozhestv”, Sib. zhurn. chist. i prikl. matem., 18:2 (2018), 47–52 | MR | Zbl

[3] R. M. Friedberg, “Three theorems on recursive enumeration. I: Decomposition. II: Maximal set. III: Enumeration without duplication”, J. Symb. Log., 23:3 (1958), 309–316 | DOI | MR

[4] S. S. Goncharov, A. Sorbi, “Obobschenno-vychislimye numeratsii i netrivialnye polureshetki Rodzhersa”, Algebra i logika, 36:6 (1997), 621–641 | MR | Zbl

[5] S. S. Goncharov, S. Lempp, D. R. Solomon, “Fridbergovskie numeratsii semeistv $n$-vychislimo perechislimykh mnozhestv”, Algebra i logika, 41:2 (2002), 143–154 | MR | Zbl

[6] J. C. Owings, Jr., “The meta-r.e. sets, but not the $\Pi^1_1$ sets, can be enumerated without repetition”, J. Symb. Log., 35:2 (1970), 223–229 | DOI | MR | Zbl

[7] A. I. Maltsev, Algoritmy i rekursivnye funktsii, Nauka, M., 1965

[8] Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

[9] V. G. Kanovei, V. A. Lyubetskii, Sovremennaya teoriya mnozhestv: borelevskie i proektivnye mnozhestva, MTsNMO, M., 2010

[10] K. Gödel, “The consistency of the axiom of choice and of the generalized continuum-hypothesis”, Proc. Natl. Acad. Sci., 24 (1938), 556–557 | DOI

[11] J. W. Addison, “Separation principles in the hierarchies of classical and effective descriptive set theory”, Fundam. Math., 46 (1959), 123–135 | DOI | MR | Zbl

[12] J. W. Addison, Y. N. Moschovakis, “Some consequences of the axiom of definable determinateness”, Proc. Natl. Acad. Sci., 59 (1968), 708–712 | DOI | MR | Zbl

[13] D. A. Martin, “The axiom of determinateness and reduction principles in the analytical hierarchy”, Bull. Am. Math. Soc., 74:4 (1968), 687–689 | DOI | MR | Zbl

[14] T. Jech, Set theory, Springer Monogr. Math., The third millennium edition, revised and expanded, Springer, Berlin, 2003 | MR | Zbl

[15] J. W. Addison, “Some consequences of the axiom of constructibility”, Fundam. Math., 46 (1959), 337–357 | DOI | MR | Zbl