5.4 Characterizing countable admissible ordinals – Recursion Theory

5.3.2 Sacks generic reals

A set D is dense if for any condition T, there is an SD such that ST. 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 TT0T1 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,

Since x ∈ [T0] ∩ [T1],

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 TT0, 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,

(∃ST)(∀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

m1S ⊩(∃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 m0O1 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 ST 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 yh x is nonhyperarithmetic. Then xh y, i.e. x is a set of minimal hyperdegree.

Proof. Suppose that yh 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 ST, there exist QiS, i < 2, and an n such that Qiφ( , i).

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

ny ⇔ (∃QS)Qφ(n, 0)

and

ny ⇔ (∃QS)Qφ( , 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 ST 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 SDφ 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 yf. Since f is hyperarithmetic, we conclude that xh 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 ŜDφ such that x ∈ [S]. Note that the set {(S, ⌜φ(n, i)⌝) | Ŝ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β)(S0S ∩[tS(0)]∧S1S ∩[tS(1)]), where tS is the natural homeomorphic map from 2<ω to S;

(ii) (∀Sβ)(∃n)(∃{Si}inγ)([S] ⊆ ⋃in[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 S0S ∩ [tS(0)] and S1S ∩ [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] ∧ SI|n|)∧ n1}.

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 n1, ⋂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 xM 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 ŜDφ such that x ∈ [S].

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

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 AX 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 yh 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 tx, 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 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) ∈ ̂tphp(σ ↾(|σ|− 1)) > 0));

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

pt 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φ( ) for some nω;

p ⊩(∃zγ) φ(zγ) if and only if pφ(z | ψ) for some ranked formula ψ( ) 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 (∀qp)(¬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

(∀p1p)(∃q1q)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 p1p. 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 (∀p1p)(p1 ⊮ ψ) but (∃q1q)(qψ). By Lemma 5.4.5, there is a p2p 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 (∀qp) (q ⊮ φ). Fix a condition qp 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 p0p1 ≥ … and piDi 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 |(∃σ)(σ ∈ ̂tphp(σ)= γ)} is dense.

The set = {p |(∀σ)(σ ∈ ̂tphp(σ)> γ →(∃τσ)(τ ∈ ̂tphp(τ)= γ))} 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 ̂tpT 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 ̂tpT such that

Hence

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

(i) Range(hp) ⊆ γ0 ∪{∞};

(ii) for any m, f((∃zγm)(φ(n, zγm)) ∨ ¬ψ(n, zγm)) < γm+1 and for any n and pnp in Lγm, there exists a qnpn with qnLγ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)(∀qp)(∃rq)(q ⊩(∃zβ)(φ(n, zβ)∨¬ψ(n, zβ))).

Given n and qp, 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 rq such that

Hence

By Lemma 5.4.10,

Let y be defined such that ny 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 yh x, yh x and = .

Exercise 5.4.2 Prove that x if and only if for all y, implies yh x.

Exercise 5.4.3. Let αn be the n-th admissible ordinal. Thenn<ω α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 xJγ+ \ 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], ∈, ALβ[A]〉

is admissible and

Lα[A], ∈, ALβ[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 in, αi is the i + 1-th countable admissible ordinal in L[x].