14.6.2 Lowness for -randomness

Theorem 14.6.8. The following are equivalent for a real x.

(i)x is -traceable;

(ii)Every (x)-nullset is contained in a -nullset;

(iii)x is low for -randomness;

(iv)Every -ML random real is (x)-random.

Proof. (i) → (ii): Assume that x is -traceable. Let be a (x)-nullset. By Proposition 14.2.2 relativized to x, there is a (x)-ML test {Un}n<ω such that μ(Un) = 2−n for each n and . Let {Se}e<ω be a recursive enumeration of all finite subsets of 2<ω. There is a function f ≤h x such that [Sf(〈n,s〉)] = Un,s satisfies Un,s ⊆ Un,s+1, , and μ(Un,s) > 2−n(1 − 2−s).

Let T = (Te)e<ω be a -trace for f . We may choose T such that in addition |Te|≤ e for each e > 0.

We now define a subtrace ̂T of T, i. e. ̂T〈n,s〉 ⊆ T〈n,s〉 for each n, s. The objective is to define open sets Vn via ̂T (in a way to be specified) small enough to give us a -nullset , yet large enough as to keep all “relevant” reals out of T〈n,s〉 − ̂T〈n,s〉, so that .

Let ̂T〈n,s〉 be the set of e ∈ T〈n,s〉 such that 2−n(1 − 2−s) ≤ μ([Se]) ≤ 2−n and [Se] ⊇ [Sd] for some d ∈ ̂T〈n,s−1〉 (where ̂T〈n,−1〉 = ω). Note that f(〈n, s〉) ∈ ̂T〈n,s〉. Let

Then μ(Vn) ≤ 2−n|̂T〈n,0〉|+ ∑s<ω 2−s2−n|̂T〈n,s〉|. Since |̂T〈n,s〉| ≤ |T〈n,s〉| ≤ 〈n, s〉 for 〈n, s〉 ≠ 0, and 〈n, s〉 has only polynomial growth in n and s, it is clear that limn , and hence limn μ(Vn) = 0. Then is a -nullset and .

(ii) ⇒ (iii) and (iii) ⇒ (iv) are immediate.

(iv) ⇒ (i). The proof is identical to the proof in [67]. We leave it to the reader.

By Theorem 13.3.18, lowness for -randomness is different from that for -Kurtz randomness.

14.6.3 Lowness for -ML randomness

Theorem 14.6.9 (Hjorth and Nies [51]). Every real low for -ML randomness is hyperarithmetic.

Proof. We give a sketch. Suppose that x is low for -ML randomness. Then it is not difficult to verify that = and that there is a (x)-ML random y ≥h x. In fact, one may use a -version of Turing reduction, termed ≤fin−h and introduced in [51], to argue that x ≤fin−h y. In other words, there is a consistent -partial map Φ : 2<ω → 2<ω such that X = ∪n<ωΦ(Y ↾ n). Applying the method in [48] it can be shown that x is -trivial, where is an analog of Kolmogorov complexity in the -setting. It follows as in [51] that every -trivial real is either hyperarithmetic or is hyperarithmetically equivalent to . Since = , x has to be hyperarithmetic.

14.6.4 Lowness for -randomness and strong -ML randomness

Theorem 14.6.9 raises the natural question of characterizing reals that are low for -randomness – in particular whether there is one that is not hyperarithmetic. The answer to the latter is in the negative. Proposition 14.6.10 gives a characterization of such reals. We say that x is non--random cuppable if for all -random y. It Is immediate that if x is low for -randomness then = .

Proposition 14.6.10 (Harrington, Nies and Slaman [12]). A real x is low for -randomness if and only if x is low for -randomness and non--random cuppable.

Proof. If x is low for -randomness, then every -random real is (x)-random. Note that by relativizing Theorem 13.1.4, the (x)-set {y | y ⊕ x ≥h } is null since x . Thus x is non--random cuppable.

Suppose y is -random. If y is not (x)-random, then there is a (x)-nullset A containing y. By Proposition 14.2.3, the set is } is a -nullset. Now y ∈ A B. Hence A B is a nonempty (x)-set. By the Gandy Basis Theorem (2.5.3), there is a z ∈ A B such that = = . By Corollary 14.3.2, z is -random but not (x)-random, a contradiction.

Conversely, suppose x is low for -randomness and non--random cuppable. Then x . Let z be a random real. Relativizing the proof of Theorem 14.3.1, the largest (x)-nullset (x) is a union of countably many (x)-null sets n(x) and the (x)-nullset {y | y ⊕ x ≥h }. Since x is low for -randomness, Since x is non--random cuppable, z ⊕ x . Hence z is (x)-random. We conclude that x is low for -randomness.

Proposition 14.6.11. There is a -traceable x which is -random cuppable.

Proof. By Corollary 13.3.8, there is an uncountable -set A containing only nonhyperarithmetic -traceable reals. Let be the largest -nullset. By Theorem 13.2.1, there exist x ∈ A and y ∉ . such that x ⊕ y ≥h .

Corollary 14.6.12.

(i)Lowness for -Kurtz randomness is different from -Kurtz randomness;

(ii)Lowness for -randomness is different from -randomness.

Proof. To prove (i), note that by Theorem 14.6.8 and 14.6.6, every -traceable real is low for -Kurtz randomness. By Proposition 14.6.11, there is an x which is low for -Kurtz randomness for which there is a -random y satisfying x ⊕ y ≡h . We claim that x is not low for -Kurtz randomness. Let e < ω and n ∈ such that y = .

Then

Hence y is a (x)-singleton and so non-(x)-random. Note that (ii) follows immediately from Proposition 14.6.10 and 14.6.11.

We now show that no nonhyperarithmetic real is low for -random. Let ℙ = 〈P, ≤〉 be a notion of forcing, where

P = {P | P is nonempty and -closed containing only -ML random reals}.

For P, Q ∈ P, define P ≤ Q if and only if P ⊆ Q. Note that μ(P)> 0 for each P.

Let {(φi, ψi)}i<ω be a recursive enumeration of arithmetical formulas. For each i, let

Define an approximation of Ai at j as

and for n ∈ , set

Suppose x ∈ Ai. Then for each j, there is an n such that x ∈ Ai,j,n. Uniformly for each j < ω and n ∈ , apply a “dual form” of Lemma 13.1.10 obtained by replacing m, n there respectively with l and the Gödel number of “¬(∀k ≤ j)(∃y|n|)(φi(k, y|n|)∨¬ψi(k, y|n|))”. We then have a -function pi : ω2 × → ω such that for j, l < ω and n ∈ ,

is a -open cover of Ai,j,n, with μ(Ui,j,l,n Ai,j,n) < 2−j−n−l. Then Ui,j,l = ⋃n∈O Ui,j,l,n

is a -open set. Note that Ai,j ⊆ Ui,j,l and

Let Gi ⊇ Ai be the -set defined as . Let

Lemma 14.6.13. 1 is dense for each i.

Proof. Let P be a condition. There are two cases to consider:

Case 1. μ(P Gi)> 0. Then there is a k such that . Let . Then .

Case 2. μ(P Gi) = 0. By Lemma 13.1.10, there exists a -closed set F ⊆ Gi such that μ(F ∩ P)> 0. Let Q = P ∩ F. Then Q ∈ P.

Theorem 14.6.14 (Monin [105]). If g is a ℙ-generic real meeting all i’s, then = .

Proof. Let g be ℙ-generic. It is sufficient to prove that (, g) -comprehension.

Let P be a condition such that g ∈ P. If P ∩ Gi = , then P ∩ Ai = . It follows that there is a k such that (, g) (∀y)(¬φi(k, y)∧ ψi(k, y)).

Otherwise P ⊆ Gi. By (topological) compactness, for any j and l there is an n such that P ⊆ Ui,j,l,n. It follows that there is a total –hence – function f : ω2 → such that for any j, l, f(j, l)∈ and P ⊆ Ui,j,l,f(j,l). Hence there is an m ∈ such that |f(j, l)| < |m| for any j, l. Then is a -nullset. Since g is -ML-random, g ∉ Ci. Then for any j, there is an l such that g ∈ Ai,j,f(j,l). Thus (, g) (∀k)(∃y|m|)(φi(k, y|m|)∨¬ψi(k, y|m|)) and so (, g) -comprehension.

Theorem 14.6.15 (Greenberg and Monin). Every low for -random real is hyperarithmetic.

Proof. Suppose that x is not hyperarithmetic. By Theorem 14.6.9, x is not low for -ML randomness. Let be a universal (x)-ML test. We claim that for any n and P ∈ P, ∩ P ≠ . Otherwise, P ∩ = for some n. Then every real z ∈ P is (x)-ML random. However, for any -ML random y, by Proposition 14.2.7, there is a z ∈ P such that y = ∗ z. Hence y is also (x)-ML random. In other words, x is low for -ML random, a contradiction.

Since P contains only -ML random reals, P ∩ ≠ implies that there is a condition Q ⊆ P ∩ .

Let n = {P ∈ P | P ⊆ }. Then n is dense for each n. If g is ℙ-generic meeting each i and n, then g is -random and . In other words, g is not (x)-ML random and hence not (x)-random.

By the proof of Theorem 14.6.15, for any x if every -random real is (x)-ML random, then x must be hyperarithmetic.

Corollary 14.6.16. A real x is low for strongly -ML random if and only if it is hyperarithmetic.

Proof. Obviously every hyperarithmetic real is low for strongly -ML random. Now suppose that x is low for strongly -ML random. Then every -random real is strongly (x)-ML random and so (x)-ML random. So x must be hyperarithmetic.

14.6.5 Lowness for -and -randomness

One may also introduce the notion -traceability as for -traceability. However, this notion is vacuous under V = L in view of Proposition 14.4.2. Thus we have the following conclusion

Proposition 14.6.17. If V = L, then

Lowness for -ML randomness = Lowness for -randomness.

In the case of lowness for -randomness, one may apply Theorem 14.4.7 to obtain a characterization. Finally, it is possible to introduce the notion of constructible traceability in the obvious way and use it to study lowness property for -randomness under additional set-theoretic assumptions. This will involve the use of some sophisticated techniques in set theory. The interested reader may consult [2].

14.6.6 Exercises

Exercise 14.6.1. Prove Lemma 14.6.3.

Exercise 14.6.2. Prove that x is -semitraceable if and only if every -ML random real is (x)-Kurtz random.

Exercise 14.6.3. Prove that there exist two uncountable -sets A, B such that for any x ∈ A, y ∈ B and recursive ordinal, .

Exercise 14.6.4 (Bienvenu, Greenberg and Monin). Let {Gi}i∈ω be as defined as before. Prove that a -random x is -random if and only if for any i, either x ∉ Gi or x ∈ .

Exercise 14.6.5 (Monin [105]). Prove that the set of -random reals is but not

Exercise 14.6.6 (Greenberg and Monin). Prove that if x is low for -random but not hyperarithmetic, then x is -random cuppable.