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 z ⊆ z1 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 x ∈ C such that x ≡h . 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 ≻ σ → y ∈ A)}. Then x is a -real coding A (i. e. y ∈ A 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 μ(⋃{[σ]|(∃m ∈ n)(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 B ⊆ A 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 x ∈ A, 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<ω |(∃y ∈ B)(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))> 2−k. Let

Then C is a -closed nullset. However, x ∈ C 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 b ≥ a, 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 z ≥T x ′, there is an x-Kurtz-random real y ≡T z.

Proof. Let z ≥T 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 y ≤T 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 lm ≤ i < 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 y ≥T 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) = 2−n) 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 z (§ 2.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)) < 2−n, and

–A ⊆ Af(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 Un ⊆ Vn and μ(Vn) = 2−n. Since the set U = {(n, σ) | σ ∈ Un} is , there is an m ∈ such that U ≤T 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) = 2−n and Un ⊆ Vn. 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) < 2−n 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 2−n. 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 z ≥h , there is a -ML random x ≡h 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)(∀n ≥ m)(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) ≤ ∑m≥n (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−1 ≺ x so that x = σ0⌢σ1⌢ …⌢ σn−1⌢z 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)P ∈ D if and only if P ⊆ 2ω is -closed and of positive measure;

(ii)for any P, Q ∈ D, P ≤ Q if and only if P ⊆ Q.

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

Lemma 14.2.8. U is dense.

Proof. Let P ∈ D. 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 P0 ∩ P is a -closed set and has measure greater than or equal to μ(P)/2. Thus P ∩ P0 ∈ D.

For any set G, let = {P | P ∈ D ∧ P ∩ G = }.

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

Proof. Let P ∈ D. 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 [z ↾ n]∩ G = 0. Let Q = [z ↾ n]∩ 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 x ∈ P. 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,β) < 2−n;

(3) x ∈ ⋂n<ω Un;

(4) for any z, if z ∈ Un,<β 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 x ∈ P 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 x ≥h , there is a z ≡h 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 x ∈ A ⇔ A(, x) (∃y)φ(x, y). Hence if = , then x ∈ A ⇔ 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,n ∈ Ae,n such that μ(Ae,n) = 1. Hence if x is -random, then x ∈ Ae,n. By Corollary 14.3.2, = . Thus if g ≤h 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 x ∈ P. 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 y ≥h x such that no z ≡h y is -random.

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

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

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