Characterizing the Strongly
Jump-Traceable Sets via Randomness
Status: published in Advances
in Mathematics 231 (2012) 2252 -
2293.
Availability: journal
version and preprint
Abstract. We show that if a set is computable from every superlow
1-random set, then it is strongly jump-traceable. Together with a result
by Greenberg and Nies, this theorem shows that the c.e. strongly
jump-traceable sets are exactly the c.e. sets computable from every
superlow 1-random set.
We also prove the analogous result for superhighness: a c.e. set is
strongly jump-traceable if and only if it is computable from every
superhigh 1-random set.
Finally, we show that for each cost function c with the limit
condition
there is a 1-random Δ02 set Y such that
every Y-computable c.e. set obeys c. To do so, we connect
cost function strength and the
strength
of randomness notions. Together with a theorem by Greenberg and Nies, this
result gives a full correspondence
between obedience of cost functions and being computable from
Δ02
1-random sets.
drh@math.uchicago.edu