Geodesic
Degrees of presentability of structures.~I
Algebra i logika, Tome 46 (2007) no. 6, pp. 763-788.

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

Presentations of structures in admissible sets, as well as different relations of effective reducibility between the structures, are treated. Semilattices of degrees of $\Sigma$-definability are the main object of investigation. It is shown that the semilattice of degrees of $\Sigma$-definability of countable structures agrees well with semilattices of $T$- and $e$-degrees of subsets of natural numbers. Also an attempt is made to study properties of the structures that are inherited under various effective reducibilities and explore how degrees of presentability depend on choices of different admissible sets as domains for presentations.
Mots-clés : admissible set, structure
Keywords: semilattice of degrees of $\Sigma$-definability. 
@article{AL_2007_46_6_a5,
     author = {A. I. Stukachev},
     title = {Degrees of presentability of {structures.~I}},
     journal = {Algebra i logika},
     pages = {763--788},
     publisher = {mathdoc},
     volume = {46},
     number = {6},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2007_46_6_a5/}
}
TY  - JOUR
AU  - A. I. Stukachev
TI  - Degrees of presentability of structures.~I
JO  - Algebra i logika
PY  - 2007
SP  - 763
EP  - 788
VL  - 46
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2007_46_6_a5/
LA  - ru
ID  - AL_2007_46_6_a5
ER  - 
%0 Journal Article
%A A. I. Stukachev
%T Degrees of presentability of structures.~I
%J Algebra i logika
%D 2007
%P 763-788
%V 46
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2007_46_6_a5/
%G ru
%F AL_2007_46_6_a5
A. I. Stukachev. Degrees of presentability of structures.~I. Algebra i logika, Tome 46 (2007) no. 6, pp. 763-788. http://geodesic.mathdoc.fr/item/AL_2007_46_6_a5/

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

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

[3] A. I. Stukachev, “$\Sigma$-dopustimye semeistva nad lineinymi poryadkami”, Algebra i logika, 41:2 (2002), 228–252 | MR | Zbl

[4] L. Richter, “Degrees of structures”, J. Symb. Log., 46 (1981), 723–731 | DOI | MR | Zbl

[5] D. Lacombe, “Deux généralizations de la notion de récursivité relative”, C. R. Acad. Sci., Paris, 258 (1964), 3410–3413 | MR | Zbl

[6] Y. N. Moschovakis, “Abstract computability and invariant definability”, J. Symb. Log., 34 (1969), 605–633 | DOI | MR | Zbl

[7] J. F. Knight, “Degrees coded in jumps of orderings”, J. Symb. Log., 51 (1986), 1034–1042 | DOI | MR | Zbl

[8] A. N. Khisamiev, “O verkhnei polureshëtke Ershova $\mathfrak L_E$”, Sib. matem. zh., 45:1 (2004), 211–228 | MR | Zbl

[9] V. Baleva, “The jump operation for structure degrees”, Arch. Math. Logic, 45, no. 3, 249–265 | MR | Zbl

[10] Yu. T. Medvedev, “Stepeni trudnosti massovykh problem”, Dokl. AN SSSR, 104:4 (1955), 501–504 | Zbl

[11] E. Z. Dyment, “O nekotorykh svoistvakh reshëtki Medvedeva”, Matem. sb., 101(143):3(11) (1976), 360–379 | MR | Zbl

[12] U. Kalvert, D. Kammins, Dzh. F. Nait, S. Miller, “Sravnenie klassov konechnykh struktur”, Algebra i logika, 43:6 (2004), 666–701 | MR | Zbl

[13] A. A. Muchnik, “O silnoi i slaboi svodimosti algoritmicheskikh problem”, Sib. matem. zh., 4:6 (1963), 1328–1341 | MR | Zbl

[14] A. Selman, “Arithmetical reducibilities. I”, Z. Math. Logik Grundl. Math., 17 (1971), 335–350 | DOI | MR | Zbl

[15] M. G. Rozinas, “Polureshëtka $e$-stepenei”, Rekursivnye funktsii, Ivanovskii gos. un-t, Ivanovo, 1978, 71–84 | MR

[16] J. Miller, “Degrees of unsolvability of continuous functions”, J. Symb. Log., 69:2 (2004), 555–584 | DOI | MR | Zbl

[17] A. Sorbi, “The Medvedev lattice of degrees of difficulty”, Computability, enumerability, unsolvability. Directions in recursion theory, Lond. Math. Soc. Lect. Note Ser., 224, eds. Cooper S. B. et al., Cambridge Univ. Press, Cambridge, 1996, 289–312 | MR | Zbl

[18] J. Barwise, A. Robinson, “Completing theories by forcing”, Ann. Math. Logic, 2 (1970), 119–142 | DOI | MR | Zbl

[19] 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