Limits to joining with generics and randoms

DOI10.1142/9789814449274_0004zbMATH Open1364.03057arXiv1209.3282OpenAlexW2326799362MaRDI QIDQ5737985FDOQ5737985

Authors: Adam R. Day, Damir D. Dzhafarov 

Publication date: 31 May 2017

Published in: Proceedings of the 12th Asian Logic Conference (Search for Journal in Brave)

Abstract: Posner and Robinson (1981) proved that if $Ssubseteqomega$ is non-computable, then there exists a $Gsubseteqomega$ such that $SoplusGge{q}_T{G}^{\prime }$. Shore and Slaman (1999) extended this result to all $ninomega$, by showing that if $Sle{q}_{T}emptyse{t}^{(n-1)}$ then there exists a $G$ such that $SoplusGge{q}_T{G}^{(n)}$. Their argument employs Kumabe-Slaman forcing, and so the set they obtain, unlike that of the Posner-Robinson theorem, is not generic for Cohen forcing in any way. We answer the question of whether this is a necessary complication by showing that for all $ngeq1$, the set $G$ of the Shore-Slaman theorem cannot be chosen to be even weakly 2-generic. Our result applies to several other effective forcing notions commonly used in computability theory, and we also prove that the set $G$ cannot be chosen to be 2-random.

Full work available at URL: https://arxiv.org/abs/1209.3282

Recommendations

• Generics for computable Mathias forcing
• The Turing degrees below generics and randoms
• On the interplay between effective notions of randomness and genericity
• On Mathias generic sets
• Genericity for Mathias forcing over general Turing ideals

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Consistency and independence results (03E35) Other aspects of forcing and Boolean-valued models (03E40)

Cited In (4)

• On Mathias generic sets
• Generics for computable Mathias forcing
• Higher randomness and genericity
• Decomposing Borel functions using the Shore-Slaman join theorem

This page was built for publication: Limits to joining with generics and randoms

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