Say that Y has the strong random anticupping property if there is a set A such that for every Martin-Loef random set R Y ≤ _T A ⊕ R => Y ≤ _T R (in this case A is an anticupping witness for Y). Nies has shown that every random Δ_2~0 set has the strong random anticupping property via a promptly simple anticupping witness. We show that every Δ_2~0 set has the random anticupping property via a promptly simple anticupping witness. Moreover, we prove the following stronger statement: for every non-computable Y ≤ _T φ′ there exists a promptly simple A such that Y ≤ _T A ⊕ R => A ≤ _T R for all Martin-Loef random sets R.
展开▼
