Degrees of sets having no subsets of higher m- and tt-degree

Article type: Research Article

Authors: Cintioli, Patrizio^{; *}

Affiliations: School of Sciences and Technology, Mathematics Division, University of Camerino, 62032 Camerino, Italy. patrizio.cintioli@unicam.it

Correspondence: [*] Corresponding author. patrizio.cintioli@unicam.it.

Abstract: We consider sets without subsets of higher m- and tt-degree, that we call m-introimmune and tt-introimmune sets respectively. We study how they are distributed in partially ordered degree structures. We show that: each computably enumerable weak truth-table degree contains m-introimmune Π10-sets;each hyperimmune degree contains bi-m-introimmune sets. Finally, from known results we establish that each degree a with a′⩾0″ covers a degree containing tt-introimmune sets.

Keywords: Many-one reducibility, truth-table reducibility, weak truth-table reducibility, computably enumerable degrees, hyperimmune degrees

DOI: 10.3233/COM-200296

Journal: Computability, vol. 10, no. 3, pp. 235-255, 2021