The Arithmetical Complexity of Dimension and Randomness

Original · EN

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ᵃlpha and DIMstrᵃlpha be the classes of all sequences of dimension alpha and of strong dimension alpha, respectively. We show that DIM⁰ is properly Pi⁰₂, and that for all Delta⁰₂-computable alpha in (0,1], DIMᵃlpha is properly Pi⁰₃. 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⁰₁ level. For all Delta⁰₂-computable alpha in [0,1), we show that DIMstrᵃlpha is properly in the Pi⁰₃ level of this hierarchy. We show that DIMstr¹ is properly in the Pi⁰₂ level of this hierarchy. We also prove that the class of Schnorr random sequences and the class of computably random sequences are properly Pi⁰₃.