The Arithmetical Complexity of Dimension and Randomness
<|reference_start|>The Arithmetical Complexity of Dimension and Randomness: Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1].   Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong dimension alpha, respectively. We show that DIM^0 is properly Pi^0_2, and that for all Delta^0_2-computable alpha in (0,1], DIM^alpha is properly Pi^0_3.   To classify the strong dimension classes, we use a more powerful effective Borel hierarchy where a co-enumerable predicate is used rather than a enumerable predicate in the definition of the Sigma^0_1 level. For all Delta^0_2-computable alpha in [0,1), we show that DIMstr^alpha is properly in the Pi^0_3 level of this hierarchy. We show that DIMstr^1 is properly in the Pi^0_2 level of this hierarchy.   We also prove that the class of Schnorr random sequences and the class of computably random sequences are properly Pi^0_3.<|reference_end|>
@article{hitchcock2004the,
    title={The Arithmetical Complexity of Dimension and Randomness},
    author={John M. Hitchcock, Jack H. Lutz, and Sebastiaan A. Terwijn},
    journal={arXiv preprint arXiv:cs/0408043},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0408043},
    primaryClass={cs.LO cs.CC}
}