Limits to joining with generics and randoms

DOI10.1142/9789814449274_0004MaRDI QIDQ5737985zbMATHOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(4)

• Generics for computable Mathias forcing
• On Mathias generic sets
• 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)