Generic degrees are complemented (Q685063): Difference between revisions

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.