Generics for computable Mathias forcing (Q2453068)

The method of forcing, originally developed in set theory to demonstrate the consistency of the negated continuum hypothesis, has by now found many applications in recursion theory, most commonly through arithmetical variants of Cohen forcing. This paper studies recursion-theoretical variants and applications of a different forcing notion, namely Mathias forcing. Roughly, Mathias forcing approximates a real number by fixing its bits on a finite initial segment and then giving an infinite set of natural numbers above that initial segment from which all further elements must be picked. The authors define a number of computable analogues, depending on the one hand on the definitional complexity of subsets of the forcing that a generic filter needs to intersect and on the other hand on whether only dense such sets must be intersected (weak genericity) or whether the filter must intersect such a set or the set of elements that have no strengthening in it (genericity). It is shown that generics for \(\Sigma_{n}\)-definable sets exist with jump below \(0^{(n)}\), that weak \(n\)-genericity is strictly weaker than \(n\)-genericity, which is in turn strictly weaker than weak \((n+1)\)-genericity, that weakly \(n\)-generics are hyperimmune relative to \(0^{(n-1)}\) and that \(n\)-generics form minimal pairs with \(0^{(n-1)}\). It turns out that, in some respects, the results are similar to these for Cohen generics: For example, if \(n\geq 2\) and \(G\) is \(n\)-generic, then \(G^{(n-1)}\) is Turing-equivalent with \(G^{\prime}\oplus 0^{(n)}\). On the other hand, it is shown that Mathias \(n\)-generic degrees cannot even be Cohen \(1\)-generic, though every Mathias \(n\)-generic computes some Cohen \(n\)-generic. The paper assumes acquaintance with arithmetical forcing and uses standard recursion-theoretical notation like \(W_{e}\) and terminology (e.g. `hyperimmune') without introducing it. Apart from that, proofs are carried out and the motivation is explained. It will be accessible to readers with a background in recursion theory.