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


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


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



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



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.