Geodesic
Computable positive and Friedberg numberings in hyperarithmetic
Algebra i logika, Tome 59 (2020) no. 1, pp. 66-83
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We point out an existence criterion for positive computable total $\Pi^1_1$-numberings of families of subsets of a given $\Pi^1_1$-set. In particular, it is stated that the family of all $\Pi^1_1$-sets has no positive computable total $\Pi^1_1$-numberings. Also we obtain a criterion of existence for computable Friedberg $\Sigma^1_1$-numberings of families of subsets of a given $\Sigma^1_1$-set, the consequence of which is the absence of a computable Friedberg $\Sigma^1_1$-numbering of the family of all $\Sigma^1_1$-sets. Questions concerning the existence of negative computable $\Pi^1_1$- and $\Sigma^1_1$-numberings of the families mentioned are considered.
Keywords: computable numbering, analytical hierarchy, positive numbering, Friedberg numbering, negative numbering.
Mots-clés : admissible set 
@article{AL_2020_59_1_a3,
     author = {I. Sh. Kalimullin and V. G. Puzarenko and M. Kh. Faizrakhmanov},
     title = {Computable positive and {Friedberg} numberings in hyperarithmetic},
     journal = {Algebra i logika},
     pages = {66--83},
     year = {2020},
     volume = {59},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2020_59_1_a3/}
}
TY  - JOUR
AU  - I. Sh. Kalimullin
AU  - V. G. Puzarenko
AU  - M. Kh. Faizrakhmanov
TI  - Computable positive and Friedberg numberings in hyperarithmetic
JO  - Algebra i logika
PY  - 2020
SP  - 66
EP  - 83
VL  - 59
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/AL_2020_59_1_a3/
LA  - ru
ID  - AL_2020_59_1_a3
ER  - 
%0 Journal Article
%A I. Sh. Kalimullin
%A V. G. Puzarenko
%A M. Kh. Faizrakhmanov
%T Computable positive and Friedberg numberings in hyperarithmetic
%J Algebra i logika
%D 2020
%P 66-83
%V 59
%N 1
%U http://geodesic.mathdoc.fr/item/AL_2020_59_1_a3/
%G ru
%F AL_2020_59_1_a3
I. Sh. Kalimullin; V. G. Puzarenko; M. Kh. Faizrakhmanov. Computable positive and Friedberg numberings in hyperarithmetic. Algebra i logika, Tome 59 (2020) no. 1, pp. 66-83. http://geodesic.mathdoc.fr/item/AL_2020_59_1_a3/

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

[2] I. Sh. Kalimullin, V. G. Puzarenko, M. Kh. Faizrakhmanov, “Chastichnye pozitivnye predstavleniya v giperarifmetike”, Sib. matem. zh., 60:3 (2019), 599–609 | Zbl

[3] I. Sh. Kalimullin, V. G. Puzarenko, M. Kh. Faizrakhmanov, “Pozitivnye predstavleniya semeistv otnositelno svodimosti po perechislimosti”, Algebra i logika, 57:4 (2018), 492–498 | Zbl

[4] J. Barwise, Admissible sets and structures. An approach to definability theory, Perspec. Math. Log., Springer-Velag, Berlin, 1975 | DOI | MR | Zbl

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

[6] G. E. Sacks, Higher recursion theory, Perspect. Math. Log., Springer-Verlag, Berlin etc., 1990 | DOI | MR | Zbl

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

[8] M. V. Dorzhieva, “Nerazreshimost elementarnykh teorii polureshetok Rodzhersa analiticheskoi ierarkhii”, Sib. elektron. matem. izv., 13 (2016), 148–153 http://semr.math.nsc.ru/v13/p148-153.pdf

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

[10] V. G. Puzarenko, “O razreshimykh vychislimykh $\mathbb{A}$-numeratsiyakh”, Algebra i logika, 41:5 (2002), 568–584 | Zbl

[11] Yu. L. Ershov, Opredelimost i vychislimost, Sibirskaya shkola algebry i logiki, 2-e izd., ispr. i dop., Nauch. kn., Novosibirsk; Ekonomika, M., 2000

[12] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977

[13] I. Sh. Kalimullin, V. G. Puzarenko, “O printsipakh vychislimosti na dopustimykh mnozhestvakh”, Matem. tr., 7:2 (2004), 35–71 | Zbl

[14] I. Sh. Kalimullin, V. G. Puzarenko, M. Kh. Faizrakhmanov, “Pozitivnye predstavleniya semeistv otnositelno $e$-orakulov”, Sib. matem. zh., 59:4 (2018), 823–833 | Zbl

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