Geodesic
Families of permutations and ideals of Turing degrees
Algebra i logika, Tome 61 (2022) no. 6, pp. 706-719.

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

Families ${\mathcal P}_{\mathrm I}$ consisting of permutations of the natural numbers $\omega$ whose degrees belong to an ideal $\mathrm I$ of Turing degrees, as well as their jumps ${\mathcal P}'_{\mathrm I}$, are studied. For any countable Turing ideal $\mathrm I$, the degree spectra of families ${\mathcal P}_{\mathrm I}$ and their jumps ${\mathcal P}'_{\mathrm I}$ are described. For some ideals $\mathrm I$ generated by c.e. degrees, the spectra of families ${\mathcal P}_{\mathrm I}$ are defined.
Keywords: computable permutation, family of permutations, jump, Turing degree, ideal of Turing degrees, degree spectra. 
@article{AL_2022_61_6_a3,
     author = {A. S. Morozov and V. G. Puzarenko and M. Kh. Faizrahmanov},
     title = {Families of permutations and ideals of {Turing} degrees},
     journal = {Algebra i logika},
     pages = {706--719},
     publisher = {mathdoc},
     volume = {61},
     number = {6},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2022_61_6_a3/}
}
TY  - JOUR
AU  - A. S. Morozov
AU  - V. G. Puzarenko
AU  - M. Kh. Faizrahmanov
TI  - Families of permutations and ideals of Turing degrees
JO  - Algebra i logika
PY  - 2022
SP  - 706
EP  - 719
VL  - 61
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2022_61_6_a3/
LA  - ru
ID  - AL_2022_61_6_a3
ER  - 
%0 Journal Article
%A A. S. Morozov
%A V. G. Puzarenko
%A M. Kh. Faizrahmanov
%T Families of permutations and ideals of Turing degrees
%J Algebra i logika
%D 2022
%P 706-719
%V 61
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2022_61_6_a3/
%G ru
%F AL_2022_61_6_a3
A. S. Morozov; V. G. Puzarenko; M. Kh. Faizrahmanov. Families of permutations and ideals of Turing degrees. Algebra i logika, Tome 61 (2022) no. 6, pp. 706-719. http://geodesic.mathdoc.fr/item/AL_2022_61_6_a3/

[1] C. G. Jockusch, jun., “Degrees in which the recursive sets are uniformly recursive”, Can. J. Math., 24:6 (1972), 1092–1099 | DOI | MR | Zbl

[2] R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspect. Math. Log., Omega Series, Springer-Verlag, Berlin etc., 1987 ; R. I. Soar, Vychislimo perechislimye mnozhestva i stepeni. Izuchenie vychislimykh funktsii i vychislimo perechislimykh mnozhestv, Kazanskoe matem. ob-vo, Kazan, 2000 | DOI | MR

[3] A. S. Morozov, “Perestanovki i neyavnaya opredelimost”, Algebra i logika, 27:1 (1988), 19–36 | MR

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

[5] V. A. Rudnev, “O suschestvovanii neotdelimoi pary v rekursivnoi teorii dopustimykh mnozhestv”, Algebra i logika, 27:1 (1988), 48–56 | MR

[6] A. S. Morozov, V. G. Puzarenko, “O $\Sigma$-podmnozhestvakh naturalnykh chisel”, Algebra i logika, 43:3 (2004), 291–320 | MR | Zbl

[7] A. Montalbán, Computable structure theory. Within the arithmetic, Perspect. Log., Cambridge Univ. Press, Cambridge, Urbana, IL, 2021 | MR

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

[9] V. G. Puzarenko, “Ob odnoi svodimosti na dopustimykh mnozhestvakh”, Sib. matem. zh., 50:2 (2009), 415–429 | MR

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

[11] A. Montalbán, “Notes on the jump of a structure”, Mathematical theory and computational practice, 5th conf. on computability in Europe (CiE 2009), Proc. (Heidelberg, Germany, July 19–24, 2009), Lect. Notes Comput. Sci., 5635, eds. K. Ambos-Spies et al., Springer-Verlag, Berlin, 2009, 372–378 | DOI | MR | Zbl

[12] A. A. Soskova, I. N. Soskov, “A jump inversion theorem for the degree spectra”, J. Log. Comput., 19:1 (2009), 199–215 | DOI | MR | Zbl

[13] V. G. Puzarenko, “Hepodvizhnye tochki operatora skachka”, Algebra i logika, 50:5 (2011), 615–646 | MR | Zbl

[14] Yu. L. Ershov, Opredelimost i vychislimost, Sibirskaya shkola algebry i logiki, Nauch. kn., Novosibirsk ; 2-е изд., испр. и доп., Экономика, М., 2000 | MR

[15] J. Barwise, Admissible sets and structures. An approach to definability theory, Reprint of the 1975 original published by Springer, Perspec. Math. Log., Cambridge Univ. Press, Cambridge; Assoc. Symb. Log. (ASL), Urbana, IL, 2016 | Zbl

[16] Yu. L. Ershov, V. G. Puzarenko, A. I. Stukachev, “$\mathbb {HF}$-Computability”, Computability in context. Computation and logic in the real world, ed. S. B. Cooper, World Scientific, London, 2011, 173–248 | MR

[17] G. Barmpalias, A. Nies, “Upper bounds on ideals in the computably enumerable Turing degrees”, Ann. Pure Appl. Logic, 162:6 (2011), 465–473 | DOI | MR | Zbl

[18] A. Nies, Computability and randomness, Oxf. Logic Guides, 51, Oxford Univ. Press, Oxford, 2009 | MR | Zbl

[19] A. Nies, “Lowness properties and randomness”, Adv. Math., 197:1 (2005), 274–305 | DOI | MR | Zbl

[20] K. M. Ng, “On strongly jump traceable reals”, Ann. Pure App. Logic, 154:1 (2008), 51–69 | DOI | MR | Zbl

[21] D. Diamondstone, N. Greenberg, D. Turetsky, “Inherent enumerability of strong jump-traceability”, Trans. Am. Math. Soc., 367:3 (2015), 1771–1796 | DOI | MR | Zbl

[22] S. Schwarz, “Index sets related to prompt simplicity”, Ann. Pure App. Logic, 42:3 (1989), 243–254 | DOI | MR | Zbl