The Arithmetical Complexity of Dimension and Randomness
John M. Hitchcock, Jack H. Lutz, Sebastiaan A. Terwijn · Lecture notes in computer science · 2003
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) ∈ [0,1]. Let DIM α and ${\rm DIM}_{str}^\alpha$ be the classes of all sequences of dimension α and of strong dimension α, respectively. We show that DIM0 is properly $\Pi^{\rm 0}_{\rm 2}$ , and that for all $\Delta^{\rm 0}_{\rm 2}$ -computable α ∈ (0,1], DIM α is properly $\Pi^{\rm 0}_{\rm 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^{\rm 0}_{\rm 1}$ level. For all $\Delta^{\rm 0}_{\rm 2}$ -computable α ∈ [0,1), we show that ${\rm DIM}_{str}^\alpha$ is properly in the $\Pi^{\rm 0}_{\rm 3}$ level of this hierarchy. We show that ${\rm DIM}_{str}^1$ is properly in the $\Pi^{\rm 0}_{\rm 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^{\rm 0}_{\rm 3}$ .