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/