Groups of permutations and ideals of Turing degrees

A. S. Morozov ; V. G. Puzarenko ; M. Kh. Faizrahmanov

Algebra i logika, Tome 63 (2024) no. 2, pp. 209-224

Résumé

We study degrees and degree spectra of groups $\mathfrak{G}_{\mathrm{I}}$ defined on a set of permutations on the natural numbers $\omega$ whose degrees belong to a Turing ideal $\mathrm{I}$. A necessary condition and a sufficient condition are stated which specify whether an arbitrary Turing degree belongs to the degree spectrum of a group $\mathfrak{G}_{\mathrm{I}}$. Nonprincipal ideals $\mathrm{I}$ for which the group $\mathfrak{G}_{\mathrm{I}}$ has or does not have a degree are exemplified.

Détail

Keywords: computable permutation, Turing degree, Turing ideal, degree of permutation group, degree spectrum.
Mots-clés : permutation group

Bibliographie

[1] C. J. Ash, J. Knight, Computable structures and the hyperarithmetical hierarchy, Stud. Logic Found. Math., 144, Elsevier, Amsterdam, 2000

[2] A. Montalb\'{a n}, Computable structure theory: Within the arithmetic, Cambridge Univ. Press, Cambridge, 2021

[3] L. J. Richter, “Degrees of structures”, J. Symb. Log., 46:4 (1981), 723–731

[4] A. T. Nurtazin, “O konstruktivnykh gruppakh”, Tez. 4-i vsesoyuz. konf. matem. logike, Kishinev, 1976, 106

[5] V. V. Kozminykh, “O predstavlenii chastichno rekursivnykh funktsii v vide superpozitsii”, Algebra i logika, 11:3 (1972), 270–294

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

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

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

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

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

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

[12] A. Montalb\'{a n}, “Notes on the jump of a structure”, Proceedings of the 5th Conference on Computability in Europe: Mathematical Theory and Computational Practice, Lect. Notes Comput. Sci., 5635, 2009, 372–378

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

[14] Yu. L. Ershov, Opredelimost i vychislimost, Ekonomika; Novosibirsk, Nauch. kn., M., 2000

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

[16] A. S. Morozov, V. G. Puzarenko, M. Kh. Faizrakhmanov, “Semeistva perestanovok i idealy tyuringovykh stepenei”, Algebra i logika, 61:6 (2022), 706–719

[17] R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspect. math. logic, Springer-Verlag, Berlin–Heidelberg–NY, 1987

[18] J. Barwise, Admissible sets and structures, Perspect. Logic, 7, Cambridge Univ. Press, Cambridge, 2017

[19] Yu. L. Ershov, V. G. Puzarenko, A. I. Stukachev, “HF-Computability”, Computability in Context. Computation and Logic in the Real World, World Sci., London, 2011, 169–242

[20] A. Nies, Computability and randomness, Oxford Univ. Press, NY, 2009

[21] A. Nies, “Lowness properties and randomness”, Adv. Math., 197 (2005), 274–305

[22] I. Sh. Kalimullin, V. G. Puzarenko, “O printsipakh vychislimosti na dopustimykh mnozhestvakh”, Matem. tr., 7:2 (2004), 35–71

[23] C. J. Jockusch, Jr., “Degrees of generic sets”, Cambridge Univ. Press, London Math. Soc. Lect. Notes, 45, Cambridge, 1980, 110–139

[24] R. G. Downey, D. R. Hirschfeldt, Algorithmic randomness and complexity, Theory Appl. Comput., Springer, Berlin–NY, 2010