Geodesic
Descriptive properties on admissible sets
Algebra i logika, Tome 49 (2010) no. 2, pp. 238-262.

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

Relations are treated between the following descriptive properties on admissible sets: enumerability, uniformization, reduction, separation, extension. Moreover, in the setting of these properties, we consider existence problems for a universal computable function and for a computable function universal for $\{0;1\}$-valued computable functions. It is shown that all relations between the given properties are strict. Also we look into algorithmic complexity of admissible sets lending support to the specified relations. It is stated that the reduction principle fails in some admissible sets over classical structures.
Mots-clés : admissible set
Keywords: descriptive property, universal function. 
@article{AL_2010_49_2_a5,
     author = {V. G. Puzarenko},
     title = {Descriptive properties on admissible sets},
     journal = {Algebra i logika},
     pages = {238--262},
     publisher = {mathdoc},
     volume = {49},
     number = {2},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2010_49_2_a5/}
}
TY  - JOUR
AU  - V. G. Puzarenko
TI  - Descriptive properties on admissible sets
JO  - Algebra i logika
PY  - 2010
SP  - 238
EP  - 262
VL  - 49
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2010_49_2_a5/
LA  - ru
ID  - AL_2010_49_2_a5
ER  - 
%0 Journal Article
%A V. G. Puzarenko
%T Descriptive properties on admissible sets
%J Algebra i logika
%D 2010
%P 238-262
%V 49
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2010_49_2_a5/
%G ru
%F AL_2010_49_2_a5
V. G. Puzarenko. Descriptive properties on admissible sets. Algebra i logika, Tome 49 (2010) no. 2, pp. 238-262. http://geodesic.mathdoc.fr/item/AL_2010_49_2_a5/

[1] Yu. L. Ershov, Opredelimost i vychislimost, Nauchnaya kniga, Novosibirsk, 2000 | MR

[2] J. Barwise, Admissible sets and structures, Springer-Velag, Berlin, 1975 | MR | Zbl

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

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

[5] V. G. Puzarenko, “Obobschennye numeratsii i opredelimost polya $\mathbb R$ v dopustimykh mnozhestvakh”, Vestnik NGU. Ser. matem., mekh., inform., 3:2 (2003), 107–117 | Zbl

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

[7] A. N. Khisamiev, “O kvazirezolventnykh modelyakh i $B$-modelyakh”, Algebra i logika, 40:4 (2001), 484–499 | MR | Zbl

[8] V. G. Puzarenko, “K vychislimosti na spetsialnykh modelyakh”, Sib. matem. zh., 46:1 (2005), 185–208 | MR | Zbl

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

[10] V. G. Puzarenko, “O vychislimosti nad modelyami razreshimykh teorii”, Algebra i logika, 39:2 (2000), 170–197 | MR | Zbl

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

[12] R. Yu. Vaitsenavichyus, “O neobkhodimykh usloviyakh suschestvovaniya universalnoi funktsii na dopustimom mnozhestve”, Matematicheskaya logika i primeneniya, 1989, no. 6, 21–37, Vilnyus | MR

[13] V. A. Rudnev, “Ob universalnoi rekursivnoi funktsii na dopustimykh mnozhestvakh”, Algebra i logika, 25:4 (1986), 425–435 | MR | Zbl

[14] A. I. Stukachev, “Teorema ob uniformizatsii v nasledstvenno konechnykh nadstroikakh”, Obobschënnaya vychislimost i opredelimost, Vychisl. sist., 161, In-t matem. SO RAN, Novosibirsk, 1998, 3–14 | MR