# 14 The theory of higher randomness – Recursion Theory

## 14 The theory of higher randomness

Higher randomness theory studies algorithmic complexity problems of randomness using techniques and ideas from hyperarithmetic theory and set theory. Since second order arithmetic provides a broader, though sometimes coarser, view of the reals, the picture one gets of randomness is quite different from that for first order theory.

### 14.1 Higher Kurtz randomness

#### 14.1.1 and -Kurtz randomness

Definition 14.1.1. Let x ∈ 2ω. Given a class Γ of sets of reals, x is Γ-Kurtz random if it is not a member of any closed nullset in Γ.

We focus on , and -Kurtz randomness. Recall (§ 2.7.1) that BC denotes the set of Borel codes and {Az | z ∈ BC} is the set of reals generated by the codes.

Proposition 14.1.2.

(i)x is -Kurtz random if and only if x does not belong to any Π1(HYP)-nullset.

(ii)The set of -Kurtz random reals is but not .

Proof. Note that (i) follows immediate from Theorem 2.7.4. We give a self-contained proof here.

By Theorem 2.7.2, every Π1(HYP)-set is a -set. Hence no -Kurtz random real belongs to a Π1(HYP)-nullset. Conversely, let P be a -nullset. Then is . Since P is closed and the set of hyperarithmetic reals is dense, we have

By Corollary 2.2.12, U is also and hence . Thus PΠ1(HYP). It follows that x does not belong to a Π1(HYP)-nullset, and hence . In other words, x is -Kurtz random.

To prove (ii), observe that the set

is , where Az is as defined in § 2.7.1. By Proposition 13.1.6, the set

is . Hence the set

is a -nullset. Moreover by (i),

Hence the set of -Kurtz random reals is . Now μ(E)= 1, and since no hyperarithmetic real is -Kurtz random, by Theorem 13.1.13 one concludes that E is not .

Theorem 14.1.3 (Kjos-Hanssen, Nies, Stephan and Yu [68]). -Kurtz randomness-Kurtz randomness = -Kurtz randomness.

Proof. It is obvious that -Kurtz randomness ⊆ -Kurtz randomness ⊆ -Kurtz randomness. We show that the first inclusion is proper. Let

By Proposition 13.1.6, R is and by Theorem 4.2.1, there is a -function f : ω → 2<ω uniformizing R. Let

Then C is a closed -set and μ(C)≥ 2−1. Note that if z1Σ1 ∩ HYP and μ(Az1)> p for some p, then there is a finite zz1 in Σ1 ∩ HYP such that μ(Az)> p. By Proposition 14.1.2, every real in C is -Kurtz random. Since C is closed and , it can be presented by a -tree. By Theorem 11.1.2, there is an xC such that xh . Let e and be such that . Then

In other words, x is a -singleton which is therefore not -Kurtz random.

We now show that every -Kurtz random real is -Kurtz random. Let A be a -open set of measure 1. Define x ={σ ∈ 2<ω |(∀y)(yσyA)}. Then x is a -real coding A (i. e. yA if and only if there is a σx such that yσ). Hence there is a recursive function f : 2<ωω such that σx if and only if f(σ)∈ . Define a -relation Rω × ω so that (k, n)∈ R if and only if n and μ(⋃{[σ]|(∃mn)(f(σ)= m)}) > 1 − . Clearly R is a -relation which can be uniformized by a -function f. Since μ(A)= 1, f is a total function. Thus the range of f is bounded by a notation n. Define B ={y |(∃σ)(yσf(σ)∈ n)}. Then BA is a -open set with measure 1. It follows that every -open co-nullset has a -open co-null subset. Hence -Kurtz randomness = -Kurtz randomness.

The following result clarifies the connection between and -Kurtz randomness.

Proposition 14.1.4. If = , then x is -Kurtz random if and only if x is -Kurtz random.

Proof. Suppose that = and x is -Kurtz random. If A is a -closed nullset such that xA, then by the Spector–Gandy Theorem 3.7.3, there is an arithmetic formula φ(z, y) such that the formula (∃z ∈ HYP)φ(z, y) defines A. Since = , there is a recursive ordinal β such that

Define T = {σ ∈ 2<ω |(∃yB)(yσ)}. Clearly B ⊆ [T]. Since B is , [T] is . Since A is closed, we have [T] ⊆ A. Also A is null implies that [T] is null as well. By Lemma 13.1.10 and a routine application of -uniformization, there is a total -function f : ω → HYP such that for any k, f(k) ∈ Σ1 ∩ HYP, Af(k) ⊆ 2ω \ [T] and μ(Af(k))> 2k. Let

Then C is a -closed nullset. However, xC and this is a contradiction.

#### 14.1.2 Base of a cone of Kurtz random reals

From the proof of Theorem 14.1.3, one sees that every hyperdegree above that of contains a -Kurtz random real. This fails for -Kurtz randomness. We say that a hyperdegree a is a base of a cone for Γ-Kurtz randomness if for every hyperdegree ba, b contains a Γ-Kurtz random real.

The hyperdegree of is a base of a cone for -Kurtz randomness as proved in Theorem 14.1.3. Not every nonzero hyperdegree is a base of a cone for -Kurtz randomness (see Lemma 14.6.1). Does there exist a base of a cone for -Kurtz randomness? If so, such a base, say b, is not hyperarithmetically reducible to a -singleton. This means that a hyperdegree which serves as a base must be fairly complicated.

Lemma 14.1.5. For any reals x and zT x, there is an x-Kurtz-random real yT z.

Proof. Let zT x′ and fix an enumeration of x-r. e. open sets . We construct an increasing sequence {σs}s<ω of strings as follows.

Let σ0 = .

Stage s + 1. Let l0 = 0, l1 = |σs|, and for n > 1. For each such n, let

Then

In other words,

Case 1. There is an m > l1 + 1 such that . Let n = m + 1. Then ln+1 − 1 − ln > 2 and ln > m. Then there is a and a τ σ such that [τ] ⊆ and τ ∈ 2m.

Let .

Case 2. Otherwise. Let .

This completes the construction at stage s + 1. Let . Obviously the construction is recursive in z and so yT z. Moreover, if is of measure 1, then Case 1 holds at stage s + 1. Hence y is x-Kurtz random.

Let l0 = 0 and let for n > 0. To compute z(n) from y, we y-recursively find the n-th lm such that for all i, j with lmi < j < lm+1, y(i) = y(j). Then z(n) = y(lm).

We call Aω × 2ω auniversal -closed set if (i) it is , (ii) for every n, An = {x |(n, x)∈ A} is a -closed set, and (iii) every -closed set is An for some n. By Theorems 13.1.3 and 13.1.4, the real x0 = {n | μ(An) = 0} is . Let

Then c may be viewed as a -real. Since every -null closed set is (c), every c-Kurtz-random real is -Kurtz random.

Theorem 14.1.6. The hyperdegree of c is the base of a cone for -Kurtz randomness.

Proof. Lemma 14.1.5 implies that the Turing degree of any yT c′ contains a member which is c-Kurtz random and therefore -Kurtz random. Thus c is a base for -Kurtz randomness.

We analyze the complexity of c. Since every -singleton is recursive in Moreover, the set {x | x is a -singleton} is (c). In other words, {x | x is a -singleton} . Hence one has > . Applying the same argument as that in Proposition 4.4.4, the reals in are precisely those that are and so c is not . Moreover, since c is , it is Σ1 definable over and hence c. Indeed, all -reals belong to . Thus:

c has the largest hyperdegree among all reals.

#### 14.1.3 Exercises

Exercise 14.1.1. Prove that neither the set of nor -Kurtz random reals are

Exercise 14.1.2. Prove that there is a -Kurtz random real which is not Schnorr random.

Exercise 14.1.3. Prove that the set of -Kurtz random reals is not .

Exercise 14.1.4. Prove that .

### 14.2 and -Martin-Löf randomness

#### 14.2.1 -randomness

Definition 14.2.1. Let Γ be a definable class of sets of reals. We say that x is Γ-random if it does not belong to any Γ-nullset.

In this section, we study the key properties of -randomness.

Proposition 14.2.2. Suppose that A is a -nullset. There is a -set Vω × 2<ω such that (∀n)(μ(Vn) = 2n) and A ⊆ ⋂n<ω Vn, where Vn = {σ |(n, σ)∈ V)} is a -open set.

Proof. As before, {Az} is the collection of sets of reals generated by Borel codes z2.7.1). Since A is a -nullset, by Lemma 13.1.10 there is a -function f : ωΣ1 ∩ HYP such that for every n < ω,

μ(Af(n)) < 2n, and

AAf(n)

Then Af(n) = [Un] for some -set Un ⊆ 2<ω. It now suffices to show that {Un}n<ω may be expanded to a -collection {Vn}n<ω such that UnVn and μ(Vn) = 2n. Since the set U = {(n, σ) | σUn} is , there is an m such that UT Hm. Note that the set is r. e. Then by a standard technique in classical randomness theory relativized to , there is a Vω × 2<ω recursive in such that for every n, μ(Vn) = 2n and UnVn. Then

By Proposition 14.2.2, -randomness may be viewed as a higher analog of Schnorr randomness.

Proposition 14.2.3 (Martin-Löf [97]). The set of -random reals is but not .

Proof. Define a -set

By Proposition 14.2.2, A is precisely the set of -random reals. Since A does not contain a hyperarithmetic member, by Theorem 13.1.13, it is not .

#### 14.2.2 -Martin-Löf randomness

A sequence of open sets {Un}n<ω is a Martin-Löf test (ML test) if μ(Un) < 2n for all n. Given a class Γ of sets of reals (e. g. ), {Un}n<ω is a Γ-ML test if {(n, σ)|σ ∈ 2<ω ∧[σ]∈ Un}∈ Γ.

Definition 14.2.4. Let Γ be a class of sets of reals. Then x is Γ-ML random if for any Γ ML test {Un}n<ω.

Proposition 14.2.5 (Hjorth and Nies [51]). There is a universal -ML test {Un}n<ω, i. e. for every -ML test

Proof. Let Ûω × 2<ω be a universal -set, i. e. Û is and every -set is Ûn = {σ |(n, σ)∈ Û} for some n. Then there is a recursive function f : ω × 2<ωω such that (n, σ)∈ Û ⇔ f(n, σ)∈ . Let

In other words, (n, σ) is enumerated into ̂V if the measure of ̂Un up to stage f(n, σ) is less than 2n. Let

Then U is as well. Setting Un = {σ |(n, σ)∈ U}, we have

Hence {Un}n<ω is a -ML test. By the universality of Û, {Un}n<ω is a universal -ML test

Corollary 14.2.6 (Hjorth and Nies [51]).

(i)There is a -closed set of positive measure of -ML random reals.

(ii)For any zh , there is a -ML random xh z.

Proof. (i) follows immediately from Proposition 14.2.5, while (ii) is a consequence of (i) and Theorem 11.1.2.

The following results says that every -closed set of positive measure essentially contains all the -ML random reals.

Proposition 14.2.7. Suppose that T ⊆ 2<ω is a -tree with μ([T]) > 0. Then for any -ML random x, there is a z ∈[T] such that z = x, i. e. (∃m)(∀nm)(x(n) = z(n)).

Proof. Let T ⊆ 2<ω be as given. For any n ≥ 0, let

Then {Un}n<ω is uniformly . Moreover, μ(U0) = μ(2ω \ [T]) = 1 − μ([T]). For any n, μ(Un+1]) = μ(Un)⋅(1 − μ([T])) = (1 − μ([T]))n+2. Let . Then μ(Vn) ≤ ∑mn (1 − μ([T]))m+1 and hence {Vn}n<ω can be viewed as a -ML test. It follows that there is a least n such that x Vn. If n = 0, then x ∈ [T]. Otherwise there is a σ0σ1 σn−1x so that x = σ0σ1 σn−1z for some z ∈ [T]. Hence x = z.

#### 14.2.3 Separating -Martin-Löf randomness from -randomness

Define a notion of forcing = 〈D, ≤〉 as follows:

(i)PD if and only if P ⊆ 2ω is -closed and of positive measure;

(ii)for any P, QD, PQ if and only if PQ.

Suppose Uω × 2<ω is and Un = {σ |(n, σ)∈ U}. Assume limn→∞ μ(Un) = 0 and let

Lemma 14.2.8. U is dense.

Proof. Let PD. There is an n such that μ(Un) < μ(P)/2. Now the complement P0 = 2ω \ Un has measure greater than or equal to 1 −(μ(P)/2). Then P0P is a -closed set and has measure greater than or equal to μ(P)/2. Thus PP0D.

For any set G, let = {P | PDPG = }.

Lemma 14.2.9. If G is a -set consisting only of -random reals, then is dense in

Proof. Let PD. Then there is a hyperarithmetic x such that P is (x). Without loss of generality, we may assume that for any σ, if [σ]∩ P ≠ 0, then μ([σ]∩ P)> 0 (since we may assume that P contains only 1-x-random reals). By Theorem 13.1.13, there is a hyperarithmetic z in P. Hence z G. Since G is closed, there is an n such that [zn]∩ G = 0. Let Q = [zn]∩ P. Then Q.

Theorem 14.2.10 (Chong, Nies and Yu [12]). -ML randomness-randomness.

Proof. By Proposition 14.2.2, -ML randomness ⊆ -randomness. By Proposition 14.2.5, let {Un}n<ω be a universal -ML test. For n < ω, let

By Lemma 14.2.9, is dense. By Lemma 14.2.8, there is a -random x such that for any n, there is a P with xP. Hence , i. e. x is not -ML random.

We remark that is an analog of random forcing ℝ discussed in § 6.2.2. However, ℝ is c. c. c. and so preserves all cardinals while is not c. c. c. in . By the proof of Theorem 14.2.10 and Corollary 14.3.2 below, any -generic x collapses and hence does not preserve admissible ordinals.

#### 14.2.4 Strong -Martin-Löf randomness

A sequence of open sets {Un}n<ω is a generalized Martin-Löf test (ML test) if limn→∞ μ(Un) = 0. Given a class Γ of sets of reals (e. g. ), {Un}n<ω is a generalized Γ-ML test if {(n, σ)| σ ∈ 2<ωσUn}∈ Γ.

Definition 14.2.11. Given a class Γ of sets of reals, x is strongly Γ-ML random if x for any generalized Γ-ML test {Un}n<ω.

Obviously every strongly -ML random real is -ML random.

Lemma 14.2.12. If x is the leftmost path of a -closed set of reals, then x is not strongly -ML random.

Proof. Let P be a -closed set. Then there is a -tree T ⊆ 2<ω such that P = [T]. By the Gandy–Spector Theorem (3.7.1), there is a Σ0-formula φ(σ, β) such that

For β < , let

For n < ω and β < , let

Define

and

The following facts are straightforward to verify: For n < ω and β < ,

(1) Un+1,βUn,β;

(2) μ(Un,β) < 2n;

(3) x ∈ ⋂n<ω Un;

(4) for any z, if zUn,<β \ Un,β, then z Un,γ for any γβ.

Now suppose that . Then there is a σ0 such that

Let n0 = |σ0|+ 2. Then there is a β0 < such that

By (2),

By (1) and (4),

Hence there is a σ1σ0 such that

Let n1 = |σ1|+ 2. There is a β1 < β0 such that

Repeating the process, one obtains an infinite descending sequence β0 > β1 > … of ordinals which is a contradiction. It follows that {Un}n<ω is a generalized -ML test and .

Theorem 14.2.13 (Chong, Nies and Yu). There is a real which is -ML random but not strongly -ML random.

Proof. By Corollary 14.2.6, there is -closed set P of positive measure consisting only of -ML random reals. By Lemma 14.2.12, there is an xP which is not strongly -ML random.

#### 14.2.5 Exercises

Exercise 14.2.1 (Sacks [123]). Prove that every -random real is -random.

Exercise 14.2.2. Prove that for any -random x and recursive ordinal β, x(β)T x⊕0(β).

Exercise 14.2.3 (Yu [171]). Prove that the set of -random reals is not .

Exercise 14.2.4. Prove that for any -random x and recursive function f :2ω → 2ω, if f is almost everywhere differentiable, then f is differentiable at x.

Exercise 14.2.5 (Bienvenu, Greenberg and Monin). Prove that for any x which is the leftmost path of a -closed set of reals, there is a generalized -Martin-Löf test {Un}n<ω such that is countable.

Exercise 14.2.6 (Chong and Yu). Prove that for any xh , there is a zh x which is -Martin-Löf random but not strongly -Martin-Löf random.

### 14.3 -randomness

#### 14.3.1 The largest -nullset

The notion of -randomness was introduced in Hjorth and Nies [51] and is unique to the study of higher randomness. There is no analog of this notion in the subject of classical randomness theory.

Theorem 14.3.1 (Kechris [64]; Stern [161]; Hjorth and Nies [51]). There is a largest -nullset.

Proof. Define

and

Define

We show that is the largest -nullset. By Theorem 13.1.1, is . Moreover, μ(n) = 0 for all n < ω. By Theorem 13.1.4, μ() = 0.

If A is a -nullset, then, by Corollary 3.7.4, there is an arithmetic formula φ( ̇x,z) such that if = , then xA ⇔ A(, x) (∃y)φ(x, y). Hence if = , then xA ⇔ A(, x) (∃yβ)φ(x, yβ) for some β < . Since A is null, we have

Thus A.

Corollary 14.3.2. For any x ∈ 2ω, the following are equivalent:

(i)x is -random;

(ii)x is strongly -ML random and = ;

(iii)x is -ML random and = ;

(iv)x is -random and = .

Proof. Suppose that x is -random. Since {z | > } is a -nullset, we have = and hence (i) ⇒ (ii) ⇒ (iii).

By Theorem 14.2.10, (iii) implies (iv). We now show (iv) ⇒ (i). By the proof of Theorem 14.3.1, if = and x, then x n for some n. Since Qn is a -nullset, if = and x is -random, then it is -random.

The equivalence between (i) and (iv) was also obtained by Stern [161].

#### 14.3.2 Domination and -randomness

Lemma 14.3.3. If x is -random, then it is -dominated.

Proof. By the proof of Theorem 13.3.2, for each eω and n, the set

has measure 1. Note that Ae,n is . By Corollary 13.1.11, there is a -set e,nAe,n such that μ(Ae,n) = 1. Hence if x is -random, then xAe,n. By Corollary 14.3.2, = . Thus if gh x, then for some e and n, proving the lemma.

Proposition 14.3.4 (Kjos-Hanssen, Nies, Stephan and Yu [68]). For any x ∈ 2ω, the following are equivalent:

(i)x is -random;

(ii)x is strongly -ML random and -dominated;

(iii)x is -ML random and -dominated;

(iv)x is -random and -dominated;

(v)x is -Kurtz random and -dominated.

(vi)x is -Kurtz random and -dominated.

Proof. By Corollary 14.3.2 and Lemma 14.3.3, we have (i) ⇒ (ii) ⇒ (iii) ⇒ (iv) ⇒ (v) ⇒ (vi).

To prove (vi) ⇒ (i), it is sufficient to prove (vi) ⇒ (iv) according to Corollary 14.3.2. Suppose x is -dominated and -Kurtz random. Let {Un}n<ω be a -ML test. Then there is a recursive function f : ω × 2<ωω such that for any pair (n, σ), σUn if and only if f(n, σ)∈ . Since x is -dominated, = . Define a (x) relation Rω × ω such that

where . By the -Uniformization Theorem (4.2.1), there is a partial function p uniformizing R. Since x Un, p is a total function and so (x). Since = , there is an m0 such that p(n)∈ for every n. Define a -Martin-Löf test {̂Un}n<ω so that σ̂Un if and only if f(n, σ)∈ . Then x ̂Un. Let

be a (x)-function. Then there is a -function f dominating ̂f. For n < ω, define

Then P = ⋂n<ω Vn is a -closed set and xP. Hence x is not -Kurtz random, a contradiction.

#### 14.3.3 Hyperdegrees of random reals

By Corollary 14.2.6, we know that the hyperdegrees of the set of -random reals include the cone of hyperdegrees with base . This raises the natural question of whether the hyperdegrees of -random reals are closed upwards.

Proposition 14.3.5. If x is -random and = , then there is a yh x such that no zh y is -random.

Proof. Suppose that x is -random and = . Let

Then F(x) is (x). Since xF(x), F(x) is not empty. By Gandy’s Basis Theorem relativized to x, there is a yF(x) with ωy1 = = . By Corollary 14.3.2 and Proposition 14.3.4, no zh y is -random.

On the other hand, the hyperdegrees of -random reals are closed downwards.