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

Algebra Logika, 2022 Volume 61, Number 6, Pages 706–719 (Mi al2738)

Families of permutations and ideals of Turing degrees

A. S. Morozova, V. G. Puzarenkoa, M. Kh. Faizrahmanovb

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Kazan (Volga Region) Federal University

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

UDC: 510.5

Received: 19.04.2022
Revised: 13.10.2023

DOI: 10.33048/alglog.2022.61.603



© Steklov Math. Inst. of RAS, 2024