RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2024 Volume 63, Number 2, Pages 209–224 (Mi al2802)

Groups of permutations and ideals of Turing degrees

A. S. Morozovab, V. G. Puzarenkoab, M. Kh. Faizrahmanovcd

a Novosibirsk State University
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
c Scientific-Educational Mathematical Center of Volga Federal District
d Kazan (Volga Region) Federal University

Abstract: 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.

Keywords: computable permutation, permutation group, Turing degree, Turing ideal, degree of permutation group, degree spectrum.

UDC: 510.5

Received: 14.09.2022
Revised: 06.12.2024

DOI: 10.33048/alglog.2024.63.205


 English version:
Algebra and Logic, 2024, 63:2, 141–152


© Steklov Math. Inst. of RAS, 2025