Geodesic
Properties of $s\Sigma$-reducibility
Algebra i logika, Tome 53 (2014) no. 5, pp. 625-642.

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

We couch the definition of $s\Sigma$-reducibility on structures, describe some properties of $s\Sigma$-reducibility, and also exemplify explicitly how to use it. In particular, we consider natural expansions of structures such as Morleyization and Skolemization. Previously, a class of quasiregular structures was defined to be a class of fixed points of Morleyization with respect to $s\Sigma$-reducibility, extending the class of models of regular theories and the class of effectively model-complete structures. It was proved that an $\mathrm{HF}$-superstructure over a quasiregular structure is quasiresolvent and, consequently, has a universal $\Sigma$-function and possesses the reduction property. Here we show that an $\mathrm{HF}$-superstructure over a quasiregular structure has the $\Sigma$-uniformization property iff with respect to $s\Sigma$-reducibility this structure is a fixed point for some of its Skolemizations with an extra property, that of well-definededness. In this case an $\mathrm{HF}$-superstructure and a Moschovakis superstructure over a given structure are $s\Sigma$-equivalent.
Keywords: generalized computability, model theory, model completeness, decidability, uniformization property. 
@article{AL_2014_53_5_a4,
     author = {A. I. Stukachev},
     title = {Properties of $s\Sigma$-reducibility},
     journal = {Algebra i logika},
     pages = {625--642},
     publisher = {mathdoc},
     volume = {53},
     number = {5},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2014_53_5_a4/}
}
TY  - JOUR
AU  - A. I. Stukachev
TI  - Properties of $s\Sigma$-reducibility
JO  - Algebra i logika
PY  - 2014
SP  - 625
EP  - 642
VL  - 53
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2014_53_5_a4/
LA  - ru
ID  - AL_2014_53_5_a4
ER  - 
%0 Journal Article
%A A. I. Stukachev
%T Properties of $s\Sigma$-reducibility
%J Algebra i logika
%D 2014
%P 625-642
%V 53
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2014_53_5_a4/
%G ru
%F AL_2014_53_5_a4
A. I. Stukachev. Properties of $s\Sigma$-reducibility. Algebra i logika, Tome 53 (2014) no. 5, pp. 625-642. http://geodesic.mathdoc.fr/item/AL_2014_53_5_a4/

[1] A. I. Stukachev, “Teorema ob uniformizatsii v $\mathrm{HF(R)}$”, Materialy XXXIV mezhdunarodnoi nauchnoi studencheskoi konferentsii “Student i nauchno-tekhnicheskii progress: Matematika”, NGU, Novosibirsk, 1996, 83 | MR

[2] A. I. Stukachev, “Uniformization property in hereditary finite superstructures”, Sib. Adv. Math., 7:1 (1997), 123–131 | MR | Zbl

[3] A. I. Stukachev, “Teorema ob uniformizatsii v nasledstvenno konechnykh nadstroikakh”, Obobschënnaya vychislimost i opredelimost, Vychisl. sist., 161, In-t matem. SO RAN, Novosibirsk, 1998, 3–14 | MR

[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 Logic, 41, 2013, 164–197 | MR

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

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

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

[10] I. N. Soskov, Abstraktna izchislimost i opredelimost: v'nshen podkhod, Dis. d-r matem. nauk, Sofiya, 2000

[11] V. Baleva, “The jump operation for structure degrees”, Arch. Math. Logic, 45:3 (2006), 249–265 | DOI | MR | Zbl

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

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

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

[15] A. J. Wilkie, “Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function”, J. Am. Math. Soc., 9:4 (1996), 1051–1094 | DOI | MR | Zbl

[16] A. Macintyre, A. Wilkie, “On the decidability of the real exponential field”, Kreiseliana, About and around Georg Kreisel, ed. P. Odifreddi, A K Peters, Wellesley, MA, 1996, 441–467 | MR | Zbl

[17] L. van den Dries, “Algebraic theories with definable Skolem functions”, J. Symb. Log., 49:2 (1984), 625–629 | DOI | MR | Zbl

[18] M. V. Korovina, “Ob universalnoi rekursivnoi funktsii i abstraktnykh mashinakh na veschestvennykh chislakh so spisochnoi nadstroikoi”, Strukturnye i algoritmicheskie svoistva vychislimosti, Vychisl. sist., 156, In-t matem. SO RAN, Novosibirsk, 1996, 24–43 | MR

[19] S. S. Goncharov, Yu. L. Ershov, D. I. Sviridenko, “Semantic programming”, Information processing, Proc. IFIP 10th World Comput. Congr. (Dublin/Irel. 1986), IFIP Congr. Ser., 10, 1986, 1113–1120 | Zbl

[20] I. V. Ashaev, V. Ya. Belyaev, A. G. Myasnikov, “Podkhody k teorii obobschennoi vychislimosti”, Algebra i logika, 32:4 (1993), 349–386 | MR | Zbl

[21] S. A. Aleksandrova, “Problema uniformizatsii dlya $\Sigma$-predikatov v nasledstvenno konechnoi spisochnoi nadstroike nad polem deistvitelnykh chisel s eksponentoi”, Algebra i logika, 53:1 (2014), 3–14 | MR | Zbl