Geodesic
Computability Principles on Admissible Sets
Matematičeskie trudy, Tome 7 (2004) no. 2, pp. 35-71.

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

We study some principles of descriptive set theory which are translated from $e$-ideals to admissible sets. We are mainly interested in the properties of principal $e$-ideals. A construction is suggested of an admissible set corresponding to a principal $e$-ideal. This construction preserves the majority of basic computability-theoretic properties of a given principal $e$-ideal, such as the enumeration and uniformization principles, the existence of a universal function, and the separation principle. For principal ideals, we find the exact relations between the above-listed properties. We also find the exact arithmetical and structural estimates for the complexity of separating degrees. The results are used for clarifying the relationship between the principles on admissible sets. 
@article{MT_2004_7_2_a1,
     author = {I. Sh. Kalimullin and V. G. Puzarenko},
     title = {Computability {Principles} on {Admissible} {Sets}},
     journal = {Matemati\v{c}eskie trudy},
     pages = {35--71},
     publisher = {mathdoc},
     volume = {7},
     number = {2},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MT_2004_7_2_a1/}
}
TY  - JOUR
AU  - I. Sh. Kalimullin
AU  - V. G. Puzarenko
TI  - Computability Principles on Admissible Sets
JO  - Matematičeskie trudy
PY  - 2004
SP  - 35
EP  - 71
VL  - 7
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MT_2004_7_2_a1/
LA  - ru
ID  - MT_2004_7_2_a1
ER  - 
%0 Journal Article
%A I. Sh. Kalimullin
%A V. G. Puzarenko
%T Computability Principles on Admissible Sets
%J Matematičeskie trudy
%D 2004
%P 35-71
%V 7
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MT_2004_7_2_a1/
%G ru
%F MT_2004_7_2_a1
I. Sh. Kalimullin; V. G. Puzarenko. Computability Principles on Admissible Sets. Matematičeskie trudy, Tome 7 (2004) no. 2, pp. 35-71. http://geodesic.mathdoc.fr/item/MT_2004_7_2_a1/

[1] Ershov Yu. L., “$\Sigma$-opredelimost v dopustimykh mnozhestvakh”, Dokl. AN SSSR, 285:4 (1985), 792–795 | MR | Zbl

[2] Ershov Yu. L., Opredelimost i vychislimost, Nauchnaya kniga; Ekonomika, Novosibirsk; M., 2000

[3] Morozov A. S., “Ob otnoshenii E-svodimosti mezhdu dopustimymi mnozhestvami”, Sib. mat. zhurn., 45:3 (2004), 534–652

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

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

[6] Puzarenko V. G., “O teorii modelei na nasledstvenno konechnykh nadstroikakh”, Algebra i logika, 41:2 (2002), 199–222 | MR | Zbl

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

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

[9] Rodzhers X., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

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

[11] Rudnev V. A., “O suschestvovanii neotdelimoi pary v rekursivnoi teorii dopustimykh mnozhestv”, Algebra i logika, 27:1 (1987), 48–56

[12] Stukachev A. I., “Teorema ob uniformizatsii v nasledstvenno konechnykh nadstroikakh”, Obobschennaya vychislimost i opredelimost, Vychislitelnye sistemy, 161, Izd-vo In-ta matematiki, Novosibirsk, 1998, 3–14 | MR

[13] Ash S. J., Knight J. F., Computable Structures and the Hyper arithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, 144, Elseiver, Amsterdam, 2000 | MR | Zbl

[14] Barwise J., Admissible Sets and Structures, Springer-Verlag, Berlin; Gottingen; Heidelberg, 1975 | MR | Zbl

[15] Jockusch C.G. (Jr.), Soare R. I., “$\Pi_1^0$ classes and degrees of theories”, Trans. Amer. Math. Soc., 173 (1972), 33–56 | DOI | MR | Zbl

[16] Soare R. I., Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer-Verlag, Berlin, etc., 1987 | MR