13 More on hyperarithmetic theory

13.1 Hyperarithmetic measure theory

The application of measure theory in recursion theory was initiated by Spector [155], Sacks [117] and Leeuw, Moore, Shannon, and Shapiro [19]. Randomness theory on the natural numbers may be viewed as such an application, while higher randomness theory is the union of measure theory with hyperarithmetic theory. In this chapter we discuss these connections to set the stage for higher randomness in the next chapter.

13.1.1 The measure of -sets

Lemma 13.1.1 (Sacks [120]). The set

is .

Proof. By the Spector–Gandy Theorem (3.7.1) it is sufficient to prove that the set

is Σ1 over . We apply Theorem 3.1.8 by performing induction on the rank of φ.

If φ is atomic, then

is recursive. By induction on the complexity of φ, it is not difficult to see that

is arithmetical and hence Σ1 over .

Now suppose that the set

is Σ1 over .

Let φ(x, xβ) be a formula of rank at most β so that the only free variables are x and xβ. Then (, x) (∃xβ)φ(̇x, xβ) if and only if (, x) φ(̇x, xβ | ψ) for some formula ψ(n) with rank less than β, where n is the only free variable of ψ.

For simplicity, write φ(x, xβ | ψ) as φ(x, ψ). Then

{(⌜(∃xβ)φ(x, xβ)⌝, p)| μ({x | (, x) (∃xβ)φ(, xβ)}) ≥ p ∧ p is rational}= {(⌜(∃xβ)φ(x, xβ)⌝, p)|(∃ ψ(n) of rank < β) (n is the only free variable of ψ) ∧ p is rational ∧ μ({x | (, x) φ(, ψ)}) ≥ p}.

Note that the set of formulas ψ of rank < β where n is the only free variable belongs to . Hence the set {(⌜(∃xβ)φ(x, xβ)⌝, p) | p is rational ∧ μ({x | (, x) (∃xβ)φ(, xβ)}) ≥ p} is Σ1 over .

For formulas of the form (∀xβ)φ(, xβ) where n is the only free variable, note that uniformly in . there is an ω-enumeration of the set of such formulas. Fix such an enumeration {ψi(n)}i<ω. Then

if and only if

if and only if

Hence {⌜(∀xβ)φ(x, xβ)⌝, p)| p is rational∧ μ({x | (, x) (∀xβ)φ(, xβ)}) ≥ p} is Σ1 over .

We leave it to the reader to verify the other cases. Note that the induction is uniform and hence the lemma follows.

Corollary 13.1.2. Let p > 0 be rational. Suppose that φ(n, y) is a ranked formula whose only free unranked set variable is y. If for any n < ω, μ({x | (, x) (∃y)φ(n, y)}) ≥ p, then there is a β < such that (∀n)μ({x | (, x) (∃yβ)φ(n, yα)}) ≥ p.

Proof. Let m0 be fixed so that p > 2−m0. By Lemma 13.1.1 and the assumption, there is a function f : ω ×(ω [0, m0]) → in such that for every n and m > m0,

Let g(n)= f(n, m). By the admissibility of , g is total in . Hence for all n, μ({x | (, x) (∃yg(n))φ(n, yg(n))}) ≥ p. Let β = g(n). By admissibility again, β < . Moreover, (∀n)μ({x | (, x) (∃yα)φ(n, yβ)}) ≥ p.

Theorem 13.1.3 (Sacks [120]). Let p be rational. The set {(⌜φ⌝, p)|φ is ∧ φ’s only free variable is x ∧ μ({x | (, x) φ}) ≥ p} is .

Proof. This follows immediately from Lemma 13.1.1 and Corollary 13.1.2.

Theorem 13.1.3 is useful as a basic tool for hyperarithmetic measure theory.

13.1.2 Measure-theoretic uniformity

Theorem 13.1.4 (Sacks [120]). {x | = } has measure 1.

Proof. By Theorem 5.1.5, it is sufficient to prove that the set

has measure 1. Let {(φi, ψi)}i<ω be a recursive enumeration of arithmetical formulas. For each i, define the -set

Let

Then Ai,β ⊆ Ai for all i < w and β < . By Corollary 13.1.2, for any i, j < ω, there is a βi,j < such that . Moreover, for any j < ω and (Ai ), we have (, x) -comprehension. Then for any j,

Thus

Theorem 13.1.4 is somewhat counterintuitive since it is much easier to construct a real hyperarithmetically computing the hyperjump. The theorem may also be viewed as one more piece of evidence to support the randomness thesis since the set of reals hyperarithmetically computing has measure 0.

It is known (see Sacks [117] and Leeuw, Moore, Shannon, and Shapiro [19]) that for any nonrecursive x, the set {y | y ≥T x} is null. The following theorem is a hyperarithmetic analog.

Theorem 13.1.5 (Sacks [123]). If x is not hyperarithmetic, then μ({y | y ≥h x}) = 0.

Proof. For any x, the set {y | y ≥h x} is (x) and hence measurable by Corollary 3.7.10.

Now suppose that μ({y | y ≥h x}) > 0. By Theorem 13.1.4, = . Moreover, μ({y | ωy1 = ∧ y ≥h x}) > 0. By Theorem 5.1.4, there is a ranked formula φ(n) such that μ({y | n ∈ x ⇔ A(, y) φ(n)}) > 0. By the Lebesgue Density Theorem, there is a string σ ∈ 2<ω such that μ({y ≻ σ | n ∈ x ⇔ (, y) φ(n)}) > ⋅ 2−|σ|. Then

and

By Lemma 13.1.1, x is hyperarithmetic, which is a contradiction.

It is also known that the statement “μ(A)> p” is r.e. if A is an r.e. set of reals and p is rational. The following corresponding result holds in hyperarithmetic theory.

Proposition 13.1.6 (Sacks [123]). Let A ⊆ ω × 2ω be and An ={x |(n, x)∈ A}. Then {(n, p)| p is rational ∧ μ(An)> p} is .

Proof. Since A is , by Corollary 3.7.4 there is an arithmetical formula φ(n, x, z) such that

Let B ={(n, x)| (, x) (∃z)φ(n, x, z)} ⊆ A. By Theorem 13.1.4 for every n, μ(Bn)= μ({x |(n, x)∈ B})) = μ(An). By Corollary 13.1.2, μ(Bn)> p if and only if

if and only if

By Lemma 13.1.1, it follows that the set {(n, p)| μ(An)> p∧p is rational} is .

The following result was proved by Kechris in [63] under the assumption of PD. It turns out that the additional assumption can be weakened.

Corollary 13.1.7 (Kechris [63]). Assume that < ω1. Given a -set A ⊆ 2ω, both {p ∈ℚ| μ(A)> p} and {p ∈ℚ| μ(A)≥ p} are .

Proof. By assumption, almost every real is ℝ-generic over L (see § 6.2.2). Note that for any x that is ℝ-generic over L, = . Since A is , there is a relation R such that

Then μ(A)> p if and only if there is an ordinal β < such that μ({x |(∃y ∈ Lβ[x]) R(x, y)}) > p.Thus μ(A)> p if and only if there is a real r ∈ L coding a well-ordering of order type β such that μ({x |(∃y ∈ Lβ[x])R(x, y)}) > p. By Proposition 13.1.6, the latter is a -statement.

The second part of the corollary follows immediately from the first.

By the proof of Corollary 13.1.7, we have the following conclusion.

Corollary 13.1.8. If < ω1, then every -set is measurable.

Proposition 13.1.9 (Kechris [63]). Suppose that < ω1. For any x, if {y | x ≤ y} is not null, then x is Δ;

Proof. By the -Uniformization Theorem (4.2.1), there is a -partial function F : ω× 2ω → 2ω such that for any y and (y)-singleton z, there is an n such that F(n, y)= z. By Corollary 4.2.8, if and only if there exist n and e such that x = . Note that for any pair (n, e) and numbers m and i, the set

is and hence, by Corollary 13.1.8, is measurable. Note also that for any n and e, the set

is measurable. Hence E ={y | } is measurable. Now suppose that E is not null. Then there is a pair (n, e) that has Dn,e positive measure. Let σ ∈ 2<ω such that μ(Dn,e ∩[σ]) > 2−|σ| ⋅ . Then

By Corollary 13.1.7, x is . By the same argument, ωx is also and hence x is . It should be pointed out that the assumption “ < ω1” in Proposition 13.1.9 is not provable under ZFC.

13.1.3 A measure-theoretic basis theorem

In measure theory, every measurable set of reals is approximated by closed sets. There is an effective version of this in hyperarithmetic theory.

Lemma 13.1.10. There is a -function f : ω × ω → ω such that for any Gödel number n of a ranked formula,

(i)f(n, m) is the Gödel number of a ranked formula whose only free variable is x;

(ii)the set {x|(, x) φf(n,m)} is a closed subset of {x|(, x) φn};

(iii)μ({x|(, x) φn} {x|(, x) φf(n,m)}) < 2−m.

Proof. We construct the function f by induction on the rank of formulas. Let β < and assume by induction that f is defined for every formula with rank less than β. In , there is a uniform enumeration {ψi(n)}i<ω of the set of formulas of rank < β with n as the only free variable.

Let φ(xβ) be a formula of rank ≤ β whose only free ranked variable is xβ. For the formula (∃xβ)φ(xβ), (, x) (∃xβ)φ(xβ) if and only if there is a j such that (, x) ⋁i≤j φ(ψi). By Theorem 13.1.3, there is a hyperarithmetic function taking each m to a large enough j such that

By induction hypothesis, there is a formula φ′ corresponding to (i. e. ⌜φ′⌝= f(⌜∨i≤jφ(ψi)⌝, m + 1)) so that

Then μ({x | (, x) (∃xβ)φ(xβ)}) − μ({x | (, x) φ′}) < 2−m. Let , m) = .

For (∀xβ)φ(xβ), we have (, x) (∀xβ)φ(xβ) if and only if for all j < ω, (, x) ⋀i≤j φ(ψi). By induction hypothesis, there is a hyperarithmetic function taking each j to a formula corresponding to φ(ψi) (i. e. , m + j + 2) so that

Now {x |(∀j)(, x) } is hyperarithmetic. Hence there is a ranked formula φ′ such that for any x,

Note that the set {x | (, x) φ′} is closed. Moreover,

Thus define . For the other cases, the definition of f is straightforward.

Corollary 13.1.11. If A is and μ(A)= r where r is hyperarithmetic, then there is a -set B ⊆ A such that μ(B)= μ(A).

Proposition 13.1.12 (Kechris [63]). Assume that < ω1. Suppose that A ⊆ 2ω is a -set with positive measure. Then for any n, there is a perfect set Bn ⊆ A such that μ(A)< μ(Bn)+ 2−n. Furthermore, if μ(A) is , then {(n, x)| x ∈ Bn ∧ n < ω} is .

Proof. Since A is , there is a relation R such that

Let p be a rational between μ(A) and μ(A)− 2−n. By an argument similar to that for Corollary 13.1.7, μ(A)> p if and only if there is an r ∈ L coding a well-ordering of ω such that μ({x |(∃y ∈ L|r|[x])R(x, y)}) > p. Let C ={r | r codes a well-ordering of ω ∧ μ({x |(∃y ∈ L|r|[x])R(x, y)}) > p}. Then C is a nonempty -set. Hence there is an rn ∈ C which is . Let

Then Bn ⊆ A is and μ(Bn)> p > μ(A)− 2−n. The other part of the proposition follows from the above.

The following is a measure-theoretic basis theorem:

Theorem 13.1.13 (Sacks [120]). If A ⊆ 2ω is a -set with positive measure, then A contains a hyperarithmetic real.

Proof. Suppose that A ⊆ 2ω is a -set with positive measure. By Corollary 3.7.4, there is an arithmetical formula φ(x, z) such that

Let B ={x | (, x) (∃z)φ(x, z)}. Then B ⊆ A. By Theorem 13.1.4, μ(B)= μ(A)> 0. By Lemma 13.1.10, there is a closed nonempty set C ⊆ B which is defined by a ranked formula ψ(). Let

Then, by Lemma 13.1.1, [T]⊆ C is a hyperarithmetic tree. The leftmost infinite path in T is hyperarithmetic.

13.1.4 Exercises

Exercise 13.1.1. Let A ⊆ ω × 2ω be and let An ={x |(n, x)∈ A}. Show that the set {(n, p)| μ(An)≥ p ∧ p is rational} is .

Exercise 13.1.2. Prove that if A ⊆ 2ω is , then μ(A)≤T

Exercise 13.1.3. Prove that for any real x, the set {y |(∀z)(z ≤h x ∧ z ≤h y → z ∈ HYP)} has measure 1.

Exercise 13.1.4. Prove Corollary 13.1.11.

Exercise 13.1.5. Prove that for any recursive ordinal β, there is a hyperarithmetic set A with measure 1 such that no real in A is recursive in (β).

Exercise 13.1.6 (Jockusch). If A ⊆ 2ω is a -set containing no hyperarithmetic real, then the set {x |(∃y)(y ∈ A ∧ y ≤h x)} is null.

Exercise 13.1.7. Assume V = L. Prove that for any x, {y | x y} has measure 1.

13.2 Coding sets above Kleene’s

13.2.1 A join basis theorem for -sets

The question whether there is an uncountable -set A such that x ⊕ y for any x, y ∈ A was raised in Friedman [29] and Simpson[138]. A negative answer was given by Harrington (unpublished). The following is a stronger version which is used to study higher randomness theory.

Theorem 13.2.1 (Chong and Yu [14]). Let A0 and A1 be uncountable -sets. For any z ≥h , there exist x0 ∈ A0 and x1 ∈ A1 such that x0 ⊕ x1 ≡h z.

Proof. Fix a real z ≥h and two uncountable -sets A0 and A1. Then there are two recursive trees T0, T1 ⊆ 2<ω × ω<ω such that for i ≤ 1, Ai ={x |∃f ∀n(x ↾ n, f ↾ n)∈ Ti}. We may assume that neither A0 nor A1 contains a hyperarithmetic real. Also assume that if (σ, τ)∈ Ti, i ≤ 1, then |σ|=|Dom(τ)|. Let T2 ⊆ ω<ω be recursive so that [T2] is uncountable and does not contain a hyperarithmetic infinite path. Let be the leftmost path in T2. Then .

For i ≤ 1, let [Ti]={(x, f)|∀n((x ↾ n, f ↾ n)∈ Ti)}. Our plan is to define xi ∈ Ai such that z ≡h x0⊕x1. To this end, a procedure of coding z and into x0 and decoding them from x0⊕x1 will be introduced. Construction of xi will be carried out in [z] on the recursive tree Ti, hence hyperarithmetically in z (since z ≥h ). Since Ai is , x1−i will also code in the function fi which is the leftmost path in the second component of [Ti] serving as a witness to xi being in Ai (i. e. (xi, fi) ∈ [Ti] and for any f , if (xi, f) ∈ [Ti] and fi ≠ f, then the least n where fi(n) ≠ f(n) satisfies fi(n)< f(n)). Since Ai has no hyperarithmetic member, for any (σ, τ) ∈ Ti, if σ ≺ x and τ ≺ f for some (x, f) ∈ [Ti], then there exist incompatible extensions σ′ and σ″ of σ, and (possibly compatible) extensions τ′, τ″ of τ, so that (σ′, τ′) and (σ″, τ″) both have extensions in [Ti]. This “splitting property” of [Ai] allows the coding of z, f1 and in x0 and the coding of f0 in x1. More specifically, the branch to be selected by x0 at a splitting node when z(s) is to be coded (at stage s + 1 of the construction) will follow the value of z(s), so that a “left turn” is taken if z(s)= 0 and a right turn is taken if z(s)= 1. The coding at stage s + 1 of τ1,s, which denotes the initial segment of f1 defined at the end of stage s, is accomplished by taking τ1,s(t)-many consecutive left turns at splitting nodes, for each t ∈ Dom(τ1,s). The coding of (s) at stage s + 1 of the construction is carried out by taking left turns at (s)-many consecutive splitting nodes.

For the purpose of decoding, one has to delineate different types of action taken during the coding phase. Since τ1,s is a finite function, the end of coding the value τ1,s(t) and the beginning of coding the value τ1,s(t + 1), for t <|Dom(τ1,s)|, is separated by a right turn at the splitting node between the two codings (of course since the construction is executed stage by stage, one may assume that at the beginning of stage s + 1, the coding of τ1,s−1 is already completed. This means that at stage s + 1, one only needs to code the values τ1,s(t) for t ∈ Dom(τ1,s) Dom(τ1,s−1)). A “right turn” is chosen at the next splitting node to signify the end of coding τ1,s, and the beginning of the coding of (s). Finally, a right turn is taken at the next splitting node after coding (S) to mark the end of the coding action for x0 at stage s + 1. This initial segment of x0 coded at stage s + 1 is denoted σ0,s+1. Then τ0,s+1 ≺ f0 is a finite string in ω<ω such that |Dom(τ0,s+1)| = |σ0,s+1|, τ0,s+1 extends τ0,s, and is the leftmost such string. The coding of the initial segment τ0,s+1 of f0 in x1 at stage s + 1, denoted σ1,s+1, proceeds in a similar fashion. The definition of τ1,s+1, an initial segment of f1 constructed at stage s + 1, follows the same format.

We now describe the construction of x0 and x1 and the associated strings in detail. For i ≤ 1and σ, τ ∈ Ti, let Ti(σ, τ) be the set of strings in Ti compatible with σ and τ), i. e.

Note that it is unnecessary that |σ|=|τ| in the definition above.

We say that a string (or node) σ∗ ∈ 2<ω is splitting over (σ, τ) in Ti if σ∗ σ and for j ≤ 1,

contains an infinite path. is the subtree of Ti with root σ∗⌢j in its first component (note that σ∗ σ). Since Ai has no hyperarithmetic path, for each j ≤ 1, there is a string that splits over some (σ′, τ′) in . Note that σ∗ does not lie on Ti but some pair (σ∗, τ′) does and we call (σ∗, τ′) a splitting node on Ti.

For each i ≤ 1, we construct a sequence (σi,0, τi,0)≺(σi,1, τi,1) ≺ … on Ti and let . Again, the idea is to apply a “mutual coding” technique so that x0 codes the leftmost witness function f1 =∪sτ1.s (in the -definition) for x1 and x1 codes the leftmost witness function f0 =∪sτ0,s for x0. In addition, we also assign x0 the responsibility of coding z as well as . More precisely, for each s ∈ ω we use σ0,s to code z(s), (s) and τ1,s−1, and use σ1,s to code τ0,s.

At stage 0, let (σi,0, τi,0)=(, ) for i ≤ 1. Without loss of generality, assume that (0, 0) is a splitting node in both T0 and T1.

The construction at stage s + 1 proceeds as follows:

Substage (i). First let σ∗ be the shortest splitting node over (σ0,s, τ0,s) in T0. Thus contains an infinite path for j ≤ 1. Let be the leftmost splitting node over (σ0,s, τ0,s) extending σ∗⌢z(s) in T0. Thus z(s) is coded here. Next we code τ1,s. Let =|Dom(τ1,s)| − |Dom(τ1,s−1)| (let |Dom(τ1,s−1)| = 0 if s = 0). Inductively, for any k ∈ [1, ], let σk0,s+1 be the leftmost splitting node over (σ0,s, τ0,s) extending in T0 so that there are τ1,s(k +|Dom(τ1,s−1)|)-many splitting nodes over (σ0,s, τ0,s) in T0 between and . This completes the coding of τ1,s. To code (s), let be the leftmost splitting node extending over (σ0,s, τ0,s) in T0 so that there are (s)-many splitting nodes in T0 over (σ0,s, τ0,s) between and . For j ≤ 1, let be the next splitting node in T0 over (σ0,s, τ0,s) extending . This coding tells us that the action at this substage for the “x0 side” is completed. Define σ0,s+1 = σn . Let τ0,s+1 extend τ0,s so that |Dom(τ0,s+1)| = |σ0,s+1| and τ0,s+1 is the leftmost node such that the tree T0(σ0,s+1, τ0,s+1) has an infinite path.

Remark. At stage s + 1, the coding of x0 in T0 by way of σ0,s+1 applies he method of the proof of 11.1.1, treating the -set A0 as a “closed set”. This means that one first ignores the second component (the “τ side”) and applies the coding construction in the proof of Theorem 11.1.1 to the closed set τ0,s(x ↾ n = y ↾ n ∧(y, f) ∈ [T0])}. Once the coding of σ0,s+1 (an initial segment of x0) is completed, one pairs it with a finite string τ which has an infinite extension to guarantee that x0 belongs to A0. Since x0 does not know the right τ to select, x1 is designed to help decode the correct τ. The mutual coding strategy is crucial for this purpose.

Substage (ii). Let = σ1,s and =|Dom(τ0,s+1)| − |Dom(τ0,s)|. Inductively for any k ∈ [1, ], let be the leftmost splitting node over (σ1,s, τ1,s) extending so that in T1 there are τ0,s+1(k +|Dom(τ0,s)|)-many splitting nodes over (σ1,s, τ1,s) between and . Hence τ0,s+1 is coded. For j ≤ 1, let be the next splitting node over (σ1,s, τ1,s) in T1 extending . This coding tells us that the action of coding τ0,s+1 at this substage for the “x1 side” is completed. Define σ1,s+1 = . Thus we have coded τ0,s+1 into σ1,s+1. Let τ1,s+1 extend τ1,s so that |Dom(τ1,s+1)| = |σ1,s+1| and τ1,s+1 is the leftmost finite string such that the tree T1(σ1,s+1, τ1,s+1) has an infinite path.

This ends the construction at stage s + 1.

Let xi = σi,s for i ≤ 1. Note that the construction is carried out over [Z] since ∈ and whether (σ, τ) ∈ Ti has an infinite path extension in Ti is decided by stage . As z ≥h we have > and so z ≥h x0 ⊕ x1.

We now use x0 and x1 to decode the coding construction and hence hyperarithmetically recover and z from x0 ⊕ x1. The decoding is achieved via a finite injury method similar to that used in the proof of Theorem 11.1.1. However, a correct decoding requires use of the witness functions f0 and f1. Without these witness functions, x0 would still code z and would belong to the closure of A0. The entire construction is then reduced to that in the proof of Martin’s Theorem 11.1.1. However, in this case one cannot conclude that x0 belongs to A0. This difficulty is resolved by a procedure of mutual coding, in which x0 also codes f1 and x1 codes f0. The coding of z is weaved into the mutual coding strategy in the course of the construction.

We now point out the key decoding steps and leave the details to the reader. As in the proof of Theorem 11.1.1, we may fix a Σ1-enumeration over such that for i ≤ 2,

–Ti[0] = Ti

–Ti[α]⊆ Ti[β] if α ≥ β

–Ti[] = Ti[α]

–Ti[] has no dead end nodes, and

–Ai ={x |∃f ∀n(x ↾ n, f ↾ n) ∈ Ti[]}.

Since [Ti] does not contain a hyperarithmetic infinite path, we have [Ti[]] = [Ti] to be a perfect tree (which as noted earlier enabled the coding procedure to be implemented). Clearly (xi, fi) is an infinite path in Ti[α] for each α. As was the case for Ti, i ≤ 1, for each α < one may define the notion of a string σ′ being a splitting node over (σ, τ) in Ti[α]. In particular, for (σ, τ) ∈ Ti[α] such that σ ≺ xi, it makes sense to say that xi ↾ n splits over (σ, τ) in Ti[α]. This means that there are strings τi0, τi1 τ such that (xi ↾ n⌢0, τi0), (xi ↾ n⌢1, τi1) ∈ Ti[α]. In this case we also say that xi ↾ n is a locally splitting node over (σ, τ) in Ti[α]. Here “local” refers to the fact that there is no guarantee that (xi ↾ n⌢j, τij) has an infinite extension in Ti[α] for j = 0, 1.

Since for each i ≤ 1 and α < , 〈xi, fi〉 is a path on Ti[α], one may use x0 ⊕ x1 to approximate the values of (s) and fi(s) by simulating in Ti[α] the construction of xi. This is achieved by attempting to retrieve the sequences {(σi,s, τi,s)}s<ω, i ≤ 1, using x0 ⊕ x1. Of course, since it is yet to be established that z and are hyperarithmetic in x0 ⊕ x1, the retrieval is only by way of approximating the original construction. Using x0⊕x1, one may mimic the construction of {(σi,s, τi,s)}s<ω to define {(σi,s[α], τi,s[α])}s<ω, for i ≤ 1, so that σi,s+1[α] is an initial segment of xi (in ascending order of length) and a local splitting node over (σi,s[α], τi,s[α]) in Ti[α]. Furthermore, for each i, τi,s+1[α] is an approximation of fi ↾ s at stage α. In other words, τi,s+1[α] is the leftmost finite string so that (σi,s+1[α], τi,s+1[α]) ∈ Ti[α](σi,s, τi,s).