#### 5.3.2 Sacks generic reals

A set D ⊆ is dense if for any condition T, there is an S ∈ D such that S ≤ T. A real x is Sacks generic if for any dense set D ⊆ arithmetical in , there is a condition T ∈ such that x ∈ [T]. Note that by Lemma 5.3.2 and Lemma 5.3.4, for any sentence φ the set Dφ = {T | T ⊩ φ ∨ T ⊩¬φ} is dense and arithmetical in .

Lemma 5.3.5. Let x be Sacks generic and x ∈ [T0] ∩ [T1]. Then there is a T ⊆ T0 ∩ T1 such that x ∈ [T].

Proof. Let i ∈ {0, 1}. Since Ti is hyperarithmetic, there is a ranked formula φi such that

Hence for i < 2,

By the genericity of x and the definition of forcing for ranked formulas, there is a condition T such that x ∈ [T] and

This means that

and so T ≤ T0, T1.

Lemma 5.3.6. Suppose that x is Sacks generic. Then for any sentence φ,

Proof. If φ is ranked, then by the definition of forcing, (∃T)(x ∈ [T] ∧ T ⊩ φ) implies (, x) ⊨ φ. Conversely suppose that (, x) ⊨ φ. The genericity of x implies that there is a condition T such that x ∈ [T] and either T ⊩ φ or T ⊩ ¬φ. Then by the definition of forcing again, T ⊩ φ.

If φ is unranked, then one may prove the lemma by induction on the complexity of φ as was done in Theorem 5.2.4. The only difference with Cohen forcing is when φ is the conjunction of two sentences, but this is resolved by applying Lemma 5.3.5.

Lemma 5.3.7. If x is Sacks generic, then (, x) satisfies -comprehension and hence = .

Proof. Suppose that

where both φ(n, z) and ψ(n, x) are arithmetical.

Thus

Let T be a condition such that

By the definition of forcing,

Hence

implying that

By Lemma 5.3.3,

(∃S ≤ T)(∀n)(S ⊩∃z(φ(n, z)∨¬ψ(n, z))).

By Lemma 5.3.2, define a -relation R ⊆ ω × ω such that R(n, m) if and only if

m ∈ 1 ∧ S ⊩(∃z|m|)(φ(n, z|m|)∨¬ψ(n, z|m|)).

By Theorem 4.2.1, there is a total and hence -function f uniformizing R. By Corollary 1.5.2, there is an m0 ∈ O1 such that for any n, f(n)<o m0, so that

(∀n)(S ⊩(∃z|m0|)(φ(n, z|m0|)∨¬ψ(n, z|m0|))).

Hence for any condition T with T ⊩(∀n)(∃z)(φ(n, z)∨¬ψ(n, z)), there is an S ≤ T and β < such that

(∀n)(S ⊩(∃zβ)(φ(n, zβ)∨¬ψ(n, zβ))).

Let

Then is a dense set of conditions arithmetical in . By the genericity of x there is a T ∈ such that x ∈ [T]. By Lemma 5.3.6 and the assumption, T ⊮ ¬(∀n)(∃z)(φ(n, z)∨¬ψ(n, z)). Thus

T ⊩ (∀n)(∃zβ)(φ(n, zβ)∨¬ψ(n, zβ)))

for some β < . By the definition of forcing,

Thus as in the proof of Theorem 5.2.5, (, x) satisfies -comprehension.

Theorem 5.3.8 (Gandy and Sacks [36]). Suppose that x is Sacks generic and y ≤h x is nonhyperarithmetic. Then x ≤h y, i.e. x is a set of minimal hyperdegree.

Proof. Suppose that y ≤h x is nonhyperarithmetic. By Corollary 5.1.4 and Lemma 5.3.7, there is a ranked formula φ such that

(∀n)(y(n)= i ⇔ (, x) ⊨ φ(n, i)).

By Lemma 5.3.6, let T be a condition such that x ∈ [T] and

T ⊩ (∀n)(∃!i)(i < 2 ∧ φ(n, i)).

Claim. For any S ≤ T, there exist Qi ≤ S, i < 2, and an n such that Qi ⊩ φ( n̄, i).

Otherwise, fix S such that for all Qi and all n, it is not the case that Q0 ⊩ φ( n̄,0) and Q1 ⊩ φ( n̄,1). Then

n ∈ y ⇔ (∃Q ≤ S)Q ⊩ φ(n, 0)

and

n ∉ y ⇔ (∃Q ≤ S)Q ⊩ φ( n̄, 1),

implying by Lemma 5.3.2 that y is hyperarithmetic, which is a contradiction.

By the Claim and Lemma 5.3.3, one may define a condition S ≤ T such that

(∀σ, σʹ ∈ S)(∃m)(∃j < 2)(σ|σʹ → S ∩[σ]⊩ φ(m, j)∧ S ∩[σʹ]⊩ φ(m,1 − j)).

Furthermore, there is a hyperarithmetic function f mapping (σ, σʹ) to an appropriate (m, j,1 − j).(*)

Let

Then Dφ is a dense set arithmetic in O. By the assumption on x, there is an S ∈ Dφ such that x ∈ [S] and S satisfies (*). The function f defined on S effectively separates the reals in [S], and hence x is recursive in y⊕f. Since f is hyperarithmetic, we conclude that x ≤h y.

#### 5.3.3 A -set of minimal hyperdegrees

Let φ be ranked and

̂Dφ ={S | S ⊩ ¬(∀n)(∃!i < 2)φ(n, i) or (∀n)(∃!i < 2)S ⊩ φ(n, i) or

S satisfies (*) defined in the proof of Theorem 5.3.8}.

Define x to be weakly Sacks generic if for any ranked φ(n, i), there is a condition S ∈ ̂Dφ such that x ∈ [S]. Note that the set {(S, ⌜φ(n, i)⌝) | S ∈ ̂Dφ} is . By the proof of Theorem 5.3.8, ̂Dφ is dense for every ranked φ(n, i). Moreover, by going through the proof of Theorem 5.3.8, we have the following lemma.

Lemma 5.3.9. Let x be weakly Sacks generic and n ∈ . If then x <h y.

Let be -enumeration of all ranked sentences. By the Fusion Lemma (5.3.3) and Theorem 3.1.8, we may define by induction a Σ1(-enumeration of sets of conditions such that for any γ < β < ,

(i)(∀S ∈ γ)(∃S0, S1 ∈ β)(S0 ≤ S ∩[tS(0)]∧S1 ≤ S ∩[tS(1)]), where tS is the natural homeomorphic map from 2<ω to S;

(ii) (∀S ∈ β)(∃n)(∃{Si}i≤n ⊆ γ)([S] ⊆ ⋃i≤n[Si]), and

(iii)(∀S ∈ β)(∃n)(∀σ ∈ 2n)(S ∩ [tS(σ)] ∈ ̂Dφβ ).

Let 0 ={2<ω}. At stage β + 1, for any S ∈ β, by the density of ̂Dφβ, let S0, S1 ∈ ̂Dφβ be the <L-least pair of conditions such that S0 ≤ S ∩ [tS(0)] and S1 ≤ S ∩ [tS(1)]. Let S0, S1 ∈ β+1.

At limit stage λ, let {βi}i<ω be the <L-least increasing ω-sequence of ordinals with limit λ. For β < λ, let iβ be the least i such that β ≤ βi. By the inductive hypothesis, it is not difficult to see that there is a <L-least fusion sequence {Sσ}σ∈2<ω such that

Let T = ⋂n<ω ⋃σ∈2n Sσ. Put T ∩[tT(0)] and T ∩[tT(1)] into λ. We leave it to the reader to verify that satisfies (i)–(iii). The following is an immediate consequence of (iii).

Lemma 5.3.10. If for any β < there is a condition Sβ ∈ β such that x ∈ [Sβ], then x is weakly Sacks generic.

Now let

A = {(n, x) | (∃S)(x ∈ [S] ∧ S ∈ I|n|)∧ n ∈ 1}.

Since every S ∈ β is hyperarithmetic, by Corollary 2.2.12, A is . Moreover, for any n, An ={x |(n, x) ∈ A} is .

Lemma 5.3.11. An is an uncountable -set.

Proof. Obviously An is . By the definition of {, for any n ∈ 1, ⋂m<on Am ≠ . Hence for any . By the Kreisel Compactness Theorem (4.2.4), An is nonempty. Since no member of this set is hyperarithmetic, by Lemma 2.5.4 it is uncountable.

Theorem 5.3.12 (Simpson [138]). There is an uncountable -set of minimal hyperdegrees.

Proof. Let M = {x | x ∉ HYP ∧ x ∈ An ∧ = }. Then M is and by Lemma 5.3.11 and the Gandy Basis Theorem (2.5.3), M is nonempty. By Lemma 2.5.4, M is uncountable. By Lemma 5.3.9, every x ∈ M is of minimal hyperdegree.

By relativizing the proof of Theorem 5.3.12 (see [138]), one can show that there is a -set M ⊆ 2ω × 2ω such that for any x, there is a y with (x, y) ∈ M, and for any (x, y) ∈ M, y’s hyperdegree is a minimal cover of the hyperdegree of x.

#### 5.3.4 Exercises

Exercise 5.3.1 (Sacks [123]). Prove that x is Sacks generic if and only if for every sentence φ, there is an S ∈ ̂Dφ such that x ∈ [S].

Exercise 5.3.2 (Simpson [138]). Prove that there are two reals x, y of minimal hyperdegree such that x ⊕ y ≥h .

Exercise 5.3.3 Prove that no weakly Sacks generic real is hyperarithmetic.

Exercise 5.3.4 Let X be a -set of ranked sentences. Assume that if A ⊆ X is , then there is an x such that (, x) is a model of A. Show that there is an x such that (, x) is a model of X.

Exercise 5.3.5 (Simpson [138]). If there is an x such that 2ω = L[x] ∩ 2ω, then for any z, there is a y ≥h z whose hyperdegree is not a minimal cover of any hyperdegree.

### 5.4 Characterizing countable admissible ordinals

By relativizing the proof of Corollary 3.6.7, one can show that is a countable admissible ordinal for any x. The converse was proved by Sacks [122]: every countable admissible ordinal α > ω is for some x. His proof produces in addition an x such that no y <h x satisfies = α. We prove a weaker result, that α = for some x, using a notion of forcing introduced by Steel [158]. Let α be a countable admissible ordinal greater than ω for the rest of the section.

#### 5.4.1 Generalized ramified analytical hierarchy

Let (α, ẋ) be a language consisting of the following:

–number variables: i, j, k, m, n, …

–numerals: 0̄, 1̄, 2̄,…

–constants: ẋ, ẏ,…

–ranked set variables: xγ, yγ,… where γ < α

–unranked set variables: x, y,…

–operations and relation: +, ⋅ (times), ʹ (successor) and ∈.

Formulas are defined by induction. The set of number-theoretic terms is the set of terms closed under +, ⋅, ʹ over numerals and number variables. Atomic formulas are formulas of the form t = s and t ∈ x, where t and s are number-theoretic terms. The other formulas are generated in the usual way. A formula is ranked if all of its set variables are ranked. A ranked formula φ has rank at most γ if

–for any β, if xβ is a free variable occurring in φ, then β ≤ γ;

–for any β, if xβ is a bound variable occurring in φ, then β < γ.

By Σ-induction on Lα, we have

–the set of formulas is Σ1 in Lα;

–the set {(γ, φ) | φ is a ranked formulas of rank at most γ} is Δ1 in Lα.

Given x, one now defines the structure (α, x) = ⋃γ<α (γ, x), where x interprets the symbol ẋ as a countable union of collations of reals. During the construction, a ranked variable xγ is to be interpreted as a real in ⋃β≤γ (β, x). The satisfaction relation ⋃β≤γ (β, x) ⊨ φ, for a ranked formula φ with rank at most γ, is well defined. (α, x) is constructed by induction on ordinals less than α:

γ = 0: (γ, x) = {x}∪ ω.

γ > 0: Suppose (β, x) is defined for all β < γ. For a ranked formula φ(n) with rank at most γ and n as the only free variable, let

Let B be the collection of such zφ’s. Set

The satisfaction relation (α, x) ⊨ φ is defined inductively:

–if φ is ranked with rank at most γ, then (α, x) ⊨ φ if and only if ⋃β≤γ (β, x) ⊨ φ;

–if φ is (∃z)ψ(z), then (α, x) ⊨ φ if and only if there is a γ < α and a zγ such that zγ ∈ (α, x) and (α, x) ⊨ ψ(zγ);

–if φ is ¬ψ, then (α, x) ⊨ φ if and only if (α, x) ⊭ ψ.

We leave the proof of the following results to the reader.

Theorem 5.4.1 If ≥ α, then the set {(x, φ) | φ is ranked ∧ (α, x) ⊨ φ} is Δ1 in [x].

Theorem 5.4.2 Assume that ≥ α. Then = α if and only if (α, x) satisfies the -comprehension axiom.

#### 5.4.2 Steel forcing

Steel forcing is a notion of forcing whose conditions are finite tagged trees p with the following properties:

–p =( ̂t, h) where ̂t ⊆ ω<ω and h : ̂t → α ∪{∞} is a function such that h() = ∞ and (∀σ, τ ∈ Dom(h))(σ ≻ τ → h(σ) < h(τ)). We adopt the convention that ∞> β for all β < α;

–p =( ̂tp, hp) < q = (̂tq, hq) if and only if ̂tq is a subtree of ̂tp and hp ↾ ̂tq = hq.

Fix a recursive coding of ω<ω so that a string in ω<ω is identified with a natural number. Since the generic real is intended to be a tree, we also use Ṫ in place of ẋ.

Given a sentence φ ∈ (α, Ṫ), define p = (tp, hp) ⊩ φ by induction on the complexity of φ:

–p ⊩ σ̄ ∈ Ṫ if and only if σ = ∨(σ ↾(|σ|− 1) ∈ ̂tp ∧ hp(σ ↾(|σ|− 1)) > 0));

–p ⊩ t1 = t2 if and only if (α,0) ⊨ t1 = t2, where t1, t2 are number-theoretic terms;

–p ⊩ t ∈ Ṫ if and only if (α,0) ⊨ t = σ for some σ and p ⊩ σ̄ ∈ Ṫ, where t is a

number-theoretic term;

–p ⊩(∃n)φ(n) if and only if p ⊩ φ( n̄) for some n ∈ ω;

–p ⊩(∃zγ) φ(zγ) if and only if p ⊩ φ(z | ψ) for some ranked formula ψ( n̄) of rank at most γ;

–p ⊩(∃z)φ(z) if and only if p ⊩(∃zγ) φ(zγ) for some γ < α;

–p ⊩ φ ∧ ψ if and only if p ⊩ φ and p ⊩ ψ;

–p ⊩ ¬φ if and only if (∀q ≤ p)(¬q ⊩ φ).

The following basic facts follow immediately from the definition of forcing.

Proposition 5.4.3. For any sentence φ,

Analyzing the complexity of ⊩ defined above is not a straightforward matter. The difficulty is that Steel forcing, unlike Cohen forcing, is essentially a form of “class forcing”. Because of tagging, the forcing conditions range over the entire Lα. This makes the complexity of the statement “p ⊩ ¬φ” harder to determine. Our major effort is then to handle this problem.

Definition 5.4.4. Suppose that p, q are conditions and γ < α. Then Ret(γ, p, q), a retagging of q by p, holds if and only if

–̂tp = ̂tq;

–(∀σ)((hp(σ) < γ ∨ hp(σ) = 0 ∨ hq(σ) = 0) → hp(σ) = hq(σ)), and

–(∀σ)(hp(σ) ≥ γ → hq(σ)≥ γ).

We will use retagging to reduce a complex condition with a simpler condition while preserving the forcing relation.

Lemma 5.4.5. If γ0 < γ1 < α and Ret(ωγ1, p, q), then

(∀p1 ≤ p)(∃q1 ≤ q)Ret(ωγ0, p1, q1).

Proof. The reason for using ωγ0 and ωγ1 is to set aside some space to do the retagging. Assume that γ0 < γ1 < α and Ret(ωγ1, p, q). Let p1 ≤ p. Define q1 as follows:

Set ̂tq1 = ̂tp1 and

Case (1) σ ∈ ̂tq and hq(σ) < ωγ0. Let hq1(σ) = hq(σ);

Case (2) otherwise. Let hq1(σ) = ωγ0 + |̂tq1,σ| where ̂tq1,σ = {τ σ | τ ∈ ̂tq1}.

We leave it to the reader to verify that q1 is as required.

It is not difficult to see that there is a one-one Δ1(Lα)-function f : {φ | φ is ranked}→ α such that if the rank of φ is less than that of ψ, then f(φ) < f(ψ).

Lemma 5.4.6. If f(φ)= γ and Ret(ωγ, p, q), then p ⊩ φ ⇔ q ⊩ φ.

Proof. We prove the lemma by induction on ordinals. The only nontrivial case is when φ is of the form ¬ψ and f(ψ) < f(φ). Suppose Ret(ωγ, p, q) where f(φ)= γ.

If p ⊩ ¬φ but q ⊮ ¬φ, then (∀p1 ≤ p)(p1 ⊮ ψ) but (∃q1 ≤ q)(q ⊩ ψ). By Lemma 5.4.5, there is a p2 ≤ p such that Ret(ωγ1, p2, q1) where f(ψ)= γ1 < γ. By induction, p2 ⊩ φ, a contradiction. Hence p ⊩ φ ⇒ q ⊩ φ. A similar argument shows that q ⊩ φ ⇒ p ⊩ φ.

Theorem 5.4.7 The set {(p, ⌜φ⌝) | p ⊩ φ ∧ φ is ranked} is Δ1(Lα).

Proof. Suppose that f(φ) = γ. For any condition p, p ⊩ ¬φ if and only if (∀q ≤ p) (q ⊮ φ). Fix a condition q ≤ p and define qʹ so that ̂tq ʹ = ̂tq and

Case (1) σ ∈ ̂tp or hq(σ) < ωγ. Let ;

Case (2) otherwise. Let hqʹ (σ)= ωγ +| ̂tq,σ| where ̂tq,σ = {τ σ | τ ∈ ̂tq}.

Hence Ret(ωγ, q, qʹ) holds. By Lemma 5.4.6, q ⊩ φ ⇔ qʹ ⊩ φ. Thus

The theorem now follows from this by applying the Σ-Induction Theorem (3.1.8).

Let {Di}i<ω be an enumeration of all dense sets of conditions definable over 〈Lα, ∈〉. Then there is a sequence {pi}i<ω such that p0 ≥ p1 ≥ … and pi ∈ Di for each i. Let T = ⋃i<ω ̂tpi and h = ⋃i<ω hpi. The following lemma is immediate.

Lemma 5.4.8. For any γ < α,

–The set = {p |(∃σ)(σ ∈ ̂tp ∧ hp(σ)= γ)} is dense.

–The set = {p |(∀σ)(σ ∈ ̂tp ∧ hp(σ)> γ →(∃τ ≻ σ)(τ ∈ ̂tp ∧ hp(τ)= γ))} is dense.

Lemma 5.4.9. ≥ α.

Proof. By Lemma 5.4.8, for any γ < α, there is a σ ∈ T such that h(σ) = γ. By induction on γ, it is straightforward to verify that the subtree Tσ = {τ ∈ T | τ σ} is well ordered under the Kleene–Brouwer ordering with order type at least γ. Hence ≥ α.

The following forcing lemma is proved by a routine argument and is left to the reader.

Lemma 5.4.10. For any sentence φ, (α, T) ⊨ φ if and only if there is a p with ̂tp ⊆ T such that p ⊩ φ.

Lemma 5.4.11. (α, T) satisfies the -comprehension axiom.

Proof. Let φ and ψ be arithmetical such that

Then

As in the proof of Theorem 5.2.5, there is a p with ̂tp ⊆ T such that

Hence

By Lemma 5.4.6 and Lemma 5.4.5, we have an increasing sequence γ0 < γ1 < … in Lα such that

(ii) for any m, f((∃zγm)(φ(n, zγm)) ∨ ¬ψ(n, zγm)) < γm+1 and for any n and pn ≤ p in Lγm, there exists a qn ≤ pn with qn ∈ Lγm+1 such that qn ⊩(∃zγm+1) ∨ ¬ψ(n, zγm+1)), and

(iii) for each m, γm+1 = ωγm+1.

Let β = ⋃m<ω γm = ωβ. Then β < α. We claim that

p ⊩(∀n)(∃zβ)(φ(n, zβ)∨¬ψ(n, zβ)).

The forcing relation is equivalent to

(∀n)(∀q ≤ p)(∃r ≤ q)(q ⊩(∃zβ)(φ(n, zβ)∨¬ψ(n, zβ))).

Given n and q ≤ p, let qʹ be a condition such that ̂tqʹ = ̂tq and hqʹ(σ)= hq(σ) for hq(σ) < β and hqʹ(σ) = ∞ otherwise. By (i), qʹ ≤ p and qʹ ∈ Lγm for some m. By (ii), there is a condition rʹ ∈ Lβ such that rʹ ≤ qʹ and

By (iii), Ret(ωβ, q, qʹ) holds and

By Lemma 5.4.5 and Lemma 5.4.6, there is a condition r ≤ q such that

Hence

By Lemma 5.4.10,

Let y be defined such that n ∈ y if and only if (α, T) ⊨ (∃zβ)φ(n, zβ). Then y ∈ (α, T) and thus (, T) satisfies -comprehension.

In summary, we have the following:

Theorem 5.4.12 (Sacks [122]). For any countable admissible ordinal α > ω, there is a real x such that = α.

Remark 5.4.13. In the literature, there are several proofs of Theorem 5.4.12. Sacks’s original proof was by the method of perfect set forcing and provided a stronger conclusion. The second proof, due to Friedman and Jensen [31], was by an application of the Barwise Compactness Theorem [3]. The third proof, which remains unpublished, was due to Jensen [54] and uses a class of Levy collapse operations which may be viewed as a variant of Steel forcing.

#### 5.4.3 Exercises

Exercise 5.4.1 Prove that for any x with x ∉ , there is a y such that y ≱h x, y ≰h x and = .

Exercise 5.4.2 Prove that x ∈ if and only if for all y, ≥ implies y ≥h x.

Exercise 5.4.3. Let αn be the n-th admissible ordinal. Then ⋃n<ω αn is not admissible.

Exercise 5.4.4 (Chong [11]). Suppose that γ > ω is an ordinal so that Jγ+1 \ Jγ ∩ 2ω ≠ . Then for any admissible ordinal ω < α < γ+, where γ+ is the least admissible ordinal greater than γ, there is an x ∈ Jγ+ \ Jγ such that = α.

Exercise 5.4.5 (Jensen [54]). Suppose that α is a countable limit of admissible ordinals. Then there is a set A ⊆ α so that for any admissible β < α,

〈Lβ[A], ∈, A ∩ Lβ[A]〉

is admissible and

〈Lα[A], ∈, A ∩ Lβ[A]〉 ⊨ “β is countable”.

Exercise 5.4.6 (Jensen [54]). Suppose that ω < α0 < … < αn is a finite sequence of countable admissible ordinals. Prove that there is an x such that for any i ≤ n, αi is the i + 1-th countable admissible ordinal in L[x].