Geodesic
Generalized hyperarithmetical computability over structures
Algebra i logika, Tome 55 (2016) no. 6, pp. 769-799.

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

We consider the class of approximation spaces generated by admissible sets and, in particular, by hereditarily finite superstructures over structures. Generalized computability on approximation spaces is conceived of as effective definability in dynamic logic. By analogy with the notion of a structure $\Sigma$-definable in an admissible set, we introduce the notion of a structure effectively definable on an approximation space. In much the same way as the $\Sigma$-reducibility relation, we can naturally define a reducibility relation on structures generating appropriate semilattices of degrees of structures (of arbitrary cardinality), as well as a jump operation. It is stated that there is a natural embedding of the semilattice of hyperdegrees of sets of natural numbers in the semilattices mentioned, which preserves the hyperjump operation. A syntactic description of structures having hyperdegree is given.
Keywords: computability theory, admissible sets, approximation spaces, constructive models, computable analysis, hyperarithmetical computability. 
@article{AL_2016_55_6_a5,
     author = {A. I. Stukachev},
     title = {Generalized hyperarithmetical computability over structures},
     journal = {Algebra i logika},
     pages = {769--799},
     publisher = {mathdoc},
     volume = {55},
     number = {6},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2016_55_6_a5/}
}
TY  - JOUR
AU  - A. I. Stukachev
TI  - Generalized hyperarithmetical computability over structures
JO  - Algebra i logika
PY  - 2016
SP  - 769
EP  - 799
VL  - 55
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2016_55_6_a5/
LA  - ru
ID  - AL_2016_55_6_a5
ER  - 
%0 Journal Article
%A A. I. Stukachev
%T Generalized hyperarithmetical computability over structures
%J Algebra i logika
%D 2016
%P 769-799
%V 55
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2016_55_6_a5/
%G ru
%F AL_2016_55_6_a5
A. I. Stukachev. Generalized hyperarithmetical computability over structures. Algebra i logika, Tome 55 (2016) no. 6, pp. 769-799. http://geodesic.mathdoc.fr/item/AL_2016_55_6_a5/

[1] A. 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 Comput. Sci., 3959, eds. Jin-Yi Cai et al., Springer-Verlag, Berlin, 2006, 772–782 | DOI | MR | Zbl

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

[3] A. I. Stukachev, “O stepenyakh predstavimosti modelei. II”, Algebra i logika, 47:1 (2008), 108–126 | MR | Zbl

[4] A. I. Stukachev, “Teorema ob obraschenii skachka dlya polureshetok $\Sigma$-stepenei”, Sib. elektron. matem. izv., 6 (2009), 182–190 | MR | Zbl

[5] A. I. Stukachev, “A jump inversion theorem for the semilattices of $\Sigma$-degrees”, Sib. Adv. Math., 20:1 (2010), 68–74 | DOI | MR

[6] A. Stukachev, “Effective model theory: an approach via $\Sigma$-definability”, Effective mathematics of the uncountable, Lect. Notes Log., 41, eds. N. Greenberg et al., Cambridge Univ. Press, Cambridge; Assoc. Symb. Log. (ASL), Ithaca, NY, 2013, 164–197 | MR | Zbl

[7] A. I. Stukachev, “On processes and structures”, The nature of computation. Logic, algorithms, applications, Proc. 9th conf. comput. Europe, CiE 2013 (Milan, Italy, July 1–5, 2013), Lect. Notes Comput. Sci., 7921, eds. P. Bonizzoni et al., Springer-Verlag, Berlin, 2013, 393–402 | DOI | MR | Zbl

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

[9] J. Chisholm, “Effective model theory vs. recursive model theory”, J. Symb. Log., 55:3 (1990), 1168–1191 | DOI | MR | Zbl

[10] J. Barwise, Admissible sets and structures. An approach to definability theory, Perspec. Math. Logic, Springer-Velag, Berlin, 1975 | DOI | MR | Zbl

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

[12] D. S. Scott, “Outline of a mathematical theory of computation”, Proc. 4th Annual Princeton Conf. Inf. Sci. Syst., 1970, 165–176

[13] Yu. L. Ershov, Teoriya $A$-prostranstv, 12:4 (1973), 369–416

[14] Yu. L. Ershov, “Theory of domains and nearby”, Int. conf. formal methods progr. their appl. (Novosibirsk, Russia), Lec. Not. Comp. Sci., 735, Springer-Verlag, Berlin etc., 1993, 1–7 | DOI | MR

[15] A. I. Stukachev, “Protsessy i struktury na approksimatsionnykh prostranstvakh”, Algebra i logika, sdano v pechat

[16] Y. N. Moschovakis, Elementary induction on abstract structures, Stud. Logic Found. Math., 77, North-Holland Publ. Co., Amsterdam–London; Am. Elsevier Publ. Co., New York, 1974 | MR | Zbl

[17] A. I. Stukachev, “O kvaziregulyarnykh strukturakh vychislimykh signatur”, Sib. elektron. matem. izv., 11 (2014), 444–450 | Zbl

[18] D. Harel, First-order dynamic logic, Lect. Notes Comput. Sci., 68, Springer-Verlag, Berlin a.o., 1979 | DOI | MR | Zbl

[19] Yu. L. Ershov, “Dinamicheskaya logika nad dopustimymi mnozhestvami”, DAN SSSR, 273:5 (1983), 1045–1048 | MR | Zbl

[20] Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

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