The degrees of bi-hyperhyperimmune sets

DOI10.1016/J.APAL.2013.10.004MaRDI QIDQ386147zbMATH OpenOpenAlexFDO

Authors Uri Andrews, Joseph S. Miller, Peter M. Gerdes

Publication date 16 December 2013

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2013.10.004

zbMATH Keywords

bi-hyperhyperimmunityescapingweak 2-genericity

Mathematics Subject Classification ID

Other Turing degree structures (03D28)

Review text

The study of the upward closure of collections of Turing degrees is an interesting topic of computability theory, beginning with the work of \textit{W. Miller} and \textit{D. A. Martin} [Z. Math. Logik Grundlagen Math. 14, 159--166 (1968; Zbl 0216.29102)] and several works of \textit{C. G. Jockusch jun.} [Z. Math. Logik Grundlagen Math. 15, 135--140 (1969; Zbl 0184.02002); J. Symb. Log. 34, 489--493 (1969; Zbl 0181.30601); Z. Math. Logik Grundlagen Math. 18, 285--287 (1972; Zbl 0257.02033); Isr. J. Math. 15, 332--335, (1973; Zbl 0279.02024)]. Thanks to these works we know of the upward closure of immune, bi-immune, hyperimmune, bi-hyperimmune and hyperhyperimmune Turing degrees. The case of the bi-hyperhyperimmune degrees remained open. In the paper under review, the authors close this gap by proving the upward closure of the bi-hyperhyperimmune Turing degrees. The strategy is to prove the following characterizations of the bi-hyperhyperimmune Turing degrees, from which the upward closure follows. Given a Turing degree \(\mathbf d\): \parindent=4ptNEWLINENEWLINE(1) \(\mathbf d\) computes a \(\Delta^0_2\) escaping function,NEWLINENEWLINE(2) \(\mathbf d\) computes a weakly 2-generic sequence,NEWLINENEWLINE(3) \(\mathbf d\) contains a blockwise bi-hyperhyperimmune set,NEWLINENEWLINE(4) \(\mathbf d\) contains a blockwise hyperhyperimmune set,NEWLINENEWLINE(5) \(\mathbf d\) contains a bi-hyperhyperimmune set. \vskip.2cm \parindent=0ptNEWLINENEWLINEThe paper ends by negatively answering to Question 6.6 posed in [\textit{B. F. Csima} and \textit{I. S. Kalimullin}, Math. Log. Q. 56, No. 1, 67--77 (2010; Zbl 1184.03025)].

Recommendations

• A characterization of the δ₂⁰ hyperhyperimmune sets
• Immunity properties and strong positive reducibilities
• Computational aspects of the hyperimmune-free degrees
• scientific article; zbMATH DE number 4004170
• Effectively hyperimmune sets and majorants

Cites work

• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Degree spectra and immunity properties
• scientific article; zbMATH DE number 4172959 (Why is no real title available?)
• scientific article; zbMATH DE number 3715539 (Why is no real title available?)
• Jump equivalence of the Δ₂⁰ hyperimmune sets
• Minimal degrees which are Σ₂⁰ but not Δ₂⁰
• Notions of weak genericity
• Properly ?2 minimal degrees and 0? complementation
• The degrees of bi‐immune sets
• The degrees of hyperhyperimmune sets
• The Degrees of Hyperimmune Sets
• Upward closure and cohesive degrees
• Upward Closure of bi‐Immune Degrees

Cited in

(7)

• On the degrees of constructively immune sets
• On the interplay between effective notions of randomness and genericity
• Immunity properties of the s-degrees
• A characterization of the δ₂⁰ hyperhyperimmune sets
• Computational aspects of the hyperimmune-free degrees
• A _2⁰ singleton of minimal arithmetic degree
• Immunity and hyperimmunity for sets of minimal indices

This page was built for publication: The degrees of bi-hyperhyperimmune sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386147)