Geodesic
Constructive and Non-Constructive Infinite Formulas in Computable Structures
Algebra i logika, Tome 42 (2003) no. 4, pp. 391-412

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

A transition from arbitrary $L_{\omega_1\omega}$-formulas to computable formulas in the class of computable structures is considered. It is shown that transition of a certain type is possible which doubles the complexity of the formulas. In addition, the complexity jump is analyzed for the transition from an arbitrary Scott family consisting of $L_{\omega_1\omega}$-formulas to a computable Scott family in a fixed computable structure. Exact estimates of this jump are found.
Keywords: computable structure, computable formula, Scott family. 
P. E. Alaev. Constructive and Non-Constructive Infinite Formulas in Computable Structures. Algebra i logika, Tome 42 (2003) no. 4, pp. 391-412. http://geodesic.mathdoc.fr/item/AL_2003_42_4_a0/
@article{AL_2003_42_4_a0,
     author = {P. E. Alaev},
     title = {Constructive and {Non-Constructive} {Infinite} {Formulas} in {Computable} {Structures}},
     journal = {Algebra i logika},
     pages = {391--412},
     year = {2003},
     volume = {42},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2003_42_4_a0/}
}
TY  - JOUR
AU  - P. E. Alaev
TI  - Constructive and Non-Constructive Infinite Formulas in Computable Structures
JO  - Algebra i logika
PY  - 2003
SP  - 391
EP  - 412
VL  - 42
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/AL_2003_42_4_a0/
LA  - ru
ID  - AL_2003_42_4_a0
ER  - 
%0 Journal Article
%A P. E. Alaev
%T Constructive and Non-Constructive Infinite Formulas in Computable Structures
%J Algebra i logika
%D 2003
%P 391-412
%V 42
%N 4
%U http://geodesic.mathdoc.fr/item/AL_2003_42_4_a0/
%G ru
%F AL_2003_42_4_a0

[1] C. J. Ash, “Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees”, Trans. Am. Math. Soc., 298:2 (1986), 497–514 | DOI | MR | Zbl

[2] C. J. Ash, “Categoricity in hyperarithmetical degrees”, Ann. Pure Appl. Logic, 34:1 (1987), 1–14 | DOI | MR | Zbl

[3] C. J. Ash, J. F. Knight, “Relatively recursive expansions”, Fundam. Math., 140:2 (1992), 137–155 | MR | Zbl

[4] C. J. Ash, J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Elsevier Science B.V., Amsterdam a. o., 2000 | MR

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