Lowness for effective Hausdorff dimension

摘要

We examine the sequences A that are low for dimension, i.e. those for which the effective (Hausdorff) dimension relative to A is the same as the unrelativized effective dimension. Lowness for dimension is a weakening of lowness for randomness, a central notion in effective randomness. By considering analogues of characterizations of lowness for randomness, we show that lowness for dimension can be characterized in several ways. It is equivalent to lowishness for randomness, namely, that every Martin-Lof random sequence has effective dimension 1 relative to A, and lowishness for K, namely, that the limit of K-A(n)/K(n) is 1. We show that there is a perfect Pi(0)(1)-class of low for dimension sequences. Since there are only countably many low for random sequences, many more sequences are low for dimension. Finally, we prove that every low for dimension is jump-traceable in order n(epsilon), for any epsilon > 0.