Lowness for Effective Hausdorff Dimension

Daniel Turetsky, Steffen Lempp, Joe Miller, Rebecca Weber, Keng Meng Ng

    Veröffentlichungen: Beitrag in FachzeitschriftArtikelPeer Reviewed


    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-Löf random sequence has effective dimension 1 relative to A, and lowishness for K, namely, that the limit of KA(n)/K(n) is 1.
    We show that there is a perfect Π01-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ε, for any ε > 0.
    FachzeitschriftJournal of Mathematical Logic
    PublikationsstatusVeröffentlicht - 2014

    ÖFOS 2012

    • 101013 Mathematische Logik