Geodesic
Degrees of presentability of structures.~II
Algebra i logika, Tome 47 (2008) no. 1, pp. 108-126.

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

We show that the property of being locally constructivizable is inherited under Muchnik reducibility, which is weakest among the effective reducibilities considered over countable structures. It is stated that local constructivizability of level higher than 1 is inherited under $\Sigma$-reducibility but is not inherited under Medvedev reducibility. An example of a structure $\mathfrak M$ and a relation $P\subseteq M$ is constructed for which $\underline{(\mathfrak M,P)}\equiv\underline{\mathfrak M}$ but $(\mathfrak M,P)\not\equiv_\Sigma\mathfrak M$. Also, we point out a class of structures which are effectively defined by a family of their local theories.
Mots-clés : admissible set
Keywords: semilattice of degrees of $\Sigma$-definability. 
@article{AL_2008_47_1_a6,
     author = {A. I. Stukachev},
     title = {Degrees of presentability of {structures.~II}},
     journal = {Algebra i logika},
     pages = {108--126},
     publisher = {mathdoc},
     volume = {47},
     number = {1},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2008_47_1_a6/}
}
TY  - JOUR
AU  - A. I. Stukachev
TI  - Degrees of presentability of structures.~II
JO  - Algebra i logika
PY  - 2008
SP  - 108
EP  - 126
VL  - 47
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2008_47_1_a6/
LA  - ru
ID  - AL_2008_47_1_a6
ER  - 
%0 Journal Article
%A A. I. Stukachev
%T Degrees of presentability of structures.~II
%J Algebra i logika
%D 2008
%P 108-126
%V 47
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2008_47_1_a6/
%G ru
%F AL_2008_47_1_a6
A. I. Stukachev. Degrees of presentability of structures.~II. Algebra i logika, Tome 47 (2008) no. 1, pp. 108-126. http://geodesic.mathdoc.fr/item/AL_2008_47_1_a6/

[1] A. I. Stukachev, “O stepenyakh predstavimosti modelei. I”, Algebra i logika, 46:6 (2007), 763–788

[2] A. I. Stukachev, “On mass problems of presentability”, Theory and applications of models of computation, Proc. Third int. conf., TAMC 2006 (Beijing, China, May 15-20, 2006), Lect. Notes Comp. Sci., 3959, eds. Jin-Yi Cai et al., Springer–Verlag, Berlin, 2006, 772–782 | MR | Zbl

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

[4] T. Slaman, “Relative to any nonrecursive”, Proc. Am. Math. Soc., 126:7 (1998), 2117–2122 | DOI | MR | Zbl

[5] S. Wehner, “Enumeration, countable structure and Turing degrees”, Proc. Am. Math. Soc., 126:7 (1998), 2131–2139 | DOI | MR | Zbl

[6] C. Ash, J. Knight, M. Manasse, T. Slaman, “Generic copies of countable structures”, Ann. Pure Appl. Logic, 42:3 (1989), 195–205 | DOI | MR | Zbl

[7] R. Platek, “A note on the cardinality of the Medvedev lattice”, Proc. Am. Math. Soc., 25 (1970), 917 | DOI | MR | Zbl

[8] W. Hodges, Model theory, Encycl. Math. Appl., 42, Cambridge Univ. Press, Cambridge, 1993 | MR | Zbl

[9] J. F. Knight, “Degrees of models”, Handbook of recursive mathematics vol. 1: Recursive model theory, Stud. Logic Found. Math., 138, eds. Yu. L. Ershov et al., Elsevier Science B.V., Amsterdam, 1998, 289–309 | MR | Zbl

[10] I. N. Soskov, “Degree spectra and co-spectra of structures”, Ann. Univ. Sofia Fac. Math. Inform., 96 (2004), 45–68 | MR | Zbl