Generic degrees are complemented

DOI10.1016/0168-0072(93)90096-VMaRDI QIDQ685063zbMATH OpenFDO

Authors Masahiro Kumabe

Publication date 22 September 1993

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

Full work available at URL https://doi.org/10.1016/0168-0072(93)90096-V

zbMATH Keywords

\(n\)- generic setdegrees of unsolvabilitydegrees recursive in \(n\)-generic degreesstrong complementednessTuring degreeupper semilattice of degrees

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Review text

A set \(A \subseteq \omega\) is \(n\)-generic if it is generic for \(n\)- quantifier arithmetic; that is, for every \(\Sigma^ 0_ n\) set of strings \(S\), there is some initial segment \(\sigma\) of (the characteristic function of) \(A\) that has no extension in \(S\) unless \(\sigma\) is in \(S\) itself. A Turing degree is \(n\)-generic if it contains an \(n\)-generic set. This paper proves a strong complementedness result for degrees that are recursive in \(n\)-generic degrees. For any \(n \geq 2\) let \(a\) be an \(n\)-generic degree and \(b\) a nonrecursive degree \(<a\). Then there are \(n\)-generic degrees \(c<a\) and \(d<b\) such that for any nonrecursive \(e \leq c\) and any \(f\) with \(d \leq f<a\), we have \(e \cup f=a\) and \(e \cap f=0\). By setting \(f=b\) it follows at once that the upper semilattice of degrees \(\leq a\) is complemented. The result answers a question raised by Jockusch in 1980.

Recommendations

• Relative recursive enumerability of generic degrees
• Notions of weak genericity
• Complementation in the Turing degrees
• scientific article; zbMATH DE number 4081537
• Relative definability of n-generics

Cites work

• A theorem on minimal degrees
• Banach–Mazur games, comeager sets and degrees of unsolvability
• Complementation in the Turing degrees
• Definability in the Turing degrees
• Degrees which do not bound minimal degrees
• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 3916242 (Why is no real title available?)
• scientific article; zbMATH DE number 3715539 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• Initial segments of the degrees of unsolvability Part II: minimal degrees
• Minimal Covers and Arithmetical Sets
• Minimal degrees recursive in 1-generic degrees
• On degrees of recursive unsolvability
• Some applications of the notions of forcing and generic sets
• The degrees below a 1-generic degree < 0′
• The recursively enumerable degrees are dense
• The upper semilattice of degrees ≤ 0′ is complemented
• ∑1-Density and Turing Degrees

Cited in

(14)

• The generic degrees of density-1 sets, and a characterization of the hyperarithmetic reals
• The Turing degrees below generics and randoms
• Complementation in the Turing degrees
• Notions of weak genericity
• scientific article; zbMATH DE number 4081537 (Why is no real title available?)
• Degrees bounding minimal degrees
• Relative recursive enumerability of generic degrees
• Minimal upper bounds for arithmetical degrees
• The information content of typical reals
• Relative definability of n-generics
• Generalized high degrees have the complementation property
• The finite intersection principle and genericity
• Degree Monotone Paths
• Comparatives Bring a Degree-Based NPI Licenser

This page was built for publication: Generic degrees are complemented

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