Geodesic
On limitwise monotonic reducibility of $\Sigma_2^0$-sets
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 1, pp. 22-30
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In this paper, we study the properties of lm-reducibility of sets belonging to the class of $\Sigma_2^0$-sets. In particular, we prove the existence of incomparable $\Sigma_2^0$-sets with respect to lm-reducibility. In addition, we construct an infinite uniform sequence of incomparable $\Sigma_2^0$-sets relative to lm-reducibility and show that every countable partial order can be embedded into the class of all lm-degrees of $\Sigma_2^0$-sets.
Keywords: computable functions, $\Sigma_2^0$-sets, limitwise monotonic functions, limitwise monotonic sets. 
@article{UZKU_2014_156_1_a2,
     author = {D. Kh. Zainetdinov and I. Sh. Kalimullin},
     title = {On limitwise monotonic reducibility of $\Sigma_2^0$-sets},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {22--30},
     year = {2014},
     volume = {156},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2014_156_1_a2/}
}
TY  - JOUR
AU  - D. Kh. Zainetdinov
AU  - I. Sh. Kalimullin
TI  - On limitwise monotonic reducibility of $\Sigma_2^0$-sets
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2014
SP  - 22
EP  - 30
VL  - 156
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/UZKU_2014_156_1_a2/
LA  - ru
ID  - UZKU_2014_156_1_a2
ER  - 
%0 Journal Article
%A D. Kh. Zainetdinov
%A I. Sh. Kalimullin
%T On limitwise monotonic reducibility of $\Sigma_2^0$-sets
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2014
%P 22-30
%V 156
%N 1
%U http://geodesic.mathdoc.fr/item/UZKU_2014_156_1_a2/
%G ru
%F UZKU_2014_156_1_a2
D. Kh. Zainetdinov; I. Sh. Kalimullin. On limitwise monotonic reducibility of $\Sigma_2^0$-sets. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 1, pp. 22-30. http://geodesic.mathdoc.fr/item/UZKU_2014_156_1_a2/

[1] Soar R. I., Vychislimo perechislimye mnozhestva i stepeni. Izuchenie vychislimykh funktsii i vychislimo perechislimykh mnozhestv, Per. s angl., Kazan. matem. o-vo, Kazan, 2000, 576 pp. | MR | Zbl

[2] Kalimullin I. Sh., Puzarenko V. G., “O svodimosti na semeistvakh”, Algebra i logika, 48:1 (2009), 31–53 | MR | Zbl

[3] Kalimullin I. Sh., Faizrakhmanov M. Kh., “Spektry predelnoi monotonnosti $\Sigma_2^0$-mnozhestv”, Uchen. zap. Kazan. un-ta. Ser. Fiz.-matem. nauki, 154, no. 2, 2012, 107–116

[4] Kalimullin I., Khoussainov B., Melnikov A., “Limitwise monotonic sequences and degree spectra of structures”, Proc. Amer. Math. Soc., 141:9 (2013), 3275–3289 | DOI | MR | Zbl

[5] Khoussainov B., Nies A., Shore R., “Computable models of theories with few models”, Notre Dame J. Formal Logic, 38:2 (1997), 165–178 | DOI | MR | Zbl