Limits to joining with generics and randoms

Abstract

Posner and Robinson (1981) proved that if $S\subseteq \omega$ is non-computable, then there exists a $G\subseteq \omega$ such that $S\oplus G{\ge }_T{G}^{\prime }$. Shore and Slaman (1999) extended this result to all $n\in \omega$, by showing that if $S{\nleqq }_T{\varnothing }^{(n-1)}$ then there exists a $G$ such that $S\oplus G{\ge }_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 $n\ge 1$, 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.

Submitted to "Proceedings of the 2011 Asian Logic Conference"

References in corpus (1)

• On Mathias generic sets