2012/09/14 by Day, Adam R., Dzhafarov, Damir D.
#FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1209.3282
Posner and Robinson (1981) proved that if S ⊆ ω is non-computable, then there exists a G ⊆ ω such that S ⊕ G ≥T G'. Shore and Slaman (1999) extended this result to all n ∈ ω, by showing that if S \nleqT ∅(n-1) then there exists a G such that S ⊕ G ≥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 ≥ 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.