Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4609141 | Journal of Complexity | 2006 | 8 Pages |
Abstract
Say that Y has the strong random anticupping property if there is a set A such that for every Martin–Löf random set RY⩽TA⊕R⇒Y⩽TRY⩽TA⊕R⇒Y⩽TR(in this case A is an anticupping witness for Y ). Nies has shown that every random Δ20 set has the strong random anticupping property via a promptly simple anticupping witness. We show that every Δ20 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∅′Y⩽T∅′ there exists a promptly simple A such thatY⩽TA⊕R⇒A⩽TRY⩽TA⊕R⇒A⩽TRfor all Martin–Löf random sets R.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis
Authors
George Barmpalias,