11.2.2 The proof of Harrington’s Theorem

We follow the presentation of Hjorth [50]. By Theorem 2.6.5, for any recursive ordinal β ≥ ω, there is an n ∈ such that |n|= β and the set {m | m <o n} is recursive. We choose such an ordinal β and the corresponding n.

For each m = 3 ⋅ 5k <o n, let {ij, m}j<ω be a sequence of numbers such that

i0, m = Φk(m)

and

ij+1, m = Φk(m + j + 1).

By the proof of Theorem 2.6.5, we may assume that m ≤ ij, m < ij+1, m for all j. Clearly the set {(ij, m, j, m) | (∃k)(m = 3 ⋅ 5k ∧ m <o n ∧ j ∈ ω)} is recursive.

Lemma 11.2.7.

(i)For any m = 3 ⋅ 5k <o n and

(ii)for any l <o n, the set {m | (∃k)(i0, m <o l <o m = 3 ⋅ 5k <o n)} is finite;

(iii)the set {(m, l) | (∃k)(i0, m <o l <o m = 3 ⋅ 5k <o n)} is recursive;

(iv)if m = 3 ⋅ 5k <o n and |m|= limi→∞ βi where {βi} is an increasing sequence of limit ordinals, then for any i there is an m'' = 3 ⋅ 5k'' <o m with |m''|> βi such that for any m' = 3 ⋅ 5k' <o m with |m'|>|m''|, we have |i0, m' |>|m''|.

Proof. (i) is immediate. (ii) is true since for any number l, there are only finitely many m ≤ l such that l <o m <o n. (iii) is true since <o is a recursive relation over the recursive set {i | i <o n}.

We prove (iv). If m = 3 ⋅ 5k <o n and |m|= limi→∞ βi where {βi} is an increasing sequence of limit ordinals, then for any i there is an m'' = 3 ⋅ 5k'' <o m with |m''|> βi such that whenever m' = 3 ⋅ 5k' <o m with |m'|>|m''|, we have m' > m''. Hence |i0, m' |>|m''|.

The main difficulty with extending Theorem 11.2.2 to arbitrary levels of recursive ordinals concerns coding at limit ordinal stage. Here, as in the proof of Theorem 11.2.2, at each successor stage one attempts to carry out a stepdown construction that codes information computed at a limit level. There is no difficulty dealing with only one limit ordinal. With more than one limit ordinal, one of them has to be chosen for coding. Lemma 11.2.7 allows the use of nice sequences in the approximation of limit ordinals to facilitate the choice.

For convenience, in the rest of this section let |n|= β∞ and identify each natural number ≤o n with the ordinal β < β∞ of which it is an ordinal notation. In particular, we use λ for natural numbers which are ordinal notations of limit ordinals. Also βj, λ = |ij, m| for λ = |m|. We write (β) and x(β) for Hi and where |i| = β. Finally, β+ is identified with 2k where |k|= β.

For β ≤o n, let

Λ(β) = {λ | β <o λ ∧ (∃j ∈ ω)(βj, λ ≤o β)}.

Note that by Lemma 11.2.7, Λ(β) is finite for any β ≤o n. Hence the following is well defined:

j(β) = max ({0}∪{j | (∃λ ∈ Λ(β))(βj, λ ≤o β)}).

For each a ⊆ ω, define the following function “specialized” to ω a:

Then

pa(T) = {pa(σ) | σ ∈ T},

and

For β <o γ ≤o β∞, let

(β, γ]= {δ | β <o δ ≤o γ}.

Clearly if βo < γo < δ, then p(β, δ] = p(β,γ] ∘ p(γ, δ]. As in the previous section, there is a recursive tree T ⊆ β∞ × ω<ω such that T(β) = {σ | (β, σ) ∈ T} contains exactly one path (β). Let

Tβ∞ = {σ | (∀β)(∃i)(∃τ)(σ(β, i) defined →((β, τ) ∈ T ∧ (∀j)(σ(〈β, j〉) = τ(j))))}.

Hence Tβ∞ codes T as a single tree. For β ≤o β∞, let yβ be a real such that

(∀i, j, k)(yβ(〈i, j〉) = k ↔ i ≤o β ∧ (|i|)(j) = k).

Note that there are constants d0, d1 such that yβ ≡T (β) via (d0, d1). We build a system consisting of a uniform sequence of r. E. trees functions {ψγ, β}β ≤ oγ ≤ oβ∞ and onstants {ci}i ≤ 3 such that

Suppose that we have the sequence of trees as above. By (4) and (5), for every x ∈ , one concludes by an induction on β ≤o β∞ that

It would appear that the requirement set by (2) on Tβ ∩ ω ≤j(β) × ω ≤j(β) is a problem since too many nodes from Tλ, for λ ∈ Λ(β), are put into it. However, the following lemma says that Tβ ∩ ω ≤j(β) × ω ≤j(β) is an orderly structure due to Lemma 11.2.7 (iv).

Lemma 11.2.8. Suppose that λ ∈ Λ(β) with βj, λ ≤o β for some j. Then (σ, τ) ∈ Tβ ∩ ω ≤j × ω ≤j if and only if there exists a (σ, ) ∈ Tλ such that p(β, λ] () = τ.

Proof. Suppose not. Then there is a λ ∈ Λ(β), a j with βj, λ ≤ β such that for some (σ, τ) ∈ Tβ ∩ ω ≤j × ω ≤j, there is no (σ, ) ∈ Tλ with p(β, λ] () = τ.

By (2), there is a λ1 ∈ Λ(β) with βj1, λ1 ≤o β such that j ≤j1 and for some (σ, 1) ∈ Tλ1 ∩ ω ≤j × ω ≤j, one has p(β, λ1] (1) = τ.

We claim that λ1 <o λ. Otherwise, λ <o λ1 and so βj1, λ1 ≤o β <o λ <o λ1. In other words, λ1 ∈ Λ(λ). By applying (2) to λ, (σ, p(λ, λ1] (1)) ∈ Tλ. Then

a contradiction.

Hence λ ∈ Λ(λ1). Note that there is no (σ, ) ∈ Tλ ∩ ω ≤j × ω ≤j such that p(α, λ] () = 1. Repeating the above process upon replacing β and (σ, τ) with λ1 and (σ, 1) respectively, we see that there is a λ2 ∈ Λ(λ1) and βj2, λ2 ≤o λ1 <o λ2 such that λ2 <o λ, It follows that there is an increasing sequence of limit ordinals λ1 <o λ2 <o … <o λ such that βj, λ <o λi for every i∈ω, contradicting Lemma 11.2.7 (iv).

For γ ≥o β, define a map ψγ, β : Tγ0 → by induction on β ≤o β∞. If β = 0, then ψ0,0 is the identity map. In the following, ψβ, β is always the identity map.

If γ+ >o β, then

If λ is a limit ordinal, then for j such that β ≤o βj, λ <o λ and σ ∈ T0λ ∩ ω ≤j, we have σ ∈ Tβj0 by (2) and Lemma 11.2.8. Define ψλ, β(σ) = ψβj, λ, β(σ).

Note that in the case β = βj, λ, we have ψλ, β(σ) = ψβj, λ, β(σ) = σ. We show that ψλ, β is well-defined.

Lemma 11.2.9. Let δ ≤o β∞,

(i)If β ≤o δ, then ψδ, β is well defined.

(ii)For β ≤o β1 ≤o δ, ψδ, β = ψβ1, β ∘ ψδ, β1.

(iii)For Moreover, |ψδ, β(σ) | ≥ |σ|.

(iv)There is a recursive function g such that for each

Proof. We prove (i) and (ii) simultaneously by induction on δ. By the definition of ψδ, β, the only nontrivial case is when δ = λ for some limit ordinal λ.

For (i), fix a β <o λ and β ≤o βj0, λ <o βj1, λ <o λ for j0 < j1. Suppose that σ ∈ T0λ∩ω ≤j0 and j0 is used to define ψλ, β(σ). By (2) and Lemma 11.2.8, Note that for any γ with βj0, λ <o γ ≤o λ, we have λ ∈ Λ(γ) and j(γ) ≥ j0. By(6) and an induction on γ in (βj0, λ, λ], ψγ, βj0, λ (σ) = σ. By the same argument, for γ in (βj1, λ, λ], we have ψγ, βj1, λ (σ) = σ. Hence by induction on β, ψλ, β(σ) = ψβj0, λ, β(σ) = ψβj0, λ, β(ψλ, βj0, λ (σ)) = ψβj0, λ, β(ψβj1, λ, βj0, λ (ψλ, βj1, λ (σ))) = ψβj1, λ, β(ψλ, βj1, λ (σ)) = ψβj1, λ, β(σ). Thus ψδ, β is well defined.

For (ii), given σ let j be such that |σ|< j and β ≤o β1 <o βj, λ ≤o λ. Then ψλ, βj, λ (σ) = σ. By the definition of ψλ, βj, λ, ψλ, β(σ) = ψβj, λ, β(σ). Then by induction, ψβj, β(σ) = ψβ1, β(ψβj, λ, β1(σ)).

We obtain (iii) by using (5i) and (5ii) and an induction on β. Finally, (iv) follows from (3).

If x ∈ [], let ψδ, β(x) = ∪m ∈ ωψδ, β(x ↾ m). By Lemma 11.2.9 (iii), ψδ, β is well defined.

Lemma 11.2.10. For any β ≤o γ ≤ β∞,ψγ, β : [T0γ]→[] is a homeomorphism.

Proof. This is proved by induction on γ. First, (5) implies that the only nontrivial case is when γ = λ, a limit ordinal.

For x ∈ [] and m ∈ ω, let jm > m be chosen such that βjm, λ > β. Byinduction, there is a unique zm ∈ [Tβj, λ ] such that ψβjm, λ, β(zm) = x. By Lemma 11.2.9 (iii), ψβjm, λ, β(zm ↾ m)⪰ x ↾ m. Let σm = zm ↾ m. By (ii) and (iii) of Lemma 11.2.9, there is a z = ∪mσm. Since jm > m, we have σm ∈ Tλ for every m. Hence z ∈ []. More over, Thus In other words, ψ is onto.

Now suppose that x0, x1 ∈ [], x0 ↾ n0 = x1 ↾ n0 = σ, x0 ≻ σ⌢k0, x1 ≻ σ⌢k1 for some k0 ≠ k1. Let j >|σ|+ 1besuchthat βj, λ > β. Then ψλ, βj, λ (x0 ↾|σ|+ 1) = x0 ↾ |σ|+ 1 ≠ x1 ↾|σ|+ 1 = ψλ, βj, λ (x1 ↾|σ|+ 1). By induction, ψβj, λ, β(y0) ≠ ψβj, λ, β(y1) for any y0 ≻ x0 ↾|σ|+ 1 and y1 ≻ x1 ↾|σ|+ 1. By Lemma 11.2.9 (ii), ψλ, β(x0) ≠ ψλ, α(x1).

Hence for γ = λ, ψγ, β is a bijection between [T0γ] and []. Clearly both ψγ, β and ψ−1γ, β are continuous. Hence ψγ, β is a homeomorphism.

By (3), is a recursive tree. By the Recursion Theorem, one may assume that there is already a system satisfying (1)–(6). We define Tβ from Tβ+ . Let

be a recursive tree. Recursively compute j(β).

For σ ∈ ωj(β), let ̂T0β+, σ be a (β)-recursive tree obtained from Lemma 11.2.5 upon replacing T with {τ | σ⌢τ ∈ T0β+} and x with (β). Relativizing Lemma 11.2.6 to (β) (replacing T0 with ̂T0β+, σ), we have a (β)-recursive homeomorphism ψσ : ̂T0β+, σ → T0β, σ where T0β, σ is T1 in Lemma 11.2.6. Define to be a (β)-recursive tree such that τ ∈ if and only if either

– for some λ ∈ Λ(β), or

–

Define ψβ+, β ≤T (β+) : Tβ+0 → such that

–if and

–otherwise, let τ =(τ ↾ j(β))⌢τ'. Define ψβ +, α (τ) = τ ↾ j(β)⌢ψτ↾j(β)(τ' ⊕ (h0(β) ↾|τ'|)).

Hence for any x ∈ ,

Note that = Φdyβ (see (3)) for some d which is independent of β. Define Tβ such that (σ, τ) ∈ Tβ if and only if either

–there exists a (σ, ) ∈ Tλ ∩ ω ≤j(β) × ω ≤j(β) for some λ ∈ Λ(β) such that τ = p(β, λ]( ), or

–there is a τ' τ so that τ' ∈ Tβ1, Φdτ' (σ)[|τ'|] = 1 and (σ ↾ j(β), ' ↾ j(β)) ∈ Tλ for< some λ ∈ Λ(β) and ' such that τ' = p(β, λ] (').

Then the tree Tβ is as required. Since the construction is uniform, the rest of (1)–(6) follow. This completes the proof of Theorem 11.2.2.

By -boundedness, we have the following generalization:

Corollary 11.2.11 (Harrington). There is an uncountable-set A such that for any recursive ordinal β and

Proof. Suppose not. Let B ⊆ ω × ω<ω be arithmetical such that {[Be]}e<ω, where Be = {σ ∈ ω<ω | (e, σ) ∈ B)}, isarecursivelistofall -subsets of ωω. Let O ⊆ O be as defined in Theorem 2.6.5.

Recall that the system satisfying (1)–(6) was obtained by fixing an ordinal notation n with |n|≥ ω. Let e0 be such that |3 ⋅ 5e0|= ω. Define a -relation R ⊆ ω × ω such that

Then by Theorem 4.2.1 and the assumption, there is a total , hence , uniformizing function f : ω → O for R. Let I = {e ||[Be]| > ℵ0}. By Theorem 1.1.10, I is . By Corollary 1.5.2, there is an n ∈ O such that for all m ∈ {f(e) | e ∈ I}, we have m <o n and that contradicts the proof above.

Hence there is an e ∈ I such that Be = and a system satisfying (1)–(6) exists for each n ∈ O where |n|≥ ω. By the proof above,

11.2.3 Exercises

Exercise 11.2.1. Prove that in Theorem 11.2.1, the set A may be chosen to be a subset of 2ω.

Exercise 11.2.2. (Harrington). There is a -path through O such that the only hyper-arithmetic reals recursive in it are recursive.

Exercise 11.2.3. (Harrington). Prove that for any recursive ordinal β < ω1CK, there are two -singletons x and y in 2ω such that

Exercise 11.2.4. (Harrington). Prove that there is a transitive model N of KP such that N ⊩ ”Not every -real is hyperarithmetic”.

11.3 Perfect sets in L

11.3.1 A question of Prikry

In [98], Prikry posed the following question.

Question 11.3.1. Suppose that there is a nonconstructible real. Does every perfect set contain a nonconstructible real?

Friedman [29] also raised a question related to Question 11.3.1:

Question 11.3.2. Suppose that there is a nonconstructible real. Is

By Theorem 1.1.10, a positive answer to Question 11.3.1 would imply a negative solution to Question 11.3.2. The latter was given a negative solution by Velickovic and Woodin:

Theorem 11.3.3. (Velickovic and Woodin [166]). If the set of constructible reals is , then either (ω1)L is countable or every real is constructible.

On the other hand, Question 11.3.1 was answered positively by Groszek and Slaman [41] and the solution is discussed in the next section.

Theorem 11.3.4. If there is a perfect set A ⊆(2ω)L, then every real is constructible.

11.3.2 The proof of Theorem 11.3.4

Given a tree T ⊆ 2<ω, aset A ⊆ 2ω is dense in T if for any σ ∈ T, [σ] ∩ [T] ∩ A ≠ . Areal x ∈ [T] is eventually constant in T if there is an n such that x is the leftmost or rightmost infinite path in [x ↾ n] ∩ [T].

Lemma 11.3.5. Let T be a perfect tree. Suppose that {gi}i<ω ∈ L contains a dense subset of T no member of which is eventually constant in T. Then for any z, there exist x, y ∈ [T] such that x ⊕ y ⊕ (⊕i<ωgi) ≥T Z.

Assume Lemma 11.3.5. Let T be a perfect tree such that [T]⊆ L. Then (ω1)L = ω1. Select a countable sequence {xi}i<ω from [T] which is dense and such that no xi is eventually constant. Since (ω1)L = ω1, there is an x∗ ∈ L such that xi <L x∗ for each i < ω. Let {gi}i<ω be an enumeration of the set {x | x <L x∗}. Notethat {gi}i<ω belongs to L. By Lemma 11.3.5, for each z there exist x, y ∈ [T], and hence in L, such that x ⊕ y ⊕ (⊕i∈ωgi) ≥T Z. Thus z ∈ L.

The idea of the proof is as follows. Suppose z is a given real, T is perfect and {gi}i<ω ∈ L is a sequence with a subset dense in T no element of which is eventually constant in T. We define x ∈ [T] and an index function hx : ω → ω such that for each i, ghx(i) is a path through T that is not eventually constant in T. Theset x agrees with ghx(i) on longer and longer initial segments as i increases„ and z is coded into x and {ghx(i)}i<ω so that z(i) is the value of x at the first place where x differs from ghx(i). Itis easy to see that z ≤T x ⊕ hx ⊕ (⊕i<ωgi). There is no problem to recursively define such an x and hx.

The challenge is to decode hx. This is handled by defining another real y ∈ [T] such that hx ≤T x⊕y⊕ (⊕i<ωgi). To achieve this, we define an additional index function hy : ω → ω with the same properties (except that z is not coded here), in such a way that hx and hy can be computed from x, y and ⊕i<ωgi.

Proof of Lemma 11.3.5. We now describe the construction of the sets x, y and functions hx, hy.

Stage 0. Let σ0 and τ0 be the first splitting node of T extending its root, i. e. a splitting node of T such that every node in T extends either σ0 or τ0. Let hx(0) be the least i such that gi ∈ [σ0⌢z(0)] ∩ [T], andlet hy(0) be the least j such that gj ∈ [τ0] ∩ T.

Stage n + 1. Assume by induction hypothesis that σn and τn are splitting nodes in T, andthat σn⌢z(n)≺ ghx(n) and τn ≺ ghy(n).

Substage (a). Define j0 to be the least index j so that gj ∈ [σn⌢(1 − z(n))] ∩ [T] is not eventually constant. Let m0 be the least m >|τn| so that gi ↾ m ≠ gj0 ↾ m for every i < j0. Let m1 be the least m > m0 such that ghy(n) ↾ m is a splitting node in T. Let τ' = ghy(n) ↾ m1⌢(1 − ghy(n)(m1)). Then gi ↾ m1 ≠ gj0 ↾ m1 for i < j0 and m1 is the least m such that τ'(m) ≠ ghy(n)(m).

Substage (b). Let j1 be the least j such that gj ∈ [τ'] ∩ [T]. Let m2 be the least m such that for any i < j1, gi ↾ m ≠ gj1 ↾ m. Since gj0 is noteventuallyconstant, we may choose m3 to be the least m > m2 such that gj0 ↾ m is a splitting node in T and gj0 ≻ gj0 ↾ m3⌢z(n + 1). Then gi ↾ m3 ≠ gj1 ↾ m3 for i < j1. Let σn+1 = gj0 ↾ m3, τn+1 = gj1 ↾ m3, hx(n + 1) = j0 and hy(n + 1) = j1.

Let This completes the construction.

The construction ensures that for every n, hx(n + 1) is the least i such that gi ↾ m1 = x ↾ m1 where m1 is the least m satisfying y(m) ≠ ghy(n)(m). Also, hy(n + 1) is the least i such that gi ↾ m3 = y ↾ m3 where m3 is the least m such that x(m) ≠ ghx(n+1)(m). Hence hx ⊕ hy ≤T x ⊕ y ⊕ (⊕i<ωgi), giving z ≤T x ⊕ y ⊕ (⊕i∈ωgi).

11.3.3 Exercises

Exercise 11.3.1. Prove that Lemma 11.3.5 remains true without the condition “no element is eventually constant in T”.

*Exercise 11.3.2 (Harrington). Prove that for any -set A ⊆ 2ω which is not thin, A contains a hyperarithmetically pointed perfect tree T, i. e. T ≤ h x for every x ∈ [T].