Geodesic
Friedberg Numberings of Families of $n$-Computably Enumerable Sets
Algebra i logika, Tome 41 (2002) no. 2, pp. 143-154.

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

We establish a number of results on numberings, in particular, on Friedberg numberings, of families of d.c.e. sets. First, it is proved that there exists a Friedberg numbering of the family of all d.c.e. sets. We also show that this result, patterned on Friedberg's famous theorem for the family of all c.e. sets, holds for the family of all $n$-c.e. sets for any $n>2$. Second, it is stated that there exists an infinite family of d. c. e. sets without a Friedberg numbering. Third, it is shown that there exists an infinite family of c. e. sets (treated as a family of d. c. e. sets) with a numbering which is unique up to equivalence. Fourth, it is proved that there exists a family of d. c. e. sets with a least numbering (under reducibility) which is Friedberg but is not the only numbering (modulo reducibility). 
@article{AL_2002_41_2_a2,
     author = {S. S. Goncharov and S. Lempp and R. Solomon},
     title = {Friedberg {Numberings} of {Families} of $n${-Computably} {Enumerable} {Sets}},
     journal = {Algebra i logika},
     pages = {143--154},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2002_41_2_a2/}
}
TY  - JOUR
AU  - S. S. Goncharov
AU  - S. Lempp
AU  - R. Solomon
TI  - Friedberg Numberings of Families of $n$-Computably Enumerable Sets
JO  - Algebra i logika
PY  - 2002
SP  - 143
EP  - 154
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2002_41_2_a2/
LA  - ru
ID  - AL_2002_41_2_a2
ER  - 
%0 Journal Article
%A S. S. Goncharov
%A S. Lempp
%A R. Solomon
%T Friedberg Numberings of Families of $n$-Computably Enumerable Sets
%J Algebra i logika
%D 2002
%P 143-154
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2002_41_2_a2/
%G ru
%F AL_2002_41_2_a2
S. S. Goncharov; S. Lempp; R. Solomon. Friedberg Numberings of Families of $n$-Computably Enumerable Sets. Algebra i logika, Tome 41 (2002) no. 2, pp. 143-154. http://geodesic.mathdoc.fr/item/AL_2002_41_2_a2/

[1] 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

[2] Ju. L. Eršov, “Theorie der numerierungen. I”, Z. Math. Logik Grundlagen Math., 19:4 (1973), 289–388 ; “Theorie der numerierungen. II”, Z. Math. Logik Grundlagen Math., 21:6 (1975), 473–584 ; “Theorie der numerierungen. III”, Z. Math. Logik Grundlagen Math., 23:4 (1977), 289–371 | MR | MR | DOI | MR

[3] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977 | MR

[4] Yu. L. Ershov, “Theory of numberings”, Handbook of computability theory, ed. E. R. Griffor, North-Holland, Amsterdam, 1999, 473–503 | MR

[5] A. H. Lachlan, “On recursive numeration without repetition”, Z. Math. Logik Grundlagen Math., 11:3 (1965), 209–220 ; “A correction to: On recursive numeration without repetition”, Z. Math. Logik Grundlagen Math., 13:2 (1967), 99–100 | DOI | MR | Zbl | DOI | MR | Zbl

[6] M. B. Pour-El, W. A. Howard, “A structural criterion for recursive numeration without repetition”, Z. Math. Logik Grundlagen Math., 10:2 (1964), 105–114 | DOI | MR | Zbl

[7] M. B. Pour-El, H. Putnam, “Recursively enumerable classes and their applications to sequences of formal theories”, Arch. Math. Logik Grundlagenforsch., 8 (1965), 104–121 | DOI | MR | Zbl

[8] H. Putnam, “Trial and error predicates and the solution to a problem of Mostowski”, J. Symb. Log., 30:1 (1965), 49–57 | DOI | MR | Zbl

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

[10] S. S. Goncharov, “Vychislimye odnoznachnye numeratsii”, Algebra i logika, 19:5 (1980), 507–551 | MR | Zbl

[11] A. I. Maltsev, Algoritmy i rekursivnye funktsii, Nauka, M., 1965 | MR

[12] M. Kummer, “Recursive numerations without repetition revisited”, Lect. Notes Comput. Sci., 1432, Springer-Verlag, Berlin, 1990, 255–275 | MR

[13] S. S. Goncharov, “Predelno ekvivalentnye konstruktivizatsii”, Matematicheskaya logika i teoriya algoritmov, Trudy In-ta matem. SO AN SSSR, 2, 1982, 4–12 | MR | Zbl

[14] S. S. Goncharov, A. Yaknis, V. Yaknis, “Some effectively infinite classes of enumerations”, Ann. Pure Appl. Logic, 60:3 (1993), 207–236 | DOI | MR

[15] C. C. Goncharov, “Pozitivnye numeratsii semeistv s odnoznachnymi numeratsiyami”, Algebra i logika, 22:5 (1983), 481–488 | MR | Zbl

[16] P. Odifreddi, Classical recursion theory, v. 1, North-Holland, Amsterdam–New York, 1989 | MR | Zbl