2.5.2 Incomparable hyperdegrees

We apply the Gandy Basis Theorem to construct a pair of incomparable hyperdegrees.

Lemma 2.5.4. If A is a -set containing a nonhyperarithmetic real, then A is uncountable.

Proof. Suppose that A is a countable -set containing a nonhyperarithmetic real. Then the set B = {x ∈ A | x ≰h } is a nonempty -subset of A. Hence there is a recursive tree T such that x ∈ B if and only if there exists a y satisfying for every n, (x ↾ n, y ↾ n) ∈ T. Let T′ = {(σ, τ) | (∃x ≻ σ)(∃y ≻ τ)(∀n)((x ↾ n, y ↾ n) ∈ T)} be a subtree of T.Obviously T′ is a -tree. Moreover, for any (σ, τ) ∈ T′, there are σ0, σ1 ≻ σ and τ0, τ1 ≻ τ with σ0|σ1 so that (σi, τi) ∈ T′ for i ≤ 1. Otherwise, the -set {x | (∃y)(∀n)(x ≻ σ ∧ y ≻ τ ∧(x, y) ∈ T′)} ⊆ B contains a unique real which must be hyperarithmetic, contradicting the definition of B. Thus imitating the proof of Theorem 1.1.10, one shows that B contains a perfect subset.

Theorem 2.5.5 (Spector [155]). There exist reals x and y such that x ≰h y and y ≰h x.

In fact, there is a real x ≰h with = .

Proof. Let A = {x | x ≰h } be a nonempty -set. By Theorem 2.5.3 and Corollary 2.4.11, the set B = {x ∈ A | = } is a nonempty -set. By Lemma 2.5.4, B is uncountable. Since there are at most countably many reals hyperarithmetically reducible to , there is areal x ∈ B such that x ≰h . Furthermore, x ≱h since = .

It should be pointed out that Spector’s original proof of Theorem 2.5.5 was quite different from the one given above. His proof involved a measure-theoretic argument and was nonconstructive. That idea will be explored in Chapter 14 on higher randomness.

2.5.3 Kreisel’s Basis Theorem

Theorem 2.5.6 (Kreisel [35]). If x is nonhyperarithmetic and A ⊆ ωω is a nonempty -set, then there is a y ∈ A such that x ≰h y.

Proof. Suppose that x is nonhyperarithmetic and A ⊂ ωω is a nonempty -set. By Gandy’s Basis Theorem 2.5.3, the set is a nonempty -set.

For each pair (e, n) with n ∈ , let

We claim that for any nonempty -set C, there is a nonempty -set Q(e,n) ⊆ C∩P(e,n). There are three cases to consider.

(1) There exist z ∈ C and i ∈ ω such that . Then let ∧z ∈ C)}.

(2) Not Case (1) but there exist z0, z1 ∈ C and i ∈ ω such that (i).

Then there is a k ≤ 1 such that . Let Q(e,n) = {z | (i)∧ z ∈ C)}.

(3) Neither (1) nor (2). Then the -set {u | (∃z)(∀i)(z ∈ C ∧ u(i) = (i))} contains exactly one real which must be hyperarithmetic. Let Q(e,n) = C.

By Proposition 1.1.12, there is a y ∈ B ∩ ⋂e<ω,n∈O P(e,n) ⊆ A. By the definition of . Note that . Hence by Theorem 2.3.3, we conclude x ≰h y.

Theorem 2.5.6 says that the cone of sets hyperarithmetically above one that is nonhyperarithmetic does not contain a nonempty -subset. In particular, no cone above a nonhyperarithmetic set is . From the model-theoretic point of view, the argument used in the proof of the theorem is a type-omitting argument. This will be used again later to construct nonstandard models for characterizing hyperarithmetic sets via the constructible hierarchy L.

2.5.4 Exercises

Exercise 2.5.1. Prove that for any real z, the set {(x, ) | x ∈ 2ω} is not (z).

Exercise 2.5.2. Prove that there exist x, y ≤h such that x ≰h y and y ≰h x.

Exercise 2.5.3. Prove that there is a sequence of reals {xi}i<ω such that xi <h xi+1 <h .

* Exercise 2.5.4 (Slaman [140]). Prove that there is no -set A ⊆ ωω such that every -set is a continuous injective image of A.

* Exercise 2.5.5 (Hjorth [49]). Prove that every -set is a continuous injective image of the -set { | x ∈ ωω}.

Exercise 2.5.6. Prove that any nonempty -set A contains an element x such that ≤T .

* Exercise 2.5.7 (Solovay [152]). Given functions f, g : ω → ω, we say that g dominates f if g(i)≥ f(i) for i < ω. Prove that a real x is hyperarithmetic if and only if there is a function f ≥T x such that g ≥T f whenever g dominates f.

2.6 More on

2.6.1 A nonstandard

We construct a nonstandard which shares many properties with . The following lemma says that there is an r.e. set whose field is an end extension of .

Lemma 2.6.1. There is an r.e. set x and an r.e. partial ordering relation <x defined on x such that

(i)The conditions (i)–(iv) in § 1.2.1 hold for <x;

(ii) ⊆ x;

(iii)<o is the restriction of <x to ; and

(iv)if m <x n and n ∈ , then m ∈ .

Proof. We build <x by effective transfinite induction. Define a recursive function h as follows:

By the Recursion Theorem, there is a constant c such that Φh(c) = Φc. Set g = Φc to be a partial recursive function. Hence

Define m <x n if and only if g(〈m, n〉) = 1. Set x = {m | (∃n)(m <x n}. It is straightforward to verify that the field of <x satisfies (i)–(iv).

Note that given n ∈ x, <x restricted to the set {m | m <x n} is not necessarily linear. We introduce the following modification. Define z ⊆ x to be such that i ∈ z if and only if i ∈ x and <x restricted to {m | m <x i} is linear. Then z is an arithmetical set. It is obvious that <x restricted to z is a partial ordering, ⊆ z and the conditions (i)–(iv) hold for <x restricted to z.

Now for any n ∈ , let zn be a hyperarithmetic set such that i ∈ zn if and only if i ∈ 22n or there exists j ∈ 22n 2n satisfying j <x i and i ∈ z. Inother words, zn is obtained by “cutting off” those nodes in z not above 22n. Hence zn has 22n as an “ initial segment”. Note that <x restricted to zn also satisfies conditions (i)–(iv).

Definition 2.6.2. Let * = ⋂ A where

A = {y | y ⊆ x is hyperarithmetic ∧ Conditions (i)–(iv) in § 1.2.1 hold for <x restricted to y}.

Denote by <o* the ordering <x restricted to *. Note that zn ∈ A for all n ∈ . Moreover ⊆ * by the definition of . Since conditions (i)–(iv) in § 1.2.1 are arithmetical statements, by Corollary 2.2.2 it follows that O* is .

2.6.2 A -path through

Since * is , there must be an i ∈ * . Note that for every n ∈ , i ∈ zn n. Hence for every n ∈ , there is an in ∈ 22n 2n such that in <x i and thus in <o* i. Let . Then j ∈ if and only if j ∈ ∧ j <x i. Hence ⊆ is a -set.

Lemma 2.6.3. <o restricted to is a well-ordering of order type .

Proof. Obviously <o restricted to is a well-ordering. Suppose that the order type of <o restricted to is less than . Then there is an n ∈ such that ⊆ n. Then for any k ∈ 22n 2n, k ≮o* j. Hence j ∉ zn, a contradiction.

Thus ⊆ is a -path through , yielding the following theorem.

Theorem 2.6.4 (Feferman and Spector [26]). There is a -set 1 ⊆ such that <o restricted to 1 is a well-ordering of order type .

The proof of Theorem 2.6.4 is essentially model-theoretic. A purely recursion-theoretic proof can be found in Sacks [123]. The results in this section may also be uniformly relativized. Namely, there is a -set {(x, x,*) | x ∈ 2ω} such that for each x, x,* is a proper end extension of (a nonstandard ).

2.6.3 A regular path through

Despite the apparent complexity of the partial ordering on , there is a -path through it in which every proper initial segment is recursive. This indicates that there exists certain regularity hidden within <o.

Theorem 2.6.5 (Jockusch [56]). There is set O ⊆ such that

–<o (Definition 1.2.1) is a well-ordering of order type on O;

–O is <o-downward closed, and

–for any n ∈ O, {m | m <o n} is recursive.

Proof. First, observe that by the Padding Lemma in classical recursion theory, we may assume that

By the s-m-n Theorem, there is a recursive function g0 such that for every m,

Define a recursive function h0 as follows:

By the Recursion Theorem, there is a constant c such that Φh0(c) = Φc. Then Φc is total on . Note that Φc(1) = 1, Φc(2n) = 2Φc(n), and if n = 3 ⋅ 5k, then Φc(n) = 3 ⋅ 5w where Φw(0) = Φc(Φk(0)) and Φw(j+1) = Φw(j) +o Φc(Φk(j+1)). Φc follows the format set in (i)–(iv) of § 1.2.1 with the additional property that for n = 3 ⋅ 5k, Φc(n) gives an index w of a recursive function that is recursively defined from Φk. Thus intuitively one may view this as a version of on the range of Φc. Let i ∈ * . We claim that the set

is as required. We first leave it as an exercise to verify that

(1)Φc is strictly increasing in the sense of <o;

(2)for each j0 and m, if Φw(j0) ≤o m <o Φw(j0 + 1), then there is a j1 ∈ such that m = Φc(j0) +o j1.

Since n <o m implies Φc(n) <o Φc(m), <o is a well-ordering on O. Note that for any n ∈ , |n| ≤ |Φc(n) |. Hence Φc : {n ∈ | n <o* i} → O is an embedding and hence <o is a well-ordering of order type on O. By performing induction over the standard ordinal notations <o* below i, one easily sees that O is <o-downward closed.

By Theorem 1.3.4, there is a recursive function g1 such that Wg1(n) = {j | j <o n} for any n ∈ O. We claim that Wg1(n) is a recursive set when restricted to n ∈ O. It will then follow that the set {〈j, k〉| j <o k <o n} is recursive as well.

By an effective transfinite induction together with an application of the Recursion Theorem, we will define a partial recursive function q such that Wq(n) = ω Wg1(n) for n ∈ O. The case n = 2k and Φc(n) = 2Φc(k) is left to the reader as an exercise ( Exercise 2.6.1). Suppose n = 3 ⋅ 5k and Φc(3 ⋅ 5k) = 3 ⋅ 5w, where w is as defined earlier, and e is given such that Φe(Φw(j)) is defined for each j < ω. First note that an induction on j shows that Φw(j) ≥ j. If for each j, WΦe(Φw(j)) = ω Wg1(Φw(j)), then we claim

The proof of the claim from right to left is immediate. For the other direction, let j0 be such that Φw(j0) ≤o m <o Φw(j0 + 1). Then by (2) there is a j1 ∈ such that Φw(j0) +o j1 = m. This implies that j0 ≤ Φw(j0) ≤ m. Since m ≤o Φw(j0 + 1), we have proved the Claim.

Hence ⋃j<ω Wg1(Φw(j)) = ω ⋂j<ω WΦe(Φw(j)) is recursive. Now this calculation is uniform, and hence there is a recursive function g2 such that if WΦe(Φw(j)) = ω Wg1(Φw(j)) for every j, then Wg2(e,w) = ⋂j<ω WΦe(Φw(j)). Let g3 be a recursive function such that Wg3(e,w) = We {w}. Recall that if Φc(3 ⋅ 5k) = 3 ⋅ 5w ∈ O, then Φw(j + 1) = Φw(j) +o Φc(Φk(j + 1)). Let Wc1 = ω.

Define a recursive function h1 as follows:

By the Recursion Theorem, there is a d such that Φh1(d) = Φd. Let q = Φd. Then q is as required.

2.6.4 Exercises

Exercise 2.6.1. Complete the inductive argument for the case n = 2k and Φc(n) = 2Φc(k) in Theorem 2.6.5.

Exercise 2.6.2. Prove that for any i ∈ * , <o* is not a well-ordering on the set {j | * ∧ j <o* i}.

Exercise 2.6.3. Prove (1) and (2) in Theorem 2.6.5.

Exercise 2.6.4. Prove that there are 2ℵ0-many paths through .

Exercise 2.6.5. Prove that there is no partial recursive function p : ω2 → ω satisfying properties (1)–(3) in Exercise 1.4.1 upon replacing x with 1.

2.7 Codes for sets

In § 2.2.3, a method of coding -sets was introduced. However, the method does not provide an effective way of tracking the construction of -sets. Here we discuss the method of hyperarithmetic coding which serves as a useful tool for performing inductive analysis of -sets of reals.

2.7.1 Borel codes

Throughout this section, fix an effective enumeration {σi}i<ω of ω<ω.

For each x ∈ 2ω, define (x)n = {m | 2n ⋅ 3m ∈ x}. Define a sequence {Σβ}β<ω1 of sets of reals as follows:

β = 0: Let Σ0 = {x | x(0) = 0}.

β > 0: Let Σβ = {x ∈ 2ω Σ0 | (∀n)(∃γ < β)((x)n ∈ Σγ)}.

Let BC = ⋃β<ω1 Σβ be the set of Borel codes. For each x ∈ BC, define Ax to be:

β > 0 and x ∈ Σβ: Ax = ⋃n(ωω A(x)n ).

If σ is the empty string, let (y)σ = y. For each σ ∈ ω<ω, define

Given a real y, we define a tree Ty ≤T y over ω<ω as follows:

∈ Ty;

For any σ ∈ Ty, if (y)σ ∈ Σ0 then σ will have no extension in Ty.Otherwise, σ⌢n ∈ Ty for every n.

Lemma 2.7.1. y ∈ BC if and only if Ty is a wellfounded tree. Hence BC is . Moreover y ∈ Σβ if and only if |Ty|≤ β + 1.

Proof. If Ty is wellfounded, then one may show by induction on the rank of σ, for σ ∈ Ty, that (y)σ belongs to BC.

If y ∈ BC, then for any τ ≻ σ in Ty there exists a γ < β such that (y)τ ∈ Σγ and (y)σ ∈ Σβ. Thus Ty is a wellfounded tree.

Since Ty ≤T y uniformly and y ∈ BC if and only if Ty is wellfounded, we conclude that BC is . We leave the verification of the last statement of the lemma to the reader.

2.7.2 Hyperarithmetic codes

A hyperarithmetic code is a real in HYP ∩ BC. Let BC(HYP) denote the collection of hyperarithmetic codes. By Corollary 2.2.2 and Lemma 2.7.1, BC(HYP) is .

Since Tx ≤T x, if x ∈ BC(HYP) then by Lemma 2.7.1 and the discussion above, |Tx| < . Thus BC(HYP)⊆ .

Theorem 2.7.2 (Kleene [70]). The following statements are equivalent:

(i) A = Az for some z ∈ BC ∩ .

(ii)A = Az for some z ∈ BC(HYP).

(iii)A is .

Proof. Obviously, (i) ⇒ (ii). For (ii) ⇒ (iii), suppose A = Az for some z ∈ BC(HYP). We define a -relation Rz ⊆ ω<ω × ωω as follows. Rz will decode Az from Tz, and retraces the steps that constructed Tz from Az:

(1) (∀τ ∉ Tz)(∀y)¬Rz(τ, y);

(2) (∀τ ∈ Tz)(∀y)(τ has no extensions → (Rz(τ, y) ↔ (∃n)(y ≻ σn ∧ (z)τ(n) = 1)));

(3) (∀τ ∈ Tz)((∃n)(τ⌢n ∈ Tz) → (∀y)(Rz(τ, y)↔(∃m)¬Rz(τ⌢m, y))).

It is obvious that Rz is unique and well defined. Moreover, for any z ∈ BC, m ∈ ω, and y ∈ ωω, Rz(⌢m, y) if and only if R(z)m (, y). We make the following claim.

Claim. Rz(, y) if and only if y ∈ Az.

Proof of Claim. We prove this by induction. First assume that z ∈ Σ0. Then Tz consists only of the empty string and so by (2) Rz(, y) if and only if y ∈ Az. Suppose the Claim holds for all Σγ-codes where γ < β. Let z ∈ Σβ. If Tz(, y) then by (3) for some m, ¬Rz(0⌢m, y). Then by induction y ∉ A(z)m, hence y ∈ Az. Conversely, if y ∈ Az then there is an m such that y ∉ A(z)m. Now (z)m ∈ Σγ for some γ < β. By induction, ¬R(z)m (0, y). Thus Rz(, y) by (3), proving the Claim.

The Claim implies that Az is (z). By a similar argument, one shows that the complement of Az is also (z). Hence Az is (z). Since z ∈ HYP, Az is .

We now show (iii) ⇒ (i). Suppose that A is . Then both A and B = ωω A are . So there are two recursive trees S and T such that

and

Define R = S ⊗ T as follows:

(σ, τ, ν) ∈ R ⇔ (σ, τ) ∈ S ∧(σ, ν) ∈ T.

Define (σ, τ, ν) < (σ′, τ′, ν′) if σ ≻ σ′, τ ≻ τ′ and ν ≻ ν′. Since A ∩ B = , R is a wellfounded tree under <. We construct a hyperarithmetic code z so that B ⊆ Az and Az ∩ A = . Then Az = B.

We define a recursive function h : ω → ω such that for some c, Φh(c)(n, , , ) is a hyperarithmetic code for A.

For (σ, τ, ν) such that |σ| = |τ| = |ν|, there are three cases to consider:

(1) (σ, τ, ν) ∉ R and (σ, ν) ∈ T. Define Φh(e)(0, σ, τ, ν) = 0 and Φh(e)(n, σ, τ, ν) = 1 for all n > 0.

(2) (σ, τ, ν) ∉ R and (σ, ν) ∉ T. Define Φh(e)(n, σ, τ, ν) = 0 for all n.

(3) (σ, τ, ν) ∈ R. For (i, j, k, l), we define a recursive function g determined by the following four subcases:

3(i) i = k and (σ⌢i, τ⌢j, ν⌢l) ∈ R. Define g(e, i, j, k, l, n) = Φe(n, σ⌢i, τ⌢j, ν⌢l).

3(ii) i ≠ k. Define g(e, i, j, k, l, n) = m for all n > 0 and g(e, i, j, k, l,0) = 0, where m is a code such that σm = σ⌢k.

3(iii) i = k and (σ⌢i, τ⌢j) ∉ S. Define g(e, i, j, k, l, n) = 1 for all n > 0 and g(e, i, j, k, l,0) = 0.

3(iv) i = k and (σ⌢i, τ⌢j) ∈ S but (σ⌢i, ν⌢l) ∉ T. Define g(e, i, j, k, l, n) = 0 for all n.

Intuitively, g is a hyperarithmetic code for a set Ai,j,k,l disjoint from [S(σ⌢ i,ν⌢ j)], but covers [T(σ⌢k,ν⌢l)], where

and

The plan is to define Φh(e)(n, σ, τ, ν) to code the set C = ⋃k,l ⋂i,j Ai,j,k,l. Then C ⊇ [T(σ,ν)] and C ∩ [S(σ,τ)] = . Define a recursive function such that (0) = 1 and (2〈i,j〉 ⋅ 3n) = 1 if and only if g(e, i, j, k, l, n) = 1. Then will code the set ⋃i,j(ωω Ai,j,k,l).

Define a recursive function p2 so that p2(0) = 1 and p2(2〈k,l〉 ⋅ 3n) = 1 if and only if (n) = 1. Then p2 is a code for ⋃k,l(ωω ⋃i,j(ωω Ai,j,k,l)) = ⋃k,l ⋂i,j Ai,j,k,l.

Let Φh(e)(n, τ, ν0, ν1) = 1 if and only if p2(n) = 1. By the Recursion Theorem, there is a fixed point c such that Φh(c) = Φc.

Let z(n) = 1 ⇔ Φc(n, , , ) = 1. By an easy transfinite induction along < on R, one shows that for any (σ, τ, ν) ∈ R, z(σ,τ,ν) = {n | Φc(n, σ, τ, ν) = 1} is a recursive Borel code such that Az(σ,τ,ν) ⊇ [T(σ,ν)] and Az(σ,τ,ν) ∩ [S(σ,τ)] = . In particular, z* = z(,,) is a recursive Borel code such that A∩Az* = A∩ [S,] = and [T(,)] = B ⊆ Az*. Thus z* is a recursive Borel code for B.

Note that more was proved in the theorem above. Recall (see § 1.5.1) that there is a -set A ⊆ ω × ωω such that every -set B is of the form B = ¬An = {x | (n, x) ∉ A} for some n. These n’s are called -codes. Then Theorem 2.7.2 may be strengthened to: There is a recursive function f : ω × ω → ωω such that if n, m are -codes and (2ω An) ∩ (2ω Am) = , then f(n, m) ∈ BC ∩ , (2ω Af(n,m)) ∩ (2ω An) = , and (2ω Am) ⊆ (2ω Af(n,m)). This is an effective separation theorem which is a central result in effective descriptive set theory. We will discuss related facts in the sequel.

Remark 2.7.3. One may wonder how recursive codes are able to code the same sets as those coded hyperarithmetically. The answer is that there is a trade-off in the number of induction steps used. For example, a hyperarithmetic open set can be coded by a hyperarithmetic code in one step but any recursive code for it will be in some Σβ where β is a possibly large recursive ordinal.

We say that A ⊆ ω<ω is Σβ(HYP) if A = Ax for some hyperarithmetic x ∈ Σβ. Louveau [85], using Gandy forcing, proved the following result.

Theorem 2.7.4 (Louveau [85]). If A, B are and separated by Ax for some x ∈ Σβ, then A is separable from B by Ay for some y ∈ Σβ ∩ . Hence if A is and Σβ, then A is Σβ(HYP).

Theorem 2.7.2 yields another parameterization of -sets of reals.

Corollary 2.7.5. There is a -set A ⊆ ω × ωω such that

–(∀n)(An = {y | (n, y) ∈ A}∈ ),

–(∀C)(∃n)(C ∈ → C = An).

Proof. By Proposition 2.2.11, there is a partial function D : ω × ω → ω with a -graph parameterizing -reals. Define (n, y) ∈ A if and only if

Note that if (∀i)(∃j)(n, i, j) ∈ D, then the predicate (n, i, j) ∈ D is . So A is . Obviously each -set C is An for some n, and An codes a real in BC(HYP). For each n, either An = or An = Ax for some x ∈ BC(HYP). Hence A is as required.

2.7.3 Exercises

Exercise 2.7.1. Prove Lemma 2.4.8.

Exercise 2.7.2. Prove that y ∈ Σβ if and only if |Ty|≤ β + 1.