8 The construction of -sets

As seen in the previous chapters, inductive definition plays a key role in hyperarithmetic theory. In fact Gandy (see [106]) held the view that inductive definition rather than computation constituted the core characteristic of any generalized recursion theory. Admissible set theory (Chapter 3) reinforces the line of thought. Here we discuss inductive definition in greater detail and present some applications of this notion to the construction of -sets. The reader is referred to [47] and [106] for more on this subject.

8.1 An introduction to inductive definition

8.1.1 Inductive definability

Definition 8.1.1. Let Γ : 2ω → 2ω be a function.

–Γ is progressive if x ⊆ Γ(x) for every x ∈ 2ω;

–Γ is monotonic if Γ(y) ⊆ Γ(x) if y ⊆ x.

Given a function Γ : 2ω → 2ω, let

A real x ∈ 2ω is inductively defined by Γ if x = Γ∞. We use |Γ| to denote the least ordinal α such that Γα = Γ∞. Note that |Γ| < (2ℵ0)+. It is not difficulty to see that for any real x, there is a function Γ : 2ω → 2ω such that x is inductively defined by Γ (Exercise 8.1.1).

Theorem 8.1.2. (Gandy). Suppose that Γ is a progressive function such that the set {(n, x) ∈ ω × 2ω | n ∈ Γ(x)} is . Then |Γ| ≤ and Γ∞ is .

Proof. By Theorem 3.1.8, there is a Σ1()-definable function f : → such that f(β) = Γβ for . Let x be a real such that

n ∈ x ⇔ (∃)(n ∈ f(β)).

Note that x = . Moreover x is Σ1-definable in 〈, ∈〉 and hence . Let R be a recursive predicate such that for any i,

i ∈ Γ(x) ⇔ (∀j)R(i, x ↾ j).

Fix an i ∈ Γ(x). Then (∀j)R(i, x ↾ j). Now for each j ∈ ω, there is an ordinal β < such that Γβ ↾ j = x ↾ j and hence R(i, Γβ ↾ k) for every k ≤ j. Since R is recursive, we have

〈, ∈〉 ⊨ (∀j)(∃β)R(i, Γβ ↾ j).

By induction, let βj be the least β > βj−1 such that 〈, ∈〉 ⊨ R(i, Γβ ↾ k) for every k ≤ j. Then the function p : j ↦ βj is Σ1()-definable and hence belongs to by the admissibility of . It follows that the ordinal β(i) = j<ω βj is a limit ordinal less than . Note that Γβj ⊆ Γβj+1 for j<ω. Then for each k, there is a j ≥ k such that Γβ(i) ↾ k = Γβj ↾ k. Thus

〈, ∈〉 ⊨ R(i, Γβ(i) ↾ k).

In other words,

〈, ∈〉 ⊨ (∀k)R(i, Γβ(i) ↾ k).

Hence if i ∈ Γ(x), then i ∈ Γβ(i) and so i ∈ x. Thus Γ(x) ⊆ x, i.e. Γ(x) = x. We conclude that x = Γ∞.

8.1.2 Monotonic inductive definability of -reals

Proposition 8.1.3. Let k > 0. Suppose that Γ is progressive and monotonic, and the set {(n, x)| n ∈ Γ(x)} is . Then Γ∞ is .

Proof. Since Γ is progressive and monotonic, Γ∞ is the least real (in the sense of inclusion) x such that Γ(x) ⊆ x. Then n ∈ Γ∞ if and only if

(∀x)(Γ(x) ⊆ x → n ∈ Γ(x)).

If the set {(n, x)| n ∈ Γ(x)} is , then Γ∞ is .

The following strengthens Theorem 8.1.2 for monotonic functions.

Theorem 8.1.4. (Spector [153]). Suppose that Γ is progressive and monotonic such that {(n, x) ∈ ω × 2ω |n ∈ Γ(x)} is . Then |Γ| ≤ .

Proof. We prove that Γ()and |Γ| ≤ .

Let C ⊆ (ω × ω) be a -set such that x ∈ C if and only if

–{n | (1, n) ∈ x} =

–(∀j)(Γ({n | (j, n) ∈ x}) ⊆ {n | (2j, n) ∈ x}), and

–(∀e)(e ∈ → (j∈ω{n | (Φe(j), n) ∈ x} = {n | (3 ⋅ 5e, n) ∈ x})).

Let

Then z is . We leave it to the reader to verify that

Hence = {n | (∃j ∈ )((j, n) ∈ z)} is a -real.

Let i ∈ ∗ . Define D ⊆ × 2ω to be a -set such that x ∈ D if and only if

By Gandy’s Basis Theorem (2.5.3), there is a z∗ ∈ D such that = . For j ∈ , let

Clearly = . Moreover, for any j0 <o∗ j1 <o∗ i, ⊆ .

Suppose that n ∈ Γ(). We claim that there is a j ∈ ∩ such that n ∈ Γ() = Γ(Γ|j|). Otherwise, since Γ is monotonic, it must be the case that n ∈ Γ() for any j ∈ . Let

j ∈ yn ⇔ n ∈ Γ().

Note that ≤h z∗ for every j ∈ ∗. By Corollary 2.2.12, yn is (z∗). By the assumption, yn = . Thus yn is also (z∗) and hence (z∗). Obviously > and hence > , contradicting the choice of z∗. We conclude that Γ() ⊆ Γ(Γ|j|) = Γ|j| = .

8.1.3 Inductively defining

As an illustration, we show how may be defined inductively. Let Γ beafunctionsuch that for any x,

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

Proposition 8.1.5. Let Γ be as defined above. Then Γ∞ = = .

Thus is inductively defined by the arithmetical function Γ. Indeed, every -real is “generated” by a simple monotonic function Γ (Exercise 8.1.3).

8.1.4 Exercises

Exercise 8.1.1. Prove that for any real x, there is a function Γ : 2ω → 2ω such that x is inductively defined by Γ.

Exercise 8.1.2. Prove Proposition 8.1.5.

Exercise 8.1.3. For any -real z, there is a monotonic function Γ such that the set {(n, x)| n ∈ Γ(x)} is and z is many-one reducible to Γ∞.

Exercise 8.1.4. Suppose that Γ is a progressive function such that {(n, x) ∈ ω × 2ω | n ∈ Γ(x)} is . Show that if x is , then every ninΓ(x) belongs to Γ(y) for some hyperarithmetic y ⊆ x.

8.2 Inductively defining -sets of reals

There is a parallel way of defining -sets of reals inductively. In [164], Engelen, Miller and Steel constructed a number of -sets of reals not based on the method of inductive definition.1 We prove some of the results here via inductive definition (see Chong and Yu [17]).

8.2.1 A -induction principle for reals

Definition 8.2.1. A binary relation P(x, y) ⊆ 2ω × 2ω is cofinally progressive if for every real x, theset {y|P(x, y)} is cofinal in the hyperdegrees, i.e. for each z, there is a y ≥h z such that P(x, y) holds.

Let = {y | y ∈ }.

Lemma 8.2.2. Assume (2ω)L = 2ω. If P is and cofinally progressive, then for every x and z there is a y ≥h z such that y ∈ and P(x, y).

Proof. Suppose (2ω)L = 2ω and P is cofinally progressive. Then for any reals x, z, the set A = {y | x ⊕ z ∈ ∧ P(x, y)} is a nonempty (x ⊕ z)-set. By Theorem 4.1.2 there is a y ∈ A such that y ∈ [x ⊕ z]. Since x ⊕ z ∈ , we have x ⊕ z ≤h y and so = . Then y ∈ [x ⊕ z] = and P(x, y) holds.

Given a countable set A of reals and a real x, we say that x codes A if {(x)n | n < ω} = A where (x)n = {m | m < ω ∧ 〈n, m〉 ∈ x}.

A cofinally progressive relation generates a progressive relation as follows: Let P(x, y) be cofinally progressive. For each X ⊆ 2ω, let Q(X) = X ∪ {y | (∃x ∈ X)P(x, y)}. Then it is immediate that Q(X)⊇ X for all X. However, an operation such as Q may be too general to be useful and this motivates a refinement of Q to one that is similar to a uniformization function for well-defined sets. Now if P(x, y) is , then Theorem 4.2.1 guarantees the existence of a uniformization function for P. However, our interest is in strong uniformization, i.e. a function that uniformizes “initial segments of reals” that does roughly the following: If x codes a set of reals in such that any two elements w <L z in x satisfy P(w, z), then there is a “least” y ∈ such that x ≤ y and P(x, y) holds. This strong uniformization property enables one to implement an inductive construction which is made precise by the -inductive principle I defined as follows:

-inductive principle . If P(x, y) is and cofinally progressive, then there is a -set A ⊆ such that:

(i)|≤L↾ A|, the height of ≤L restricted to A, is ω1;

(ii)(∀y)(y ∈ A → (∃x)(x ∈ ∧ x codes the set {z | z ∈ A ∧ z <L y} ∧ P(x, y))).

Theorem 8.2.3 (Chong and Yu [17]). V = L implies .

Proof. Suppose V = L, and P is and cofinally progressive. Recall that for each constructibly countable β, there is an α > β such that (Lα+1 Lα) ∩ 2ω ≠ . Given ordinals β < α and X ⊆ α × ω, denote by X[β] the real {n | (β, n) ∈ X}. We may regard X as a sequence of reals of length α.

Since P is , by the Spector–Gandy Theorem (3.7.1) there is a Σ0-formula ψ(x, y, s) such that

Assume V = L. We define a partial function F which we will show to be total on ω1 × α<ω1 2α×ω. For α<ω1, z ∈ 2ω and X ⊆ α × ω, let be the least ordinal γ such that Lγ[X, z] is admissible. We define F(α, X) to be the real z such that [X, z] satisfies the following properties:

(1)there is a β ≥ α such that z ∈ Lβ+1 Lβ;

(2)there is an x ∈ which codes X;

(3)there is a limit ordinal γ and an element s ∈ Lγ such that Lγ[X, z] ⊨ ψ(x, z, s);

(4)if (t, y, μ) <L (s, z, γ), then 〈Lμ[X, y], ∈〉 ⊨ ψ(x, y, t) implies < β;

(5)if (t, y, μ) <L (s, z, γ) and 〈Lμ[X, y], ∈〉 ⊨ ψ(x, y, t), then either no real r ∈ codes X or y ∉ .

Since [X, z] = , <L is uniformly Δ1 in [X, z]. Moreover, (4) implies that (5) is Σ1 in [X, z]. Hence (1)–(5) are uniformly Σ1 in [X, z]. We show that F(α, X) is defined for α < ω1 if X is countable.

Fix (α, X). Since V = L, there is a countable γ′ > α with a real x ∈ Lγ′ coding X. Since P is cofinally progressive, by Lemma 8.2.2 there is a β > γ′ such that (Lβ+1 Lβ) ∩ 2ω ≠ , and a real z ∈ Lβ+1 Lβ such that x ⊕ z ∈ , Lγ ⊨ ψ(x, z, s) for some limit ordinal γ < and s ∈ Lγ. Note that = [X, z] and Lγ = Lγ[X, z] for all sufficiently large γ < . Hence (1)–(3) are satisfied. Clearly we can assume that (s, z, γ) is the <L-least satisfying these properties. Thus (4) and (5) are satisfied as well. By the absoluteness of <L, one concludes that F is a well-defined function on each (α, X), where α < ω1 and X is countable.

Observe that (1)–(4) are Σ1-statements. By (4), one verifies that (5) is a Δ1-statement. Hence there is a Σ0-formula φ(α, X, z, s) such that

Thus we may perform transfinite induction on α to define a sequence {zα | α < ω1} using F. However, the resulting sequence yields in general a set of reals that is Σ1 over Lω1, i.e. but not necessarily over second order arithmetic. To ensure that -ness is achieved, we refine the approach as follows.

Define G(α) = z if and only if α < and there is a function f : α + 1 → 2ω with f ∈ [z] so that for all β ≤ α, f(β) = F(β, {(γ, n)|n ∈ f(γ) ∧ γ < β}) and f(α) = z. Since [z] is admissible, {f(γ)| γ ≤ α} ∈ [z]. Hence G(α) = z if and only if there is a function f : α + 1 → 2ω with f ∈ [z] such that

Since [z] is admissible, G is Σ1-definable. In other words, G(α) = z if and only if there is a function f : α + 1 → 2ω with f ∈ such that

Let A be the range of G. Then z ∈ A if and only if there exists an ordinal α < and a function f : α + 1 → 2ω with f ∈ such that

Hence A is .

All that remains is to use an argument as that for Theorem 3.1.8 to show that G is a well-defined total function on ω1. The only nontrivial part is to prove that the function f defined above exists. This can be done by induction. Let α < ω1 be given and suppose that {fβ}β<α is a uniformly Σ1 and increasing (i.e. fβ ⊃ fγ for β > γ) sequence such that each fβ is an f at stage β < α as required, Let fα be such that fα ∈ [z] and for all β ≤ α, fα(β) = F(β, {(γ, n)| n ∈ fβ(γ) ∧ γ < β}) and fα(α) = z, where F(α, X) = z and X = {(γ, n) | (∃β)(γ ≤ β < α ∧ n ∈ fβ(γ))}. Note that X = {(γ, n)| γ ≤ α ∧ n ∈ fγ(γ))} by absoluteness. Then fα ⊃ fβ for all β < α and satisfies the requirement of such an f at stage α.

By (1) and (2) above, (x, z) ∈ Lγ and Lγ ∈ . So A ⊂ . Since P is cofinally progressive, (i) of the definition of is satisfied.

For (ii): If y ∈ A then y = G(α) for some α < ω1. By the definition of G, there is a real x ∈ such that x codes the set {G(β)| β < α} and P(x, G(α)) holds. Clearly β < α if and only if G(β) <L G(α). Hence (ii) holds.

It turns out that the -inductive principle is equivalent to the set-theoretic assumption (ω1)L = ω1, as we now show.

Theorem 8.2.4. (ω1)L = ω1 if and only if the -inductive principle holds.

Proof. The “if” direction is immediate: Choose P(x, y) to express x ≤T y. Then P is cofinally progressive. Let A be a -set satisfying for P, of <L-height ω1. Then (ω1)L = ω1.

For the other direction, suppose P is and cofinally progressive. Then for any pair of reals x, z ∈ L, the set Ux,z = {y | y ≥h z ∧ P(x, y)} is a nonempty (x, z)-set. By Theorem 4.1.2, there is a y ∈ Ux,z ∩ L. By Theorem 4.1.2 again,

〈L, ∈〉 ⊨ P is cofinally progressive.

By Theorem 8.2.3, there is a -set A such that (A)L witnesses the correctness of the inductive principle in L.

Since (ω1)L = ω1, (i) is true in V. Since the statement “x ∈ ” is and

by the Shoenfield Absoluteness Lemma (Corollary 4.2.9), 〈V, ∈〉 ⊨ (∀x)(x ∈ A → x ∈ . Hence A ⊂ .

Let y ∈ A. Since A ⊆ L, y ∈ L. Then there exists an x ∈ such that

〈L, ∈〉 ⊨ x codes the set {z | z ∈ A ∧ z <L y} ∧ P(x, y).

Since A ⊂ L, x codes the set {z | z ∈ A ∧ z <L y}. Since the relation P is and x, y ∈ L, by the Shoenfield Absoluteness Lemma (Corollary 4.2.9) again, P(x, y) holds. Hence (ii) follows.

One may relativize the -inductive principle to admit real parameters and obtain its boldface version . Then Theorem 8.2.4 may be generalized to state: Boldface -inductive principle fails if and only if there is no real x such that (ω1)L[x] = ω1. This leads to the following conclusion:

Corollary 8.2.5. The statement “ZFC + -inductive principle is false” is consistent if and only if “ZFC+ There exists an inaccessible cardinal” is consistent.

Proof. If fails, then (ω1)L[x] < ω1 for all x, so that the latter is inaccessible in L. Conversely, suppose ZFC+ “There is an inaccessible cardinal” is consistent. Then by Proposition 6.2.9 (the Levy collapsing map), ZFC+ “ω1 is inaccessible in L” is consistent. Now in a model M with such a property, ω1 > (ω1)L[x] for all x. Hence fails in M.

8.2.2 Exercise

Exercise 8.2.1 (Miller [100]). Asubsetof 2ω is almost disjoint if any two of its distinct members have finite intersection. Assume 2ω = (2ω)L. Prove that there is a -maximal almost disjoint set.

8.3 -maximal chains and antichains of Turing degrees

We now apply the -inductive principle I to construct some special -sets of Turing degrees.

8.3.1 Chains in the Turing degrees

Given a partial ordering (P, ≤P), p ∈ P is a minimal cover of A ⊆ P if q <P p for all q ∈ A and there is no r ∈ P such that r <P p having the same property. A set A ⊆ P is a chain if for any x, y ∈ A, either x ≤P y or y ≤P x. A chain A is maximal if there is no chain B ⊃ A. Define P(x, y) if and only if

y is a minimal cover of {(x)n | n ∈ ω} under ≤T.

Lemma 8.3.1. P(x, y) is a cofinally progressive relation.

Proof. We prove that for any countable set A = {xi}i<ω and any real x, there is a minimal cover z of A such that z″ ≥T x.

Fix an effective enumeration of partial recursive oracle functions {Φe}e<ω.

Given a perfect tree T, define the n-th level Levn(T) of T to be

{σ ∉ Levn−1(T)|(∃τ)(τ ∈ T ∧ σ ⪯ τ ∧ τ is an n-th splitting node on T)}.

Let {pn}n<ω be a recursive one-one enumeration of prime numbers. Allowing ambiguity, we will also use pσ to denote the prime number which codes the string σ. Given a recursive oracle function Φ, we use Φy = T to express the following:

(1)Φy is total;

(2)(∀n)(Φy(n) = ∏σ∈Levn(T) pσ).

Given a tree T and a string ν ∈ T, let Tν be the subtree of T consisting of all ν′ ∈ T extending ν. Define Ln(T) to be the leftmost n + 1-th splitting node and Rn(T) to be the rightmost n + 1-th splitting node on T.

For each finite string σ∗, real x and perfect tree T ⊆ 2<ω with σ∗ ∈ T, define (σ∗, x, T) to be the perfect tree that is the intersection of a sequence of perfect trees Tn given as follows:

T0 = Tσ∗.

Tn+1 = {τ | (∃σ ∈ Levn(Tn))(τ ⪯ σ)} ∪ Sn+1 ⊆ Tn

where Sn+1 is defined as:

Case 1. x(n) = 0: σ ∈ Sn+1 if and only if there exists τ ∈ Levn+1(Tn) so that σ ⪰ τ and τ = L1() for some ν which is an n-th splitting node of Tn.

Case 2. x(n) = 1: σ ∈ Sn+1 if and only if there exists τ ∈ Levn+1(Tn) so that σ ⪰ τ and τ = R1() for some ν which is an n-th splitting node of Tn.

Define

In other words, (σ*, x, T) is a subtree which, roughly speaking, codes x(n) at a 2n-th splitting node of Tσ*. Note that (σ*, x, T) ⊕ T ≥T x. Moreover, suppose for some recursive oracle function Φ, we have Φy = T for all y ∈ [T]. Then there is a recursive oracle function Ψ such that Ψy = x for all y ∈ (σ*, x, T). Furthermore, given an index of the oracle function Φ, an index of the oracle function Ψ may be effectively obtained from σ*. In other words, there is a recursive function f such that = x for all y ∈ [(σ*, x, T)]. Since Φy = T for all y ∈ [(σ*, x, T)] ⊆ [T] and x ⊕ T ≥T (σ*, x, T), there is a recursive function g so that = (σ*, x, T) for all y ∈ [(σ*, x, T)].

We give a sketch of the idea behind the construction of z. To obtain a minimal cover of a countable set A = {xi}i<ω, one makes appropriate modifications of the construction of a minimal degree (see [82]). To make the minimal degree relatively high (i.e. to make it compute a given x through jumps), one needs to code the indices of the perfect trees in the course of the construction. Were the construction uniform, one could use the Recursion Theorem to code the index of the next perfect tree being defined during the step by step construction. This technique could be applied to code x and xi into z for each i < ω. However, the construction to achieve minimality is nonuniform (one needs to decide whether the next tree will be an “e-splitting tree” or a “full tree”, which in general is a “double jump” question). Although it is highly nonuniform, the construction does become uniform once it is decided which situation one is in (see Substep 3 of the construction below). This is the reason for using z″ to “get up” to x.

We now turn to the construction.

Fix a real x and an enumeration {xi}i∈ω of A. Suppose the recursive oracle functional Φ0 satisfies = 2<ω for all reals y. We construct a sequence of perfect trees step by step. At step n, we construct a perfect tree Tn ≤T ⊕i<nxi and a finite string σn so that Tn ↾|σn|={τ | τ ⪯ σn}, |σn|> n and there is a recursive oracle functional Φen such that for each y ∈ [Tn], = Tn.