Note that for each n and α < α′ < , the number of splitting nodes along (xi ↾ n, fi ↾ n) in Ti[α] is greater than or equal to that in Ti[α′].

One may use T2[α] to define a Σ1(-approximation of “from the left”: (O) [α] ⌢…⌢ (n)[α] is the leftmost string in T2[α] (it is possible that there exist only finitely many such n’s.). Then for α < , (0)[α] ≤ (0). Suppose n > 0 and (m)[α]= (m) for all m < n. Then (n)[α]≤ (n), and lim.

The algorithm we adopt for decoding proceeds as follows. Construct a sequence of ordinals {αs}s<ω which is Δ1-definable in [x0 ⊕ x1] so that lims→ω αs = , and use it as a parameter to decode the real z, and thereby conclude that x0 ⊕ x1 ≥h z.

Let ĝO,0(0)= (0) and α0 = 0.

We say that x0 ⊕ x1 consistently computes fO up to j at stage α if for every k < j,

(1)τ1,k[α] agrees with that coded in x0 using σ0,k+1[α]. In other words, let [α] be the shortest locally splitting node over (σ0,k[α], τ0,k[α]) in T0[α]. Then there is a [α] which is the leftmost locally splitting node over (σ0,k[α], τ0,k[α]) extending [α]⌢i, for some i ∈ {0, 1}, Moreover, inductively for each l ∈ [1, n0k+1[α]] where n0k+1[α]=|Dom(τ1,k[α])| − |Dom(τ1,k−1[α])|, let σl0,k+1[α] be the leftmost locally splitting node over (σ0,k[α], τ0,k[α]) extending ([α])⌢1 in T0[α]. Then there are τ1,k[α](l +|Dom(τ1,k−1[α])|)-many locally splitting nodes over (σ0,k[α], τ0,k[α]) in T0[α] between [α] and [α];

(2)The approximation of via T2 using at stage α agrees with that via {σ0,l[α]}l≤k up to the decoding of ↾ k. In other words, let [α] be the leftmost locally splitting node extending [α])⌢1 in T0[α] over (σ0,k[α], τ0,k[α]) so that there are (k)[α]-many nodes which are locally splitting over (σ0,k[α], τ0,k[α]) in T0[α] between [α] and [α]. For i ≤ 1, let [α] be the next local splitting node in T0[α] over (σ0,k[α], τ0,k[α]) extending . Then σ0,k+1[α]= [α], and

(3)τ0,k+1[α] agrees with that coded in x1 using σ1,k+1[α]. Thus inductively for each l ∈ [1, [α]], where [α]=|Dom(τ0,k+1[α])| − |Dom(τ0,k[α])|, let [α] be the leftmost locally splitting node over (σ1,k[α], τ1,k[α]) extending in T1[α] so that there are τ0,k+1[α](l+|Dom(τ0,k[α])|)-many locally splitting nodes over (σ1,k[α], τ1,k[α]) in T1[α] between [α] and [α]. For i ≤ 1, let [α] be the next local splitting node over (σ1,k[α], τ1,k[α]) in T1[α]. Then .

Note that at any stage α, we may assume that x0 ⊕ x1 always computes consistently up to 0. Furthermore, for each α < and j ∈ ω, there is always an α′ ≥ α such that α′ < and x0 ⊕ x1 consistently computes up to j at stage α′.

Suppose that αt−1 is defined where t ≥ 1. Search for the least stage α > αt−1 so that x0 ⊕ x1 consistently computes up to t at α. Let αt = α andĝO,t(j)= (j)[αt] for each j ≤ t.

This completes the construction at step t.

We verify that the decoding construction yields an algorithm to hyperarithmetically compute z from x0 ⊕ x1.

Let

Clearly and is a limit ordinal. Furthermore . We prove that .

Suppose for the sake of contradiction that . Using the fact that neither x0 nor x1 is hyperarithmetic, we will show that for i ≤ 1, each sequence of parameters [αt], σi,t[αt] and τi,t[αt] introduced in the decoding procedure above eventually stabilizes as t → ω. Suppose this is false. Then there is a least j0 and a corresponding least t0 such that is consistently computed up to j0 −1, but not j0, at αt for all t ≥ t0. We argue that such a situation does not occur.

The proof proceeds by induction in the order of the introduction of the parameters at stage αj0. For convenience, we only show that reaches a limit after some t (essentially the same argument applies to show that the other sequences of parameters also stabilise). This means that for at most finitely many t’s.

Assume that does not change from stage onwards is as defined above before the decoding of ↾ k in (2)). If changes infinitely often, then for infinitely many t’s. Then by the decoding construction, we have the following claim.

Claim 1. ĝO,t+1(j0)≥ĝO,t(j0) for any t > t0 + 1 and hence limt→ω ,t(j0) = +∞.

Proof. If we assign a new value k to (j0) at some stage αt > αt0+1, it must be the case that (0)⌢ …⌢(j0 − 1)⌢k ∈ T2[αt]. However,(0)⌢ …⌢(j0 − 1) ∈ T2[] by the assumption on j0, so that k >ĝO,t−1(j0).

Claim 1 implies that at infinitely many t’s, left turns were selected at locally splitting nodes in T0[αt] during the decoding phase for the purpose of approximating (j0).

Let and . Note that . Define

If we let ̂p (T)={σ |∃τ(σ, τ) ∈ T} be a “local projection” of a tree T ⊆ ω<ω × ω<ω, then it is not difficult to see that is a tree (Note: denotes the analog of for T0[β]). Moreover,

In other words, X consists of all the reals x “potentially” with an accompanying witness f so that (x, f) is an infinite path in . Note that since , X is a closed subset of 2ω.

Claim 2. x0 is the leftmost path in X.

Proof. Suppose not. Then there exist y0 and σ such that , and .

Now by Claim 1 let t1 > t0 be such that for all t ≥ t1. Then there are τ, τ′ of length |σ| so that (x0 ↾|σ|+ 1, τ), (y0 ↾|σ|+ 1, τ′) ∈ T0[αt1+1]. However, since y0 is to the left of x0, the value of coded by x0 is at most |σ|+ 1. Thus ≤|σ|+ 1, a contradiction.

Claim 2 implies that x0 is hyperarithmetic which is a contradiction. Hence there is a t0 such that for any and so is a constant for all t > t0.

We leave it to the reader to verify the stabilization of the other sequences of parameters.

It follows that for each j, there is a tj such that for t ≥ tj. Define . Then and . Now ĝ is the leftmost path in and so in T2 as well. Thus . This contradicts the assumption that . Hence and so ≤h x0 ⊕ x1.

Using this, one may decode the entire construction in Ti[] and conclude that z ≤h x0 ⊕ x1, completing the proof of the Theorem.

13.2.2 Exercise

Exercise 13.2.1. Prove that there exists an uncountable -set A such that for any x, y ∈ A.

13.3 Hyperarithmetic computation

In this section, we discuss some notions concerning effective bounding in the context of hyperarithmetic theory. The results will be applied to study higher randomness.

13.3.1 Hyperarithmetic domination

Definition 13.3.1. A real x is -dominated if for any function f : ω → ω with f ≤h x, there is a hyperarithmetic g such that (∀n)(g(n)> f(n))(written as g > f).

The first item to note is that there is an abundance of -dominated reals.

Theorem 13.3.2 (Chong, Nies and Yu [12]). μ({x | x is -dominated}) = 1.

Proof. We prove that for any rational number p,

This is achieved with the use of a fusion argument.

First we show that for any e, rational r, notation n ∈ and -set A where p + r < μ(A), there is a hyperarithmetic function f such that

Note that the set is . Since A is , Proposition 13.1.6 implies that the set

is . Note that for each k, there is an m such that (k, m, k) ∈ C. Hence there is a total function f such that for all k, (k, f(k), k) ∈ C. Define

Then the set {(k, x)| x ∈ Bk} is . Moreover, for every k, Bk ⊆ A and μ(Bk)> . Hence Bk is and

Now for every x ∈ B, if is total, then < f . Thus we may construct an ω-sequence of -sets {B〈e,n〉}e<ω,n ∈ O such that

(1)if 〈e, n〉>〈e′, n′〉, then B〈e,n〉 ⊆ B〈e′,n′〉;

(2)μ(B〈e,n〉)> p.

Define

By Theorem 13.1.4, D ⊆{x|x is -dominated} and μ(D)≥ p.

It is obvious that if x is -dominated, then = . The converse is however false.

Proposition 13.3.3. There is an uncountable -set A in which every x hyperarithmetically computes an f such that f > g for every hyperarithmetic function g.

Proof. It is immediate that there is a Turing oracle function Φ such that dominates all the hyperarithmetic function. Let

By Corollary 2.2.12, A is . Since ∈ A, by Lemma 2.5.4, A is uncountable. Hence by the Gandy Basis Theorem (2.5.3), we have the following conclusion.

Corollary 13.3.4. There is an x with = which is not -dominated.

13.3.2 Traceability

Definition 13.3.5.

(i)Let h be a nondecreasing unbounded and hyperarithmetic function. A -trace/ -trace with bound h is a / -set T ⊆ ω × ω such that |Te|≤ h(e) for each e where Te ={k |(e, k) ∈ T}.

(ii)x is -traceable/-traceable if there is an h ∈ such that, for each f ≤h x, there is a -trace/ -trace T with bound h satisfying f(e) ∈ Te for each e.

It is not difficult to see that the bounding function h may be chosen to be any hyper-arithmetic function, for example h(e)= e for every e.

Proposition 13.3.6 (Chong, Nies and Yu [12]). If x is -traceable, then x is -traceable.

Proof. Firstly we show that = . It is sufficient to show that is not -traceable. Since each -set is many-one reducible to , there is a uniformly -recursive list (Te)e<ω of all -traces for the bound h(e)= e. Define f ≤h by

Then f does not have a trace. Now given f ≤h x, there is a -trace (Te)e<ω such that f(e) ∈ Te for each e. Then there is a recursive function h : ω2 → ω such that k ∈ Te if and only if h(k, e) ∈ . Define a (x)-relation R ⊆ ω × by

Note that for each e, there is a notation n ∈ such that (e, n) ∈ R. By the -Uniformization Theorem (4.2.1), there is a total (x) (and hence (x)) function g uniformizing R. Since = , there exists a notation n0 ∈ so that |g(e)| < |n0| for every e. Define a set as follows:

By the definition of n0, f(e) ∈ for all e ∈ ω. Note that the relation n ∈ is . Hence is a -trace for f . It follows that f is -traceable.

There is also a plentiful supply of -traceable reals. In fact every Sacks generic real is -traceable.

Proposition 13.3.7. Every Sacks generic real is -traceable.

Proof. Suppose x is Sacks generic. Then = . If f ≤h x, then there is an e and a notation n ∈ such that = f . Note that the ranked formula

defines the set . For simplicity, we may view as a ranked formula. Since is total, by Lemma 5.3.6, there is a condition T ⊩ “ is total”. We show that for each condition S ⊆ T, there is a condition Q ⊆ S such that

Then by the definition of forcing, there is a function f such that for all i, (i) ∈ Df(i) ∧|Df(i)|≤ 2i+1. Since T ⊩ “ is total”, S also forces the same sentence. We consider two cases.

Case 1. There is a condition R ⊆ S such that for all i, j0, j1 and for all conditions P0, P1 ⊆ R, if P0 ⊩ (i) = j0 and P1 ⊩ (i) = j1 then j0 = j1. In this case define f(i) = j if and only if there exists a condition P ⊆ R such that P ⊩ (i) = j (i) = j. Then f is a total -function and hence . This implies that R ⊩ f = .

Case 2. Otherwise. Define a -relation as

By the -Uniformization Theorem (4.2.1), there is a -function F : 2ω × 2<ω → (ω)3 ×(2ω)2 such that holds if and only if .

Without loss of generality, we assume that if then for all k ≤ i, for some jk. Define by induction on ω a -sequence of conditions as follows:

Step 0. Let = S.

Step n + 1. For each σ ∈ 2n, define if , Q0, Q1).

Let G(σ) = Pσ. Then G is a total -function and so . Note that for each σ, G(σ⌢0)∩ G(σ⌢1) = and if σ τ then G(σ)⊇ G(τ). Let

Then Q is a -perfect set.

Define g : → ω such that g(i, σ) = k if σ ∈ 2i+1 and G(σ)⊩ (i) = k. Hence g is a total and therefore -function. Define f(i) = j if j is the least number such that Dj ={g(i, σ)| σ ∈ 2i+1}. Then f is a -function and |Df(i)|≤ 2i+1 for all i. Since for all i, , it is easy to see that Q ⊩ (i) ∈ Df(i). It follows that x is -traceable.

We will see later (Theorem 14.6.8) that the collection of -traceable reals is null.

By Theorem 5.3.12, there is an uncountable -set of weakly-Sacks-generic reals in which every real x has the property = . By the proof of Proposition 13.3.7, it is easy to derive the following conclusion.

Corollary 13.3.8. There is an uncountable -set of -traceable reals.

13.3.3 Semitraceability

Definition 13.3.9.

(i)x ∈ 2ω is -semitraceable if for each f ≤h x, there is a -function g such that, for infinitely many n, f(n) = g(n). We say that g semitraces f .

(ii)x ∈ 2ω is -semitraceable if for each f ≤h x, there is a partial -function p such that for infinitely many n we have f(n) = p(n).

Lemma 13.3.10. x is -semitraceable if and only if x is -semitraceable.

Proof. It is not difficult to see that if x is -semitraceable, then = . Since x ≥h otherwise. Hence it suffices to show that is not -semitraceable. Let {ϕi}i<ω be an effective enumeration of partial recursive functions. Let be the least k such that pj(i, k) ∈ if it exists, and let it be 0 otherwise. Define a function g ≤T ′ such that g(i) = ∑j≤i mij + 1. Note that for any -partial function p, there is a partial recursive function pj such that for every pair n, m, p(n) = m if and only if pj(n, m) ∈ . Then by the definition of g, forany i > j, g(k) ≠ = p(i). Hence g is not traced by p.

Suppose that x is -semitraceable, = , and f ≤h x. Fix a -partial function p for f witnessing the semitraceability of x. Since p is a -function, there is a recursive injection h such that p(n) = m ⇔ h(n, m) ∈ .

Let R(n, m) be a (x)-relation such that R(n, m) if and only if there exists a k, where m > k ≥ n, so that f(k) = p(k). Then there is a total function g uniformizing R such that g is (x), and hence (x). Thus for every n there is an m ∈ [g(n), g(g(n))) such that f(m) = p(m). Let g′(0) = g(0), and g′(n + 1) = g(g′(n)) for all n < ω. Define a (x)-relation S(n, m) such that S(n, m) if and only if m ∈ [g′(n), g′(n + 1)) and p(m) = f(m). Uniformizing S, we obtain a (x)-function g″.

Let H ={h(m, k)|(∃n)(g″(n) = m ∧ f(m) = k)}. Then H is (x) and since = , H ⊆ n for some n ∈ . Since n is , we may define a -function by setting (i = j if h(j, j) ∈ n and (i) = 1 otherwise. Then there are infinitely many i such that (i) = (i).

The following clarifies the relationship between traceability and semitraceability.

Proposition 13.3.11 (Kjos-Hassen, Nies, Stephan and Yu [68]). Every -traceable real is -dominated and -semitraceable.

Proof. Clearly every -traceable real is -dominated. Let x be a -traceable real and let f be a (x)-function. Define g(n) =〈f(2n), f(2n + 2),..., f(2n+1 − 1)〉. Then there is a trace T for g such that |Tn|≤ n for all n.

For 2n + 1 ≤ m ≤ 2n+1, let (m) = the (m − 2n)-th entry of the tuple which is the (m − 2n)-th element of Tn if there exists such a tuple, and let (m) = 1 otherwise. It is not difficult to see that for every n there is at least one m ∈ [2n, 2n+1) such that f(m) = (m).

Corollary 13.3.12. A real x is -traceable if and only if for every hyperarithmetic in x, there is a hyperarithmetic f such that

Proposition 13.3.13. For any x, the following are equivalent.

(i)x is -semitraceable and -dominated;

(ii)For every function g ≤h x, there exist an increasing -function f and a -function F : ω → (ω) with |F(n)| ≤ n such that

Proof. (i) ⇒ (ii): Immediate because 1 ≤ n.

(ii) ⇒ (i). Suppose ĝ ≤h x. Without loss of generality, assume ĝ is nondecreasing. Let f and F be the corresponding -functions. Let u(n) = ∑i≤f(n+1) ∑k∈F(i) k and note that u is a -function dominating ĝ. Let

Then by assumption there are corresponding -functions fh and Fh. For every n and m ∈ [2n, 2n+1), let g(m) = the (m − 2n)-th entry of the (m − 2n)-th element in Fh(n) if such an m exists, and let g(m) = 1 otherwise. Then g is a -function semitracing ĝ.

To separate -traceability from the conjunction of -semitraceability and -domination, one applies a modified Sacks forcing construction.

Definition 13.3.14.

(i)A -perfect tree T ⊆ 2<ω fully splits at n if for every σ ∈ T with |σ| ∈ [2n,2n+1), both σ⌢0 and σ⌢ 1 are in T. Then n is said to be a fully splitting level of T.

(ii)A -perfect tree T ⊆ 2<ω is clumpy if there are infinitely many n’s where T fully splits at n.

Let = 〈F, ⊆〉 be the partial order of clumpy trees ordered under inclusion. Given a formula φ in the language (, ̇x) of ramified analytical hierarchy (§ 5.1.1), define the forcing relation T ⊩ φ as in Sacks forcing:

–If φ is a ranked sentence and (∀x ∈ T)((, x) φ), then T ⊩ φ.;

–if φ(y) is unranked and T ⊩ φ(y | ψ) for some ψ of rank at most β, then T ⊩ (∃yβ)φ(yα);

–if T ⊩(∃yβ)φ(yα), then T ⊩(∃y)φ(y);

–if φ(n) is unranked and T ⊩ φ() for some numeral , then T ⊩(∃n)φ(n);

–if φ and ψ are unranked, T ⊩ φ and T ⊩ ψ, then T ⊩ φ ∧ ψ;

–if φ is unranked and (∀P)(P ⊆ T → P φ), then T ⊩¬φ.

By Theorem 5.1.1, we have the following.

Lemma 13.3.15. The set

is .

Lemma 13.3.16.

(i)Let {φi}i<ω be a hyperarithmetic sequence of -sentences. Suppose that for every i and Q ⊆ T, there exists an R ⊆ Q such that R ⊩ φi. Then there exists an R ⊆ T such that R ⊩ φi for every i.

(ii)(∀φ)(∀T)(∃Q ⊆ T)(Q ⊩ φ ∨ Q ⊩¬φ).

Proof. Using the notation P ↾ n ={τ ∈ 2≤n | τ ∈ P}, define a -relation by

Then is uniformized by a partial -function F : F × ω × 2<ω → F. Using F, a hyperarithmetic family {Pσ | σ ∈ 2<ω} may be defined by recursion on σ.

Let P0 = T. If σ Pσ, let . If log |σ|− 1 is not a fully splitting level of Pσ, set Pσ⌢0, Pσ⌢1 = Pσ. Otherwise, |σ|={τ | τ ≺ σ} and Pσ⌢0, Pσ⌢1 ⊩ ⋀j≤i φj where log |σ|− 1 is the i-th fully splitting level of T.

Let . Then R ∈ F. It is routine to verify that R ⊩ φi for every i.

The proof of (ii) is similar to the proof of Lemma 5.3.4.

A real x is generic if for every dense set ⊆ F arithmetical in , there is a T ∈ such that x ∈ [T]. One can show as in the proof of Lemma 5.3.6 that for every sentence φ and generic x,

Lemma 13.3.17. If x is generic, then

(i)(, x) satisfies -comprehension. Hence = ;

(ii)x is -dominated and -semitraceable;

(iii)x is not -traceable.

Proof. The proof of (i) is the same as that of Lemma 5.3.7 and is left to the reader.

For (ii), by Proposition 13.3.13, it suffices to show that for every function g ≤h x, there exist an increasing -function f and a -function F : ω → ω<ω such that

(1) |F(n)| ≤ n;

(2) every interval [f(n), f(n + 1)) captures an m with g(m) ∈ F(m).

Since g ≤h x and = , there is a ranked formula φ such that for every n, g(n) = m if and only if (, x) φ(n, m). Hence there is a condition S ⊩ (∀n)(∃!m)φ(n, m). Let T ⊆ S. As in the proof of Lemma 13.3.16, one can build a hyperarithmetic sequence of conditions such that

where σ ∈ Pσ and log |σ|− 1 is a fully splitting level of Pσ. Let Q be as defined in the proof of Lemma 13.3.16. Let f be the -function such that f(0) = 0, and f(n + 1) is the least number k > f(n) so that mσ is defined for some σ with f(n)<|σ|< k. Let F(n) ={0}∪{mσ ||σ|= n}, and note that F is a -function. Then

This implies that

Since T is an arbitrary condition stronger than S, one has

Since x ∈ S,

Thus x is -dominated and -semitraceable.

For (iii), suppose f : ω → ω is a -function such that for every n, there is an m ∈ [2n,2n+1) with f(m) = x(m). Then there is a ranked formula φ such that f(n) = m ⇔ (, x) φ(). Moreover, (, x) (∀n)(∃m ∈ [2n,2n+1))(φ(m, x(m))). Hence there is a condition T which forces (∀n)(∃m ∈ [2n,2n+1))(φ(m, ̇x(m))) and x ∈ T. Let n be such that T is fully splitting at level n and let σ ∈ 22n−1 be a string in T. Let ν be a string such that ν(m) = 1− f(m +2n −1). Define S ={σ⌢ν⌢τ | σ⌢ν⌢τ ∈ T}⊆ T. Then S ⊩(∀m ∈ [2n,2n+1))(¬φ(m, x(m))). But S is stronger than T, which is a contradiction. By Corollary 13.3.12, x is not -traceable.

We may now separate -traceability from the conjunction of -semitraceability and -dominability.

Theorem 13.3.18 (Kjos-Hanssen, Nies, Stephan and Yu [68]). There are many -dominated and -semitraceable reals which are not -traceable.

Proof. This is immediate from Lemma 13.3.17. Note that there are many generic reals.

By exactly the same argument as in the proof of Theorem 5.3.12, we have the following.

Proposition 13.3.19. There exists an uncountable -set which contains only -dominated and -semitraceable reals.

13.3.4 Exercises

Exercise 13.3.1. Prove that no Cohen generic real is -dominated.

Exercise 13.3.2. Prove that every Cohen generic real is -semitraceable.

Exercise 13.3.3. Prove Proposition 13.3.19.