##
Characterizing the Strongly
Jump-Traceable Sets via Randomness

Status: published in *Advances in Mathematics* 231 (2012) 2252 -
2293.

Availability: PDF

**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 Delta^{0}_{2} 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
Delta^{0}_{2}
1-random sets.

drh@math.uchicago.edu