1.3 Measures and Hausdorff Dimension - Algorithmic Information Theory

1.3.1 Measures¶

We begin by reviewing premeasures and their associated outer measures. For more details, refer to Reimann, 2008 and Rogers, 1970.

In the setting of Cantor space, it is customary to consider a premeasure on $2^\omega$ to be any non-negative mapping defined on the cylinder sets $\rho : \mathcal{B} \to [0, +\infty]$ . Of course, such maps are in one-to-one correspondence with maps defined on the finite binary strings $\rho: 2^{<\omega} \to [0, +\infty]$ . We may freely interchange between these two types by identifying any $\sigma \in 2^{<\omega}$ with its cylinder set $[\sigma] \in \mathcal{B}$ .

In metric spaces, there is a standard, general method (introduced as “Method II” in Rogers (1970)) to induce an outer measure from a given premeasure.

Theorem 1.3.2 (Theorem 15 of Rogers (1970))

Let $\rho$ be a premeasure on a collection $\mathcal{C}$ of subsets of a metric space $(\Omega, d)$ . Define for each $X \subseteq \Omega$ and $\delta > 0$ :

\begin{aligned} \mathcal{H}^\rho_\delta(X) &:= \inf_{(C_i)_{i \in \omega} \subseteq \mathcal{C}} \set{\sum_{i} \rho(C_i)}{\diam_d(C_i) \leq \delta, \bigcup_i C_i \supseteq X}, \quad \text{and} \quad \mathcal{H}^\rho(X) := \sup_{\delta > 0} \mathcal{H}^\rho_\delta(X). \end{aligned}

Then, $\mathcal{H}^\rho$ is an outer measure on $\Omega$ .

We call $\mathcal{H}^\rho$ the Method II outer measure associated to the premeasure $\rho$ . And for each $\delta > 0$ , we also call $\mathcal{H}^\rho_\delta$ the $\rho$ -dimensional $\delta$ -content measure.

In Rogers (1970), C. Rogers also defines an alternative “Method I” which differs from Method II in that it does not enforce any upper bound on the diameter of the cover elements used in the infimum:

\begin{aligned} \mathcal{H}^\rho_{\operatorname{I}}(X) &:= \inf_{(C_i)_{i \in \omega} \subseteq \mathcal{C}} \set{\sum_{i} \rho(C_i)}{\bigcup_i C_i \supseteq X}. \end{aligned}

This outer measure is also sometimes denoted $\mathcal{H}^\rho_\infty$ . While this method also produces an outer measure from a premeasure $\rho$ which agrees on null sets with $\mathcal{H}^\rho$ , Rogers points out that only the results of Method II can be guaranteed to be additive on sets which are separated by positive distance Rogers, 1970. We proceed with Method II as our preferred way to produce outer measures from premeasures.

Cantor space: $2^\omega$ , is a metric space when imbued with the standard metric,

\begin{aligned} d(x, y) := \begin{cases} 2^{-N} & \text{if $x \neq y$ and $N = \min\set{n \in \omega}{x(n) \neq y(n)}$},\\ 0 & \text{if $x = y$}. \end{cases} \end{aligned}

Note that this metric is compatible with the product topology generated by the cylinder sets in $\mathcal{B}$ .

1.3.2 Hausdorff Measures¶

An important class of outer measures on any metric space $(\Omega, d)$ are the Hausdorff outer measures, which are those Method II outer measures induced from premeasures whose values depend only on the diameter of the set. First, declare a dimension function to be any non-negative, non-decreasing, continuous-on-the-right function $h$ defined on all non-negative real numbers and satisfying $h(t) = 0 \iff t = 0$ . One may associate to any dimension function $h$ its Hausdorff premeasure defined on all $X \subseteq \Omega$ as follows:

\begin{aligned} \rho_h(X) := (h \circ \diam_d)(X). \end{aligned}

In Cantor space, $\rho_h(\sigma) = h\p{2^{- \operatorname{len}(\sigma)}}$ for any $\sigma \in 2^{<\omega}$ . So, any Hausdorff premeasure on $2^\omega$ is length-invariant, in that $\rho_h(\sigma)$ only depends on the length of $\sigma$ . Later, we will briefly focus on convex Hausdorff premeasures $\rho$ over Cantor space, which satisfy:

\begin{aligned} \rho(\sigma) \leq \rho(\sigma^\smallfrown 0) + \rho(\sigma^\smallfrown 1), \end{aligned}

for all $\sigma \in 2^{<\omega}$ . It is easy to see that all length-invariant, convex Hausdorff premeasures over $2^\omega$ are also strongly convex, meaning for all $\sigma \in 2^{<\omega}$ and $i \in \seq{0, 1}$ ,

\begin{aligned} \rho(\sigma ^\smallfrown i) \geq \frac{\rho(\sigma)}{2}. \end{aligned}

Essential to fractal geometry is the family of $s$ -dimensional Hausdorff premeasures $\rho_s := \rho_{h_s}$ , where $h_s : t \mapsto t^s$ is the dimension function associated to $s \geq 0$ . If $\delta > 0$ , let $\mathcal{H}^s_{\delta} := \mathcal{H}^{\rho_s}_\delta$ denote the $s$ -dimensional Hausdorff $\delta$ -content, and $\mathcal{H}^s := \mathcal{H}^{\rho_s}$ the $s$ -dimensional Hausdorff outer measure.

For any outer measure $\mu$ on a metric space $(\Omega, d)$ , we say a set $X \subseteq \Omega$ is $\mu$ -null if $\mu(X) = 0$ . Any $\mathcal{H}^s$ -null $X$ is also called $s$ -null.

Suppose $\mathcal{H}^s(X) < \infty$ for some $s \geq 0$ . This implies that $X$ is $s_+$ -null for any $s_+ > s$ too. Alternatively, if $\mathcal{H}^s(X) > 0$ for some $s \geq 0$ , then it must be that $\mathcal{H}^{s_-}(X) = \infty$ for all $0 \leq s_- < s$ . So, the shape of the function $s \mapsto \mathcal{H}^s(X)$ is either constant with value 0 or $\infty$ , or a step from $\infty$ to 0 (where, at the critical value of $s$ where the step occurs, $\mathcal{H}^s(X)$ could take on any value in $[0, \infty]$ ). This motivates the following definition for the Hausdorff dimension of a set $X$ Hausdorff, 1919Falconer, 1990:

\begin{aligned} \dim_{\operatorname{H}}(X) := \inf\set{s \geq 0}{\text{$X$ is $s$-null}}, \end{aligned}

(1.3.1)

or $+\infty$ if the infimum is taken over the empty set.

References¶

Reimann, J. (2008). Effectively closed sets of measures and randomness. Annals of Pure and Applied Logic, 156(1), 170–182. https://doi.org/10.1016/j.apal.2008.06.015
Rogers, C. A. (1970). Hausdorff Measures. Cambridge Mathematical Library.
Hausdorff, Felix. (1919). Dimension und äußeres Maß. Mathematische Annalen, 79, 157–179. http://eudml.org/doc/158784
Falconer, K. (1990). Fractal geometry - mathematical foundations and applications. (p. I–XXII, 1–288). Wiley.