5 Recursion-theoretic forcing

Although historically Cohen introduced forcing for set-theoretic considerations, the method was adapted to study problems in recursion theory soon after by Feferman [25] (indeed, one detects a hint of Cohen forcing in the theorems of Post and Kleene on the structure of the Turing degrees proved in the 1950s). Here we study three classic examples of forcing (due to Cohen, Sacks and Steel respectively) and their applications in recursion theory. It turns out that the ramified analytical hierarchy provides an ideal platform for this purpose.

5.1 Ramified analytical hierarchy

5.1.1 The structure

The ramified analytical hierarchy was introduced by Kleene [72] and forcing constructions over it goes back to Cohen [18] and continued in Feferman [25]. It may be viewed as an analog of the constructible hierarchy defined in the language of second order arithmetic, for the study of hyperarithmetic theory.

The language for the hierarchy, denoted (, ẋ), consists of the following:

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

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

–set constants: ẋ, ẏ,…

–ranked set variables: xβ, yβ,… for β <

–unranked set variables: x, y,…

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

Formulas in this language are defined by induction in the usual way. As one might expect, the presence of ranked set variables implies that there is no recursive coding of (, ẋ). Instead, coding is carried out in the countable admissible set . First choose a -path 1 through which exists according to Theorem 2.6.4. Code the ranked set variable xβ by the number (2, n) where n ∈ 1 and |n|= β. Other symbols are coded recursively. With this, formulas are coded in . 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 bounded variable occurring in φ, then γ < β.

Note that

–the set of Gödel number of formulas is ;

–the set of Gödel numbers of ranked formulas of rank at most β is r.e. uniformly in the unique notation for β in 1.

By Theorem 1.3.4, there is a recursive function h such that for n ∈ 1, Wh(n) is the set of Gödel numbers of ranked formulas of rank at most |n|.

We now define the structure , where x is a real that interprets is a collection of reals defined in an analogous way as Gödel’s L. The construction is completed in -many stages. Any ranked set variable xβ is to be interpreted by a real in . With this as our convention, the satisfaction relation ⊨ φ is well defined for a ranked formula φ of rank at most β. We define by induction on the recursive ordinals, as follows:

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

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

Thus the reals constructed at stage β are precisely those arithmetically defined by the reals constructed at earlier stages.

For a formula φ, the satisfaction relation (, x) ⊨ φ is defined by induction:

–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) ⊭ ψ.

A sentence φ in (, ẋ) is if it is ranked, or of the form (∃x1)…(∃xn)ψ for some formula ψ with no unranked set variables bounded by a quantifier. It is not difficult to see that the set of Gödel numbers of -sentences is . Let ⌜φ⌝ be the code of the formula φ.

Theorem 5.1.1 The set {(x, ⌜φ⌝) | φ is ∧ (, x) ⊨ φ} is .

Proof. By Σ-induction (Theorem 3.1.8) and the definition of (, x), there is a Σ1-formula ψ(u) such that 〈 [x], ∈〉 ⊨ ψ(⌜φ⌝) if and only if φ is ranked ∧ (, x) ⊨ φ. Hence by the Spector–Gandy Theorem (3.7.2), the set {(x, ⌜φ⌝) | φ is ranked ∧ (, x) ⊨ φ} is . Now if φ is of the form (∃z)φ0(z), then (, x) ⊨ (∃z)φ0(z) if and only if there is an n ∈ 1 such that (, x) ⊨ (∃z|n|)φ0(z|n|). It follows that the set {(x, ⌜φ⌝) | φ is ∧ (, x) ⊨ φ} is .

Corollary 5.1.2 For β < , the set {(x, ⌜φ⌝) | rank(φ) is at most β ∧ (, x) ⊨ φ} is .

Proof. Note that the set {⌜φ⌝ | rank(φ) is at most β} is r.e. and hence . By Theorem 5.1.1, both the sets {(x, ⌜φ⌝) | rank(φ) is at most β ∧ (, x) ⊨ φ} and {(x, ⌜φ⌝) | rank(φ) is at most β ∧ (, x) ⊨ ¬φ} are and hence .

5.1.2 Characterizing

Proposition 5.1.3 For any real z, z ∈ (, x) if and only if there is an m ∈ that .

Proof. Suppose that z ∈ (, x). Then there is a ranked formula φ(n) such that

n ∈ z ⇔ (, x) ⊨ φ(n).

By Corollary 5.1.2, the set C ={(x, n) | (, x) ⊨ φ(n)} is . By the -Uniformization Theorem (4.2.1), there is a total and hence -function f : 2ω → ω such that f(x) = m if and only if m ∈ x . By relativized -boundedness (Corollary 1.5.2), there is an ordinal β < such that |f(x)|x ≤ β for all x. Thus if z ∈ (, x), then there is an m ∈ such that .

For the other direction, suppose there is an m ∈ such that . It suffices to prove that ∈ (|m| + 2, x). We show this by induction on |m|.

Suppose that m = 2n. Then ̂Hn ∈ (|m| + 1, x). So ∈ (|m| + 2, x).

Suppose that m = 3 ⋅ 5e and ∈ (, x) for all n <o m. Then i ∈ if and only if

Thus ∈ (|m| + 2, x).

Theorem 2.3.3 and Proposition 5.1.3 immediately give the following

Corollary 5.1.4 Suppose that = . Then for any z, z ∈ (, x) if and only if z ≤h x. In particular, z is hyperarithmetic if and only if z ∈ (, ).

5.1.3 -comprehension

The -comprehension scheme states:

(∀n)((∃z)φ(n, z)↔(∀z)ψ(n, z)) → (∃y)(∀n)(n ∈ y ↔(∃z)φ(n, z)),

where both φ(n, z) and ψ(n, z) are arithmetical. In forcing constructions, satisfying -comprehension in (, x) is used to guarantee = , as shown by the following theorem.

Theorem 5.1.5 = if and only if (, x) satisfies the -comprehension axiom.

Proof. If = , then by Corollary 5.1.4, for any real z, z ∈ (, x) if and only if z ≤h x. Now suppose that (, x) ⊨ (∀n)((∃z)φ(n, z) ↔ (∀z)ψ(n, z)). Then for each n, let f(n) be the <o-least m ∈ 1 such that (, x) ⊨ (∃z|m|)(φ(n, z|m|)∨ ¬ψ(n, z|m|)). f is a total , and hence , function. It follows that there is an n0 ∈ 1 such that f(n)<o n0 for all n. Let y be a real such that n ∈ y if and only if (, x) ⊨ ∃z|m0|(φ(n, z|n0|). Then y ∈ (, x) and

Suppose that (, x) satisfies the -comprehension axiom. For the sake of contradiction, assume that > . Let n ∈ x be such that n = 3⋅5e and |n|x = .

Note that for m <ox n. Let φ(n, z) be

If m <ox n, then is the unique real z such that . Thus.

Then by -comprehension, there is a y ∈ (, x) such that

Since for m <ox n, we have y = , contradicting Proposition 5.1.3.

Remark 5.1.6. The results above may be generalized. For example, one may introduce the language (, ẋ, ż), define the structure (, x, z), and show that all the results above hold. Then {(x, ⌜φ⌝, z) | φ is ∧ (, x, z) ⊨ φ} is . Moreover, (, x, z) satisfies -comprehension if and only if (, x, z) is precisely the collection of reals hyperarithmetic in x ⊕ z, and if and only if .

5.1.4 Exercise

Exercise 5.1.1. Prove that (, ) is the smallest ω-model satisfying the -comprehension axiom.

5.2 Cohen forcing

Cohen’s original notion of forcing was defined over a structure similar to the ramified analytical hierarchy, although subsequent developments in set theory have since followed a different approach. For hyperarithmetic theory, this hierarchy is the most natural setting in which to study forcing.

The collection P of forcing conditions we consider here are relatively simple, such as finite binary strings or hyperarithmetically encoded perfect sets. A forcing relation ⊩ is a binary relation that is a subset of P×{⌜φ⌝| φ is a formula in (, ẋ)}. The objective is to make ⊩ as simply defined as possible. For example, to be hyperarithmetic when the formula φ being forced is ranked, or when φ is . The generic set x will be a real that is obtained from a collection of pairwise compatible conditions through a union or intersection operation. The model (, x) is then a generic extension of (, ). We always make (, x) satisfy -comprehension so that = . With this, one can construct generic x’s with a prescribed property.

5.2.1 Cohen forcing

A Cohen condition p is a finite string σ ∈ 2<ω which may be identified with the basic open set [σ]. Define a partial ordering ≤ such that p ≤ q if and only if p q.

Given formulas φ(x) and ψ(n), denote by φ(x | ψ) the formula obtained upon replacing every occurrence of n ∈ x in φ with ψ(n) and every occurrence of n ∉ x in φ with ¬ψ(n).

For a sentence φ ∈ (, ẋ), define p ⊩ φ by induction on the complexity of φ:

–p ⊩ n̄ ∈ ẋ if and only if p(n) = 1;

–p ⊩ t1 = t2 if and only if (, 0) ⊨ t1 = t2, where t1, t2 are terms involving only numerals and arithmetic operations;

–p ⊩ t ∈ ẋ if and only if (, 0) ⊨ t = n̄ for some n and p ⊩ n̄ ∈ ẋ, where t is a term involving only numerals and arithmetic operations;

–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̄) with 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 are easy to verify.

Proposition 5.2.1. For any formula φ,

Theorem 5.2.2 The set {(p, ⌜φ⌝) | p ⊩ φ ∧ φ is } is .

Proof. Note that the set of -sentences is , and if (∃x)θ(x) is where θ(x) is arithmetical, then p ⊩(∃x)θ(x) if and only if there exists an n ∈ 1 such that p ⊩ θ(x|n|). By the Σ-Induction Theorem (3.1.8) and the definition of forcing, there is a Σ1-formula ψ(u, v) in the language of set theory such that for a -sentence φ, 〈, ∈〉 ⊩ ψ(p, ⌜φ⌝) if and only if p ⊩ φ. By the Spector–Gandy Theorem (3.7.1), the set {(p, ⌜φ⌝) | p ⊩ φ ∧ φ is } is .

A set D ⊆ 2<ω is dense if for any p ∈ 2<ω, there is a q ∈ D such that q ≤ p. Given a sentence φ, let Dφ = {p | p ⊩ φ ∨ p ⊩¬φ}. The next lemma follows from (ii) of Proposition 5.2.1.

Lemma 5.2.3. Given a formula φ, Dφ is dense.

A real x is Cohen generic if for any sentence φ there is an n such that x ↾ n ⊩ φ or x ↾ n ⊩ ¬φ. By Lemma 5.2.3 and induction on the set of Gödel numbers of formulas, it is an easy exercise to show that a Cohen generic real exists. The following theorem states that for a generic real, forcing equals truth.

Theorem 5.2.4 Suppose that x is Cohen generic. Then for any sentence φ, (, x) ⊨ φ if and only if there is an n such that x ↾ n ⊩ φ.

Proof. Either direction of the theorem may be proved by induction on the complexity of formulas. We show the nontrivial case when φ is of the form ¬ψ.

Suppose that there is an n such that x ↾ n ⊩ ¬ψ. We claim that (, x) ⊭ ψ. Otherwise, by induction, there is an m such that x ↾ m ⊩ ψ. By Lemma 5.2.1, x ↾(m + n)⊩ ψ ∧¬ψ, contradicting Lemma 5.2.1. Hence (, x) ⊨ ¬ψ, i.e. (, x) ⊨ φ.

Assume that (, x) ⊨ ¬ψ. By induction, x ↾ n ⊮ ψ for any n. Since x is Cohen generic, there exists an m such that x ↾ m ⊩ ψ or x ↾ m ⊩ ¬ψ. Hence x ↾ m ⊩ ¬ψ.

Theorem 5.2.5 If x is Cohen generic, then (, x) satisfies -comprehension.

Proof. Suppose that x is Cohen generic and

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

By Theorem 5.2.4, there exists a p ≺ x such that

By the definition of forcing,

Hence

Therefore

By the -Uniformization Theorem (4.2.1), there is a total and so -function f : {q | q ≤ p}× ω → ω such that f(q, n) = m if and only if m ∈ 1 and there is an r ≤ q with r ⊩ (∃z|m|)(φ(n, z|m|)∨¬ψ(n, z|m|)). Let S be the range of f.

By Theorem 5.2.2, f is a well-defined -function. Since f is total on its domain, it is . By Corollary 1.5.2, there is an n0 ∈ O1 such that for any m ∈ S, m <o n0. Then

Hence

and so

Since x ≻ p, by Theorem 5.2.4,

Let y be such that n ∈ y if and only if . Then y ∈ (, x). Now if n ∈ y, then (, x) ⊨ (∃z)φ(n, z). If n ∉ y, then . Then by assumption, (, x) ⊨ (∀z)¬φ(n, z). Thus (, x) satisfies -comprehension.

Corollary 5.2.6 If x is Cohen generic, then

(i) = .

(ii)For any real y ≤h x, there is an n ∈ such that y ≤T x ⊕ Hn.

Proof. Theorem 5.2.5 and Theorem 5.1.5 give (i) as an immediate consequence.

For (ii), suppose y ≤h x. Then by Corollary 5.1.4 and (i), y ∈ (, x). By Theorem 5.2.4, there is a ranked formula φ such that for any k, y(k)= 1 ⇔ (∃m)(x ↾ m ⊩ φ(k)) and y(k)= 0 ⇔ (∃m)(x ↾ m ⊩ ¬φ(k)). By Theorem 5.2.2,

is . Since is -complete (Theorem 1.5.1), there is a recursive function f : 2<ω × ω × 2 → ω such that f(p, k, i)∈ if and only if R(p, k, i)holds.

Define Rx ⊆ ω × 2 × so that Rx(k, i, n) if and only if n ∈ and there is an m with f(x ↾ m, k, i)= n. Then Rx is (x). By Theorem 4.2.1, there is a total (x), hence (x), function h : ω → 2 × ω uniformizing Rx. Thus Range(h) is a (x)-set. By (i) and Corollary 1.5.2, there is an n0 ∈ such that Range(h) ⊆ 2 × n0). Hence for any k, y(k)= 1 ⇔ (∃m)(f(x ↾ m, k, o)∈ n0), and y(k)= 0 ⇔ (∃m)(f(x ↾ m, k,0) ∈ n0). It follows that and hence there is an n ∈ such that .

From the topological point of view, a Cohen generic real is one which meets all definable dense open sets. Thus the set of such reals is co-meager. In Chapter 14, we will develop a parallel notion of forcing based on the co-null property.

5.2.2 Applications to hyperdegrees

We now use Cohen forcing to study the structure of hyperdegrees.

Proposition 5.2.7. If z is not hyperarithmetic, then there exists an x such that x ≰h z and x ≱h z.

Proof. Assume that z is not hyperarithmetic. Fix an enumeration {zi}i<ω of reals hyperarithmetic in z and an enumeration {φi}i<ω of all formulas.

We define a sequence = p0 ≥ p1 ≥ … of conditions as follows:

Suppose that pi is defined. At stage i + 1, first let ≤ pi so that there exists a j with (j) ≠ zi(j). Then let ≤ so that ∈ Dφi. This is possible according to Lemma 5.2.3.

See if φi(n, k) is ranked and whether for all n, there exists an r ≤ and k such that r ⊩ φi(n, k). If not, let pi+1 = and go to next stage. Otherwise, see if for all n and r ≤ , if r ⊩ φi(n, k) then k is unique. If this is so, let pi+1 = and go to next stage. If not, let pi+1 ≤ so that there exists an n with pi+1 ⊩ φ(n, k) for some k ≠ z(n).

Let x = ⋃i<ω pi. Then x is Cohen generic and x ≰h z. By Corollary 5.2.6, = . If x ≥h z, then by Corollary 5.1.4, there is a ranked formula φi(n, k) in the enumeration list such that z(n)= k if and only if (, x) ⊨ φi(n, k). By Theorem 5.2.4, for each n, there exist k and m such that x ↾ m ⊩ φi(n, k). Then by the construction at stage i + 1, it must be the case that for every n and r ≤ , there is a unique k satisfying r ⊩ φi(n, k). Define ̂z(n)= k if and only if there is an r ≤ with r ⊩ φi(n, k). By Theorem 5.2.2, ̂zis and hence hyperarithmetic. But z = ̂z, a contradiction.

Thus x ≰h z and x ≱h z.

5.2.3 Exercises

Exercise 5.2.1. Prove that there exists a Cohen generic x ≤T (ω)

Exercise 5.2.2. Prove that there is a sequence {xi}i<ω of reals such that for each j, xj ≰h {〈i, n〉| n ∈ xi ∧ i ≠ j}.

Exercise 5.2.3. Prove that any countable partial ordering is embeddable into the set of hyperdegrees.

Exercise 5.2.4. Prove that the Σ1-theory of the hyperdegrees as a partial ordering is decidable.

Exercise 5.2.5. Prove that for any nonhyperarithmetic x, the set {y | y ≱h x ∧ y ≰h x} is co-meager.

5.3 Sacks forcing

The notion of forcing with perfect sets over the ramified analytical hierarchy was introduced by Gandy and Sacks [36] in their construction of a set with minimal hyperdegree. The origin of perfect set forcing, however, traces back to Spector’s proof of the existence of a minimal Turing degree [154]. As will be seen, the construction of a minimal hyperdegree is much more intricate as it requires a detailed analysis of the complexity of the forcing relation ⊩.

5.3.1 Perfect set forcing over the ramified analytical hierarchy

Let be the collection of hyperarithmetic perfect sets. Each S ∈ is a condition for Sacks forcing. Given two conditions S, T ∈ , we say that S ≤ T if S ⊆ T.

Let φ be a sentence in the language of ramified analytical hierarchy (, ẋ). Define T ⊩ φ as follows.

–If φ is ranked, then T ⊩ φ if (∀x ∈ T)((, x) ⊨ φ);

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

–T ⊩(∃y)φ(y) if and only if T ⊩ (∃yβ)φ(yβ) for some β < ;

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

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

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

Note that while the definition of Cohen forcing for ranked sentences is by induction on the complexity of the sentence, that of Sacks forcing is given directly. This immediately implies the following.

Lemma 5.3.1. If T ⊩ φ and S ≤ T, then S ⊩ φ.

By Theorem 5.1.1 and the definition of forcing, we have

Lemma 5.3.2. The set

{(T, ⌜φ⌝) | φ is ∧ T ⊩ φ}

is

Lemma 5.3.3. (Fusion Lemma) Let T be a condition and {(i, φi)}i<ω be a hyperarithmetic set of -formulas. Assume that

(∀i)(∀P ≤ T)(∃S ≤ P)(S ⊩ φi).

Then (∃S ≤ T)(∀i)(S ⊩ φi).

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

Note that is a -relation. Then may be uniformized by a partial -function F : ω×2<ω × → . By assumption, for any R ≤ T, σ ∈ R and i ∈ ω, F(R, i, σ) is defined. Using F, a hyperarithmetic family {Pσ | σ ∈ 2<ω} is defined by recursion on σ:

If σ ∉ Pσ, let = = . Otherwise let and be disjoint conditions stronger than (i.e. contained in) Pσ and ↾|σ|, ↾|σ| = {τ | τ ≺ σ} so that .

Let Q = ⋂n ⋃|σ|= n Pσ. Then Q ∈ .

For each i and σ ∈ 2i+1, we have either Pσ = or Pσ ⊩ φi. Suppose that φi is of the form (∃z)ψi(z) for some ranked ψi(z). Then for some βσ whenever Pσ ≠ . Let . By the definition of the forcing relation, we have

Hence for every i, Q ⊩ φi.

Lemma 5.3.4. For any sentence φ and condition T, there is an S ≤ T such that either S ⊩ φ or S ⊩¬φ.

Proof. If φ is unranked, then the lemma follows immediately from the definition. For φ of rank β, we prove the lemma by induction on β. Without loss of generality, assume that φ is of the form (∃xβ)ψ(xβ) for some ψ with rank less than β. Let {̂ϕi(n)}i<ω be a hyperarithmetic enumeration of all the formulas of rank at most β whose only free variable is n. If there is an i and S ≤ T such that S ⊩ ψ(xβ | ̂ϕi), then we are done. Otherwise, by Lemma 5.3.3 and the inductive hypothesis, there is an S ≤ T such that S ⊩¬ψ(xβ | ̂ϕi) for every i. Then S ⊩ ¬φ.