Generics for computable Mathias forcing
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.
- Algorithmic randomness and complexity.
- Double jumps of minimal degrees
- Happy families
- scientific article; zbMATH DE number 3715539 (Why is no real title available?)
- Limits to joining with generics and randoms
- Lowness for genericity
- Notions of weak genericity
- On a conjecture of Dobrinen and Simpson concerning almost everywhere domination
- On Mathias generic sets
- On the strength of Ramsey's theorem
- On the strength of Ramsey's theorem for pairs
- Ramsey's theorem and cone avoidance
- Sets with no subset of higher degree
- Some Properties of Measure and Category
- A note on the strong and weak generative powers of formal systems
- A variant of Mathias forcing that preserves \(\mathsf{ACA}_0\)
- On the degrees of constructively immune sets
- Pigeons do not jump high
- The uniform content of partial and linear orders
- Coloring trees in reverse mathematics
- Arithmetical Sacks forcing
- On genericity and Ershov's hierarchy
- On Mathias generic sets
- Ramsey's theorem for singletons and strong computable reducibility
- Controlling iterated jumps of solutions to combinatorial problems
- Notions of weak genericity
- Reals n-generic relative to some perfect tree
- Forcing and reducibilities. III. Forcing in fragments of set theory
- Template iterations with non-definable ccc forcing notions
- Genericity for Mathias forcing over general Turing ideals
- Canonical immunity and genericity
- Thin set theorems and cone avoidance
- Open questions about Ramsey-type statements in reverse mathematics
- Any FIP real computes a 1-generic
- Limits to joining with generics and randoms
- Needed reals and recursion in generic reals
This page was built for publication: Generics for computable Mathias forcing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453068)
