Measure on Cantor space

A sequence $X \in \cs$ chosen by tossing a fair coin for each bit belongs to a cylinder $[\sigma]$ with probability $2^{-|\sigma|}$. The uniform measure extends this assignment to a large family of classes, and a property is typical if the class of sequences without it has measure $0$. Random sequences, in the sense of this course, are those that avoid every null class that can be described effectively. This lesson collects the facts about the measure that the course uses, and computes how complex the measure of an effective class is.

We use the notation of Trees and Π⁰₁ classes: $[\sigma]$ is the cylinder of the sequences extending $\sigma$, $[W]^{\prec} = \bigcup_{\sigma \in W} [\sigma]$ the open class generated by a set of strings $W$, and $2^n$ the set of strings of length $n$.

1.1 The uniform measure

The Borel classes are the classes obtained from the cylinders by complements and countable unions, iterated transfinitely; they include the open, closed, $\Pi^0_2$ and all arithmetical classes.

Fact 1.1 (Lebesgue, Carathéodory).#

There is a unique function $\lambda$ from the Borel classes of $\cs$ to $[0, 1]$ such that $\lambda([\sigma]) = 2^{-|\sigma|}$ for every string $\sigma$ and $\lambda$ is countably additive: if the classes $\mathcal B_n$ are pairwise disjoint, then $\lambda(\bigcup_n \mathcal B_n) = \sum_n \lambda(\mathcal B_n)$. Moreover $\lambda$ is outer regular: for every Borel class $\mathcal B$ and every $\varepsilon > 0$, there is an open class $\mathcal U \supseteq \mathcal B$ with $\lambda(\mathcal U) \leq \lambda(\mathcal B) + \varepsilon$.

This is a theorem of measure theory, admitted here: the existence is Carathéodory’s extension theorem, and outer regularity holds for every finite Borel measure on a metrizable space. See Kechris, Classical Descriptive Set Theory, Section 17, or any textbook on measure theory. The function $\lambda$ is the Lebesgue measure, or uniform measure, on $\cs$; it is the image of the Lebesgue measure on $[0, 1]$ under the binary expansion.

The following consequences of countable additivity are used constantly:

1. Monotonicity: if $\mathcal A \subseteq \mathcal B$, then $\lambda(\mathcal A) \leq \lambda(\mathcal B)$, and $\lambda(\mathcal B \setminus \mathcal A) = \lambda(\mathcal B) - \lambda(\mathcal A)$.
2. Subadditivity: $\lambda(\bigcup_n \mathcal B_n) \leq \sum_n \lambda(\mathcal B_n)$ for every sequence of Borel classes.
3. Continuity: if $\mathcal B_0 \subseteq \mathcal B_1 \subseteq \cdots$, then $\lambda(\bigcup_n \mathcal B_n) = \sup_n \lambda(\mathcal B_n)$; if $\mathcal B_0 \supseteq \mathcal B_1 \supseteq \cdots$, then $\lambda(\bigcap_n \mathcal B_n) = \inf_n \lambda(\mathcal B_n)$.

For (2), the classes $\mathcal B_n \setminus \bigcup_{m < n} \mathcal B_m$ are pairwise disjoint, have the same union, and are contained in the classes $\mathcal B_n$. For (3), the first statement applies additivity to the differences $\mathcal B_{n+1} \setminus \mathcal B_n$, and the second follows by complementation.

1.2 Open classes

Two cylinders are either disjoint or contained in one another: $[\sigma] \cap [\tau] = \emptyset$ unless $\sigma$ and $\tau$ are comparable. A set of strings $W$ is prefix-free if no element of $W$ is a proper prefix of another; the cylinders $[\sigma]$, $\sigma \in W$, are then pairwise disjoint, and by additivity

$$\lambda([W]^{\prec}) = \sum_{\sigma \in W} 2^{-|\sigma|}.$$

For an arbitrary set $W$, subadditivity gives only $\lambda([W]^{\prec}) \leq \sum_{\sigma \in W} 2^{-|\sigma|}$. Every open class has a prefix-free generator: the set of $\sigma \in W$ with no proper prefix in $W$ generates $[W]^{\prec}$. This set is not c.e. in general when $W$ is, but another prefix-free generator is.

Lemma 1.2.#

From an index of a c.e. set of strings $W$, one computes an index of a c.e. prefix-free set $W'$ with $[W']^{\prec} = [W]^{\prec}$ and such that every element of $W'$ extends an element of $W$.

Proof of Lemma 1.2.

Enumerate $W$ as $\sigma_0, \sigma_1, \dots$ (if $W$ is finite, possibly empty, the stages after the last element of $W$ add nothing), and build $W'$ as an increasing union of finite prefix-free sets $W'_s$, with $W'_0 = \emptyset$ and $[W'_s]^{\prec} = [\{ \sigma_i : i < s \}]^{\prec}$. At stage $s$, let $L$ be the maximum of $|\sigma_s|$ and of the lengths of the elements of $W'_s$, and let $W'_{s+1}$ be $W'_s$ together with every string $\tau \succeq \sigma_s$ of length $L$ that has no prefix in $W'_s$.

A new string $\tau$ has no prefix in $W'_s$, and no element of $W'_s$ properly extends it, since these elements have length at most $L = |\tau|$; distinct new strings have the same length, so they are incomparable. Hence $W'_{s+1}$ is prefix-free. Every new string extends $\sigma_s$, so $[W'_{s+1}]^{\prec} \subseteq [\{ \sigma_i : i \leq s \}]^{\prec}$. Conversely, let $X \succ \sigma_s$; if $X \uh L$ has no prefix in $W'_s$, it is one of the new strings, so in every case $X \in [W'_{s+1}]^{\prec}$. The construction is effective and uniform in an index of $W$.

1.3 The measure of effective classes

A real number $r$ is left-c.e. if it is the limit of a computable non-decreasing sequence of rationals, and right-c.e. if it is the limit of a computable non-increasing sequence of rationals, that is, if $-r$ is left-c.e. A real is computable if and only if it is both: given the two approximations, wait until they are within $2^{-n}$ of each other to approximate $r$ to precision $2^{-n}$. Chaitin’s number $\Omega$ is left-c.e. and not computable (Chaitin).

Proposition 1.3.#

1. If $\mathcal U = [W]^{\prec}$ with $W$ c.e., then $\lambda(\mathcal U)$ is left-c.e., uniformly in an index of $W$: with $W'$ as in Lemma 1.2, $\lambda(\mathcal U) = \lim_s \sum_{\sigma \in W'_s} 2^{-|\sigma|}$.
2. If $\mathcal P = [T]$ with $T$ a computable tree, then $\lambda(\mathcal P) = \lim_n 2^{-n} |T \cap 2^n|$, a non-increasing limit. So $\lambda(\mathcal P)$ is right-c.e., uniformly in an index of $T$.
3. In both cases the measure is computable in $\emptyset'$.

Proof of Proposition 1.3.

1. The classes $[W'_s]^{\prec}$ increase with union $\mathcal U$, and $\lambda([W'_s]^{\prec}) = \sum_{\sigma \in W'_s} 2^{-|\sigma|}$ since $W'_s$ is prefix-free. By continuity, $\lambda(\mathcal U)$ is the supremum of these computable rationals.
2. Let $\mathcal C_n = [T \cap 2^n]^{\prec}$; its measure is $2^{-n}|T \cap 2^n|$, since $2^n$ is prefix-free. Since $T$ is closed under prefixes, every node of length $n+1$ extends a node of length $n$, so $\mathcal C_{n+1} \subseteq \mathcal C_n$. A sequence $X$ belongs to every $\mathcal C_n$ if and only if $X \uh n \in T$ for every $n$, that is, $X \in [T]$. By continuity, $\lambda(\mathcal P) = \inf_n \lambda(\mathcal C_n)$.
3. A real that is left-c.e. or right-c.e. is the limit of a computable sequence of rationals that is monotone. With $\emptyset'$ one decides, for a rational $q$, whether some term of a non-decreasing sequence exceeds $q$, a $\Sigma^0_1$ question; this suffices to compute the binary expansion, or approximations to any precision. The same holds for non-increasing sequences.

The bounds of the proposition are sharp: by the first exercise below, every left-c.e. real of $[0, 1]$ is the measure of a $\Sigma^0_1$ class. Since $\Omega$ is not computable, neither is the measure $1 - \Omega$ of the complementary $\Pi^0_1$ class.

1.4 Null classes

Definition 1.4.#

A Borel class $\mathcal N$ is null if $\lambda(\mathcal N) = 0$, and conull, or of measure one, if its complement is null. A property of sequences holds for almost every $X$ if the class of sequences with this property is conull.

By outer regularity, $\mathcal N$ is null if and only if, for every $\varepsilon > 0$, it is contained in an open class of measure at most $\varepsilon$. A countable union of null classes is null, by subadditivity. A singleton $\{ X \}$ is null, since it is contained in $[X \uh n]$ for every $n$; so every countable class is null, the class of computable sequences for instance.

Example 1.5.#

1. The class $\mathcal N$ of sequences $X$ with $X(2i) = X(2i+1)$ for every $i$ is null and uncountable. Let $W_n$ be the set of strings $\sigma$ of length $2n$ with $\sigma(2i) = \sigma(2i+1)$ for $i < n$. Then $\mathcal N \subseteq [W_n]^{\prec}$, and $\lambda([W_n]^{\prec}) = 2^n \cdot 2^{-2n} = 2^{-n}$.
2. For a computable infinite set $A$, the class of sequences $X$ with $X(a) = 0$ for every $a \in A$ is null: if $a_0 < a_1 < \cdots$ enumerate $A$, it is contained in the clopen class of sequences vanishing at $a_0, \dots, a_{n-1}$, of measure $2^{-n}$.

In both examples, the covers are given by an algorithm: the open class of measure at most $2^{-n}$ is computed from $n$. The next lesson calls a sequence random if it avoids every null class that admits such an effective sequence of covers.

1.5 Relative measure and density

For a Borel class $\mathcal B$ and a string $\sigma$, the relative measure of $\mathcal B$ in $[\sigma]$ is

$$\lambda(\mathcal B \mid \sigma) = \frac{\lambda(\mathcal B \cap [\sigma])}{\lambda([\sigma])} = 2^{|\sigma|}\, \lambda(\mathcal B \cap [\sigma]).$$

It is the proportion of $[\sigma]$ occupied by $\mathcal B$. Since $[\sigma]$ is the disjoint union of $[\sigma 0]$ and $[\sigma 1]$, $\lambda(\mathcal B \mid \sigma)$ is the average of $\lambda(\mathcal B \mid \sigma 0)$ and $\lambda(\mathcal B \mid \sigma 1)$; more generally, it is the average of $\lambda(\mathcal B \mid \tau)$ over the $2^k$ extensions $\tau$ of $\sigma$ of length $|\sigma| + k$.

A class of positive measure cannot be spread thinly over every cylinder: some cylinder is almost filled by it.

Lemma 1.6 (Lebesgue density lemma).#

Let $\mathcal B$ be a Borel class with $\lambda(\mathcal B) > 0$. For every $\varepsilon > 0$, there is a string $\sigma$ with $\lambda(\mathcal B \mid \sigma) > 1 - \varepsilon$.

Proof of Lemma 1.6.

If $\varepsilon \geq 1$, the empty string works, since $\lambda(\mathcal B) > 0$; so assume $\varepsilon < 1$. By outer regularity, there is an open class $\mathcal U \supseteq \mathcal B$ with $\lambda(\mathcal U) < \lambda(\mathcal B) / (1 - \varepsilon)$, a number larger than $\lambda(\mathcal B)$. Write $\mathcal U = [W]^{\prec}$ with $W$ prefix-free. The classes $\mathcal B \cap [\sigma]$, $\sigma \in W$, are pairwise disjoint with union $\mathcal B$. If $\lambda(\mathcal B \mid \sigma) \leq 1 - \varepsilon$ for every $\sigma \in W$, then

$$\lambda(\mathcal B) = \sum_{\sigma \in W} \lambda(\mathcal B \cap [\sigma]) \leq (1 - \varepsilon) \sum_{\sigma \in W} 2^{-|\sigma|} = (1 - \varepsilon)\, \lambda(\mathcal U) < \lambda(\mathcal B),$$

a contradiction. So some $\sigma \in W$ satisfies $\lambda(\mathcal B \mid \sigma) > 1 - \varepsilon$.

Lebesgue proved a stronger statement, the density theorem: for almost every $X \in \mathcal B$, $\lambda(\mathcal B \mid X \uh n)$ tends to $1$. The lemma suffices for this course.

1.6 Exercises

Exercise 1.7 ★.

Show that for every left-c.e. real $r \in [0, 1]$ there is a $\Sigma^0_1$ class of measure $r$. Deduce that there is a non-empty $\Pi^0_1$ class whose measure is not computable.

Solution

Let $(r_s)$ be a computable non-decreasing sequence of rationals with limit $r$; replacing $r_s$ by $\max(r_s, 0)$, we may assume $0 \leq r_s \leq 1$. For a string $\sigma$, let $0.\sigma = \sum_{i < |\sigma|} \sigma(i) 2^{-i-1}$, and let $W$ be the c.e. set of strings $\sigma$ with $0.\sigma + 2^{-|\sigma|} \leq r_s$ for some $s$. For fixed $n$ and $s$, let $W_{n,s}$ be the set of strings $\sigma$ of length $n$ with $0.\sigma + 2^{-n} \leq r_s$. The numbers $0.\sigma$, $|\sigma| = n$, are the $k\, 2^{-n}$ with $k < 2^n$, so $W_{n,s}$ has $\lfloor 2^n r_s \rfloor$ elements and $\lambda([W_{n,s}]^{\prec}) = 2^{-n} \lfloor 2^n r_s \rfloor$. Both extensions of an element of $W_{n,s}$ belong to $W_{n+1,s}$, and $W_{n,s} \subseteq W_{n,s+1}$. So $[W]^{\prec}$ is the increasing union of the classes $[W_{n,n}]^{\prec}$, and its measure is $\lim_n 2^{-n} \lfloor 2^n r_n \rfloor = r$, since $|2^{-n}\lfloor 2^n r_n \rfloor - r_n| \leq 2^{-n}$.

For the second statement, apply this to $\Omega$, which is left-c.e. and in $(0, 1)$: the complement of the class obtained is a $\Pi^0_1$ class of measure $1 - \Omega > 0$, hence non-empty, and $1 - \Omega$ is not computable since $\Omega$ is not.

Exercise 1.8 ★★.

Let $\mathcal P = [T]$ be a $\Pi^0_1$ class, with $T$ computable, such that $\lambda(\mathcal P) = 0$. Show that there is a computable function $n \mapsto F_n$, with $F_n$ a finite set of strings given by its canonical index, such that $\mathcal P \subseteq [F_n]^{\prec}$ and $\lambda([F_n]^{\prec}) \leq 2^{-n}$ for every $n$. Show also that a $\Pi^0_1$ class of positive measure has a non-computable member.

Solution

By Proposition 1.3 (2), $2^{-m}|T \cap 2^m|$ tends to $\lambda(\mathcal P) = 0$. Given $n$, search for the least $m$ with $2^{-m}|T \cap 2^m| \leq 2^{-n}$, which exists and is found since $T$ is computable, and let $F_n = T \cap 2^m$. Then $\mathcal P \subseteq [F_n]^{\prec}$, as in the proof of the proposition.

For the second statement, the class of computable sequences is countable, hence null. If every member of $\mathcal P$ were computable, $\mathcal P$ would be null.

1.7 Notes and references

Borel introduced the measure of sets of reals in 1898; Lebesgue (1901, 1902) defined the measure of arbitrary sets through countable covers by intervals, which is the origin of outer regularity. Carathéodory (1914) gave the abstract construction. The computation of the measure of effective classes is folklore; the density theorem is due to Lebesgue (1904).

• A. S. Kechris, Classical Descriptive Set Theory, Springer, 1995.
• R. G. Downey and D. R. Hirschfeldt, Algorithmic Randomness and Complexity, Springer, 2010.
• A. Nies, Computability and Randomness, Oxford University Press, 2009.