Δ¹₁-randomness and higher Martin-Löf tests

Martin-Löf randomness uses null classes that are effectively $\Pi^0_2$. Replacing computability by hyperarithmetic definability gives the notions of higher randomness. Martin-Löf himself proposed in 1970 to call random the sequences avoiding every null class that is effectively Borel, the $\Delta^1_1$ classes; Hjorth and Nies (2007) defined the higher analogue of Martin-Löf tests, in which c.e. sets of strings are replaced by $\Pi^1_1$ sets. The analogy between $\Pi^1_1$ sets and c.e. sets, developed in the course on effective descriptive set theory, is the main tool.

1.1 Δ¹₁ classes and the facts we admit

A class $\mathcal A \subseteq \cs$ is $\Pi^1_1$ if it is defined by a formula $\forall Y\, \varphi(X, Y)$ with $\varphi$ arithmetic, possibly with number parameters; it is $\Sigma^1_1$ if its complement is $\Pi^1_1$ (Definition 3.1 of “Σ¹₁ classes and pseudo-well-orderings”), and $\Delta^1_1$ if it is both. For a set $Y$ and a notation $a \in \mathcal O$, the set $H^Y_a$ is defined as $H_a$ (Definition 1.1 of “Iterating the jump along notations”), starting from $H^Y_1 = Y$. The Church–Kleene ordinal relative to $Y$, $\omega_1^Y$, is the least ordinal that is not the type of a $Y$-computable well-ordering; $\omega_1^Y \geq \omega_1^{\mathrm{CK}}$ for every $Y$.

The measure theory of $\Delta^1_1$ classes extends that of the arithmetic classes, by transfinite induction along notations. We admit the following facts; they are proved in Sacks, Higher Recursion Theory, Chapters I, II and IV, and in the book of Monin and Patey.

Fact 1.1.#

1. Δ¹₁ classes. For $a \in \mathcal O$ and an index $e$, let $\mathcal D_{a, e} = \{ Y : \Phi^{H^Y_a}_e(0)\converge = 1 \}$. Every $\Delta^1_1$ class is of the form $\mathcal D_{a, e}$. Uniformly, there are a $\Pi^1_1$ relation and a $\Sigma^1_1$ relation on $(a, e, Y)$ that both define $Y \in \mathcal D_{a, e}$ when $a \in \mathcal O$. In particular each $\mathcal D_{a, e}$ is $\Delta^1_1$.
2. Measures. The classes $\mathcal D_{a, e}$ are Borel, and their measures are hyperarithmetic, uniformly: there are $\Pi^1_1$ relations $M_>(a, e, q)$ and $M_<(a, e, q)$ that express $\lambda(\mathcal D_{a, e}) > q$ and $\lambda(\mathcal D_{a, e}) < q$ for $a \in \mathcal O$ and rational $q$.
3. Approximation. For $a \in \mathcal O$, $e$ and $k$, there is a set of strings $W_{a, e, k}$ with $\mathcal D_{a, e} \subseteq [W_{a, e, k}]$ and $\lambda([W_{a, e, k}] \setminus \mathcal D_{a, e}) \leq 2^{-k}$, uniformly: the relation $\sigma \in W_{a, e, k}$ is defined, for $a \in \mathcal O$, by a $\Pi^1_1$ relation in $(a, e, k, \sigma)$.
4. Measurability (Lusin). Every $\Sigma^1_1$ and every $\Pi^1_1$ class is Lebesgue measurable: it differs from a Borel class by a subclass of a null Borel class.

Item 3 is the transfinite extension of the outer regularity of the measure (Lebesgue, Carathéodory): by induction on $\alpha$, a $\Sigma^0_\alpha$ class is contained in an open class whose measure exceeds its own by at most $\varepsilon$, with a code computable in the corresponding H-set. Item 4 is needed because $\Pi^1_1$ classes are not Borel in general.

1.2 Two notions of higher randomness

Definition 1.2.#

A sequence is $\Delta^1_1$-random if it belongs to no null $\Delta^1_1$ class.

Proposition 1.3.#

Every $\Delta^1_1$-random sequence is $n$-random for every $n$, and is not hyperarithmetic.

Proof of Proposition 1.3.

A Martin-Löf test relative to $\emptyset^{(n-1)}$ defines a null class $\bigcap_k \mathcal U_k$ with $\mathcal U_k$ uniformly $\Sigma^0_1(\emptyset^{(n-1)})$; it is arithmetic, hence $\Delta^1_1$. If $X$ is hyperarithmetic, the singleton $\{ X \}$ is defined by "$\forall n\ (n \in Y \leftrightarrow n \in X)$", where "$n \in X$" has a $\Pi^1_1$ and a $\Sigma^1_1$ definition (Proposition 2.3 of “The hyperarithmetic sets are the Δ¹₁ sets”); using the $\Pi^1_1$ definition in the implication from $n \in Y$ and the $\Sigma^1_1$ one in the converse implication gives a $\Pi^1_1$ definition of the singleton, and symmetrically a $\Sigma^1_1$ one. So $\{ X \}$ is a null $\Delta^1_1$ class containing $X$.

The higher analogue of a $\Sigma^0_1$ class is an open class generated by a $\Pi^1_1$ set of strings. For a set $W$ of strings, $[W]$ denotes the open class of sequences extending some member of $W$.

Proposition 1.4.#

A class $\mathcal U$ is open and $\Pi^1_1$ if and only if $\mathcal U = [W]$ for some $\Pi^1_1$ set of strings $W$.

Proof of Proposition 1.4.

If $W$ is $\Pi^1_1$, then $X \in [W]$ if and only if $\exists n\ X \uh n \in W$; a number quantifier in front of a $\Pi^1_1$ formula gives a $\Pi^1_1$ formula. Conversely, if $\mathcal U$ is open and $\Pi^1_1$, let $W = \{ \sigma : \forall X\ (\sigma \prec X \rightarrow X \in \mathcal U) \}$, which is $\Pi^1_1$. Every $X \in \mathcal U$ has a prefix $\sigma$ with $[\sigma] \subseteq \mathcal U$, since $\mathcal U$ is open; so $\mathcal U = [W]$.

Definition 1.5 (Hjorth, Nies).#

A higher Martin-Löf test is a sequence of classes $\mathcal U_n = [W_n]$ such that the set $\{ (n, \sigma) : \sigma \in W_n \}$ is $\Pi^1_1$ and $\lambda(\mathcal U_n) \leq 2^{-n}$ for every $n$. A sequence is $\Pi^1_1$-Martin-Löf random if it belongs to no class $\bigcap_n \mathcal U_n$ of such a test.

Every Martin-Löf test is a higher Martin-Löf test, since c.e. sets are $\Pi^1_1$; so $\Pi^1_1$-Martin-Löf random sequences are Martin-Löf random.

Proposition 1.6.#

Every $\Pi^1_1$-Martin-Löf random sequence is $\Delta^1_1$-random.

Proof of Proposition 1.6.

Let $\mathcal D$ be a null $\Delta^1_1$ class. By Fact 1.1 (1), $\mathcal D = \mathcal D_{a, e}$ for some $a \in \mathcal O$ and $e$. By item 3, the classes $\mathcal U_k = [W_{a, e, k}]$ contain $\mathcal D$ and have measure at most $2^{-k}$, and the sets $W_{a, e, k}$ are uniformly $\Pi^1_1$ in $k$, since $a$ and $e$ are fixed and $a \in \mathcal O$. So $(\mathcal U_k)$ is a higher Martin-Löf test capturing every member of $\mathcal D$.

Hjorth and Nies proved that the converse fails: some $\Delta^1_1$-random sequence is not $\Pi^1_1$-Martin-Löf random. The construction follows the stages of the enumeration of the $\Delta^1_1$ classes of measure $1$, and is admitted here.

1.3 A universal higher test

As in the classical case, there is a universal test. The trimming of the components, which keeps their measure below $2^{-n}$, now follows the ordinal stages of a $\Pi^1_1$ enumeration.

Let $U \subseteq \nat$ be the $\Pi^1_1$ set of Proposition 3.6 of “Well-founded trees and Π¹₁ sets”, whose sections include all $\Pi^1_1$ sets. Coding triples by numbers, let $V$ be the $\Pi^1_1$ set of triples $(e, n, \sigma)$ such that $\langle e, \langle n, \sigma \rangle \rangle \in U$. Then every $\Pi^1_1$ set of pairs $(n, \sigma)$ is $\{ (n, \sigma) : (e, n, \sigma) \in V \}$ for some $e$. Fix stages $\rho$ for $V$, as in Theorem 1.2 of “Π¹₁ norms and the reduction property”, given by uniformly computable trees. Write $V_{e, n} = \{ \sigma : (e, n, \sigma) \in V \}$.

Theorem 1.7 (Hjorth, Nies).#

There is a universal higher Martin-Löf test: a test $(\mathcal U_n)$ such that $\bigcap_n \mathcal U_n$ contains $\bigcap_n \mathcal V_n$ for every higher Martin-Löf test $(\mathcal V_n)$.

Proof of Theorem 1.7.

For $e$, $n$ and $\sigma$, write $\rho(e, n, \sigma)$ for the stage of the triple. Let $\widehat V_{e, n}$ be the set of strings $\sigma \in V_{e, n}$ such that, for every finite set $F$ of strings,

$$\big( \forall \tau \in F\ \ \rho(e, n, \tau) \leq \rho(e, n, \sigma) \big) \rightarrow \lambda([F]) \leq 2^{-n}.$$

By Lemma 1.1 of “Π¹₁ norms and the reduction property”, the hypothesis of the implication is $\Sigma^1_1$, so the implication is $\Pi^1_1$; the quantifier over finite sets is a number quantifier, and $\sigma \in V_{e, n}$ is $\Pi^1_1$. So $\widehat V_{e, n}$ is $\Pi^1_1$, uniformly in $e$ and $n$.

Measure. Let $F$ be a non-empty finite subset of $\widehat V_{e, n}$, and $\sigma \in F$ with the largest stage. All $\tau \in F$ satisfy $\rho(e, n, \tau) \leq \rho(e, n, \sigma)$, so $\lambda([F]) \leq 2^{-n}$ since $\sigma \in \widehat V_{e, n}$. The open class $[\widehat V_{e, n}]$ is the increasing union of the classes $[F]$ for finite $F \subseteq \widehat V_{e, n}$, so its measure is at most $2^{-n}$.

No change for tests. If $\lambda([V_{e, n}]) \leq 2^{-n}$, then every finite $F \subseteq V_{e, n}$ has $\lambda([F]) \leq 2^{-n}$, and in particular those whose members have stages at most $\rho(e, n, \sigma)$; so $\widehat V_{e, n} = V_{e, n}$.

Let $\mathcal U_n = \bigcup_e [\widehat V_{e, n + e + 1}]$. It is generated by the set of strings $\{ \sigma : \exists e\ \sigma \in \widehat V_{e, n+e+1} \}$, which is $\Pi^1_1$ uniformly in $n$, and $\lambda(\mathcal U_n) \leq \sum_e 2^{-n-e-1} = 2^{-n}$. If $(\mathcal V_n)$ is a higher Martin-Löf test, generated by $V_{e, n}$ for some $e$, then $\widehat V_{e, m} = V_{e, m}$ for every $m$, and $\bigcap_n \mathcal V_n \subseteq \bigcap_n \mathcal V_{n+e+1} \subseteq \bigcap_n \mathcal U_n$.

Corollary 1.8.#

The class of $\Pi^1_1$-Martin-Löf random sequences is $\Sigma^1_1$ and has measure $1$. It contains a $\Sigma^1_1$ class of positive measure, and therefore a member computable in $\mathcal O$.

Proof of Corollary 1.8.

Its complement is $\bigcap_n \mathcal U_n$ for the universal test, an intersection of uniformly $\Pi^1_1$ classes, hence $\Pi^1_1$, of measure $0$. The complement of $\mathcal U_1$ is $\Sigma^1_1$, of measure at least $\frac12$, and contained in the class of random sequences. By the Kleene basis theorem (Kleene basis theorem), it has a member computable in $\mathcal O$.

1.4 Exercises

Exercise 1.9 ★.

Show that the class of $\Delta^1_1$-random sequences has measure $1$, using the facts admitted in this lesson.

Solution

By Fact 1.1 (1), the $\Delta^1_1$ classes are among the classes $\mathcal D_{a, e}$ with $a \in \mathcal O$, which form a countable family. The non-$\Delta^1_1$-random sequences form the union of those that are null, a countable union of null classes, hence a null class.

Exercise 1.10 ★★.

Show that a $\Pi^1_1$-Martin-Löf random sequence is Martin-Löf random relative to every hyperarithmetic set.

Solution

Let $A$ be hyperarithmetic, and $(\mathcal V_n)$ a Martin-Löf test relative to $A$, generated by sets of strings $V_n$ that are c.e. in $A$ uniformly. The relation $\sigma \in V_n$ is $\Sigma^0_1(A)$, and $A$ is $\Delta^1_1$, so it is $\Delta^1_1$, in particular $\Pi^1_1$, uniformly in $n$. So $(\mathcal V_n)$ is a higher Martin-Löf test.

1.5 Notes and references

$\Delta^1_1$-randomness was proposed by Martin-Löf (1970). Hjorth and Nies (2007) introduced $\Pi^1_1$-Martin-Löf randomness, the universal test, higher prefix-free complexity and the higher Levin–Schnorr theorem, and separated the notion from $\Delta^1_1$-randomness. Chong and Yu’s monograph and Monin’s thesis develop higher randomness systematically.

• P. Martin-Löf, On the notion of randomness, in Intuitionism and Proof Theory, North-Holland, 1970, 73–78.
• G. Hjorth and A. Nies, Randomness via effective descriptive set theory, Journal of the London Mathematical Society 75 (2007), 495–508.
• C. T. Chong and L. Yu, Recursion Theory: Computational Aspects of Definability, De Gruyter, 2015.
• G. E. Sacks, Higher Recursion Theory, Springer, 1990, Chapter IV.