On the degrees of constructively immune sets

2021/04/27 by Birns, Samuel D., Kjos-Hanssen, Bjørn
#03D25 #03D28 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2104.13322

Abstract

Xiang Li (1983) introduced what are now called constructively immune sets as an effective version of immunity. Such have been studied in relation to randomness and minimal indices, and we add another application area: numberings of the rationals. We also investigate the Turing degrees of constructively immune sets and the closely related Σ⁰₁-dense sets of Ferbus-Zanda and Grigorieff (2008).

Related

• On New Notions of Algorithmic Dimension, Immunity, and Medvedev Degree
• P-Immune Sets with Holes Lack Self-Reducibility Properties
• Π⁰₁ classes, strong minimal covers and hyperimmune-free degrees
• Immunity and Simplicity for Exact Counting and Other Counting Classes
• Degrees of Randomized Computability