Geodesic
Reducibility on families
Algebra i logika, Tome 48 (2009) no. 1, pp. 31-53.

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

A reducibility on families of subsets of natural numbers is introduced which allows the family per se to be treated without its representation by natural numbers being fixed. This reducibility is used to study a series of problems both in classical computability and on admissible sets: for example, describing index sets of families belonging to $\Sigma_3^0 $, generalizing Friedberg's completeness theorem for a suitable reducibility on admissible sets, etc.
Keywords: family of subsets of natural numbers, reducibility.
Mots-clés : admissible set 
@article{AL_2009_48_1_a1,
     author = {I. Sh. Kalimullin and V. G. Puzarenko},
     title = {Reducibility on families},
     journal = {Algebra i logika},
     pages = {31--53},
     publisher = {mathdoc},
     volume = {48},
     number = {1},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2009_48_1_a1/}
}
TY  - JOUR
AU  - I. Sh. Kalimullin
AU  - V. G. Puzarenko
TI  - Reducibility on families
JO  - Algebra i logika
PY  - 2009
SP  - 31
EP  - 53
VL  - 48
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2009_48_1_a1/
LA  - ru
ID  - AL_2009_48_1_a1
ER  - 
%0 Journal Article
%A I. Sh. Kalimullin
%A V. G. Puzarenko
%T Reducibility on families
%J Algebra i logika
%D 2009
%P 31-53
%V 48
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2009_48_1_a1/
%G ru
%F AL_2009_48_1_a1
I. Sh. Kalimullin; V. G. Puzarenko. Reducibility on families. Algebra i logika, Tome 48 (2009) no. 1, pp. 31-53. http://geodesic.mathdoc.fr/item/AL_2009_48_1_a1/

[1] S. S. Goncharov, V. S. Harizanov, J. F. Knight, C. McCoy, R. Miller, R. Solomon, “Enumerations in computable structure theory”, Ann. Pure Appl. Logic, 136:3 (2005), 219–246 | DOI | MR | Zbl

[2] Yu. L. Ershov, Opredelimost i vychislimost, Sibirskaya shkola algebry i logiki, Nauch. kniga (NII MIOO NGU), Novosibirsk, 1996 | MR | Zbl

[3] V. G. Puzarenko, “Ob odnoi svodimosti na dopustimykh mnozhestvakh”, Sib. matem. zh., 50:2 (2009), 415–429

[4] R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspec. Math. Logic, Springer-Verlag, Berlin etc., 1987 | MR

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

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

[7] A. S. Morozov, V. G. Puzarenko, “O $\Sigma$-podmnozhestvakh naturalnykh chisel”, Algebra i logika, 43:3 (2004), 291–320 | MR | Zbl

[8] C. G. Jockusch, jr., “Degrees in which the recursive sets are uniformly recursive”, Can. J. Math., 24 (1972), 1092–1099 | MR | Zbl

[9] C. E. M. Yates, “On the degrees of index sets. II”, Trans. Am. Math. Soc., 135 (1969), 249–266 | DOI | MR | Zbl

[10] S. S. Marchenkov, “O minimalnykh numeratsiyakh sistem rekursivno perechislimykh mnozhestv”, Dokl. AN SSSR, 198:3 (1971), 530–532 | Zbl

[11] A. L. Selman, “Arithmetical reducibilities. I”, Z. Math. Logik Grundlagen Math., 17 (1971), 335–350 | DOI | MR | Zbl