Generics for computable Mathias forcing.

*(English)*Zbl 1320.03072The 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.

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.

Reviewer: Merlin Carl (Konstanz)

##### MSC:

03D28 | Other Turing degree structures |

03E40 | Other aspects of forcing and Boolean-valued models |

03D32 | Algorithmic randomness and dimension |

03E75 | Applications of set theory |

##### Keywords:

effective forcing; Mathias forcing; computability theory; arithmetical forcing; forcing and computability
PDF
BibTeX
XML
Cite

\textit{P. A. Cholak} et al., Ann. Pure Appl. Logic 165, No. 9, 1418--1428 (2014; Zbl 1320.03072)

Full Text:
DOI

##### References:

[1] | Binns, S.; Kjos-Hanssen, B.; Lerman, M.; Solomon, R., On a conjecture of dobrinen and simpson concerning almost everywhere domination, J. Symbolic Logic, 71, 119-136, (2006) · Zbl 1103.03014 |

[2] | Cholak, P. A.; Dzhafarov, D. D.; Hirst, J. L., On Mathias generic sets, (Cooper; Barry, S.; etal., How the World Computes. Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012, Proceedings, Lecture Notes in Comput. Sci., vol. 7318, (2012), Springer Berlin), 129-138 · Zbl 1358.03054 |

[3] | Cholak, P. A.; Jockusch, C. G.; Slaman, T. A., On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic, 66, 1-55, (2001) · Zbl 0977.03033 |

[4] | Downey, R. G.; Hirschfeldt, D. R., Algorithmic randomness and complexity. theory and applications of computability, (2010), Springer New York · Zbl 1221.68005 |

[5] | A.R. Day, D.D. Dzhafarov, Limits to joining with generics and randoms, http://dx.doi.org/10.1142/9789814449274_0004. · Zbl 1364.03057 |

[6] | Dzhafarov, D. D.; Jockusch, C. G., Ramsey’s theorem and cone avoidance, J. Symbolic Logic, 74, 557-578, (2009) · Zbl 1166.03021 |

[7] | Jockusch, C. G., Degrees of generic reals, (Drake, F. R.; Wainer, S. S., Recursion Theory: Its Generalisation and Applications, London Math. Soc. Lecture Note Ser., vol. 45, (1980), Cambridge University Press Cambridge), 110-139 |

[8] | Jockusch, C. G.; Posner, D. B., Double jumps of minimal degrees, J. Symbolic Logic, 43, 715-724, (1978) · Zbl 0411.03034 |

[9] | Kurtz, S. A., Notions of weak genericity, J. Symbolic Logic, 48, 764-770, (1983) · Zbl 0549.03042 |

[10] | Mathias, A. R.D., Happy families, Ann. Math. Logic, 12, 59-111, (1977) · Zbl 0369.02041 |

[11] | Miller, A. W., Some properties of measure and category, Trans. Amer. Math. Soc., 266, 93-114, (1981) · Zbl 0472.03040 |

[12] | Seetapun, D.; Slaman, T. A., On the strength of Ramsey’s theorem. special issue: models of arithmetic, Notre Dame J. Form. Log., 36, 570-582, (1995) · Zbl 0843.03034 |

[13] | Shore, R. A., Lecture notes on Turing degrees, (Computational Prospects of Infinity II: AII Graduate Summer School, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., (2014), World Sci. Publ. Hackensack, NJ) |

[14] | Soare, R. I., Computability theory and applications. theory and applications of computability, (2014), Springer New York |

[15] | Soare, R. I., Sets with no subset of higher degree, J. Symbolic Logic, 34, 53-56, (1969) · Zbl 0182.01602 |

[16] | Yu, L., Lowness for genericity, Arch. Math. Logic, 45, 233-238, (2006) · Zbl 1148.03033 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.