4 The theory of -sets

-sets of reals are endowed with rich structural properties, including those that are best understood from the perspective of the constructible universe L. In this chapter a deeper analysis of such sets is presented to elucidate this point.

4.1 A -basis theorem

4.1.1 Tree presentations for -sets

Recall that given a -set A ⊆ 2ω, there is a recursive predicate P ⊆ 2ω × ωω such that x ∈ A if and only if (∀f)(∃n)¬P(x ↾ n, f ↾ n). In other words, x ∈ A if and only if the x-recursive tree Tx ={σ |(∀τ)(τ σ → P(x ↾|τ|, τ))} is wellfounded under the Kleene–Brouwer ordering. Then there is a function px : Tx → with px ∈ [x] such that px is order preserving under the Kleene–Brouwer ordering.

Now let be a set so that (σ, p) ∈ T if and only if p is an order-preserving finite function from {τ | τ ∈|σ|≤|σ| ∧(∀τʹ)(τʹ τ → P(σ ↾|τʹ|, τʹ))} to ω1. Define (σʹ, pʹ) (σ, p) if and only if σʹ σ and pʹ extends p. Then T is a tree under ≻. Thus x ∈ A if and only if there is an f : Tx → ω1 such that (x, f) is an infinite path in T, and this holds if and only if there is an f : Tx → ω1 with f ∈ [x] such that (x, f) is an infinite path in T.

The advantage with a tree presentation is that the companion path f of x exists in [x].

Given (σ, p), (σʹ, pʹ) ∈ 2<ω × , we say that (σʹ, pʹ)<l (σ, p) if

–either (σʹ, pʹ)≻(σ, p), or

–there is an i such that σʹ(i) < σ(i) and for all j < i, σʹ(j)= σ (j), or

–there is a ν ∈ ω<ω such that pʹ(ν) < p(ν) and for all νʹ <KB ν, νʹ ∈ Dom(σ)⇒ pʹ(νʹ)= p(νʹ).

An infinite path (x, f) in T is the leftmost path if there is no infinite path in {(σ, p)| (σ, p)<l (x ↾|σ|, f ↾Dom(p))}.

Lemma 4.1.1. Suppose that (x, f) is the leftmost path of T, then f ∈ [x].

Proof. Suppose that (x, f) is the leftmost path of T. Then f is the unique order-preserving function from the x-recursive tree Tx ={σ | P(x ↾|σ|, σ)} onto an initial segment of . Since [x] is admissible, by the Σ-induction Theorem (3.1.8), we have f ∈ [x].

4.1.2 A constructible basis theorem

Theorem 4.1.2 (Guaspari [42]). If A ⊆ 2ω is a nonempty -set, then there is an x ∈ A such that x ∈ .

Proof. Let T be the tree presentation for A and (x, f) its leftmost path. We claim that x ∈ .

By Lemma 4.1.1, f ∈ [x]. Hence there is an ordinal α0 < such that Rang(f)= α0. We define a tree Tα0 by replacing ω1 with α0 in T everywhere. Obviously Tα0 ∈ Lγ0 for some γ0 < and (x, f) is an infinite path in Tα0. Moreover, for any (σ, p)<l (x ↾ |σ|, f ↾ Dom(p)), there is no infinite path in ={(σʹ, pʹ) ∈ Tα0 |(σʹ, pʹ) ≻ (σ, p)}. Otherwise, any such infinite path would also be in T and to the left of (x, f), which contradicts the choice of (x, f) in T. Then for any (σ, p)<l (x ↾|σ|, f ↾ Dom(p)), there exist ordinals α(σ, p) < , β(σ, p) < α(σ, p) and a function g(σ, p) ∈ Lα(σ, p) such that g(σ, p) is an order-preserving function from to β(σ, p). Moreover, the function from (σ, p)<l (x ↾|σ|, f ↾Dom(p)) to α(σ, p) < is Σ1 in [x]. Since the set {(σ, p, )| (σ, p)<l (x ↾|σ|, f ↾ Dom(p))} is an element of [x], there is a γ < that bounds any α(σ, p) where (σ, p)<l (x ↾|σ|, f ↾Dom(p)).

We may assume that γ > α0. Now working in Lγ, we define an infinite path as follows:

(σ0, p0) = .

(σi+1, pi+1) ≻ (σi, pi) in Tα0 is of length i + 1 so that

(1) for all (σ, p) <l (σi+1, pi+1) not extending (σi+1, pi+1), there is an order-preserving function g(σ, p) ∈ Lγ from into an ordinal β(σ, p) < γ, and

(2) there is no order-preserving function g ∈ Lγ from into any ordinal β < γ.

By the assumption of γ, we have ⋃i<ω(σi, pi) = (x, f). Clearly the sequence {(i, σi, pi)}i<ω is an element of Lγ+ω. Hence (x, f) ∈ Lγ+ω ⊆ , and so x ∈ .

We have as an immediate consequence of Theorem 4.1.2,

Corollary 4.1.3. If x is a -singleton, then x ∈ .

4.1.3 Exercises

Exercise 4.1.1. Use Theorem 4.1.2 to prove Proposition 4.2.5.

Exercise 4.1.2. Prove that there is a nonconstructible real if and only if there is a nonempty -set which does not contain a constructible real.

4.2 -uniformization

4.2.1 Uniformizing -relations

Given a relation R ⊆ 2ω × 2ω, arelation R0 is a uniformization of R if for any x and y, R0(x, y) implies R(x, y) and for any x, if there is a y such that R(x, y), then there is a unique y such that R0(x, y). Uniformization of R is in effect a choice function for R.

Theorem 4.2.1 (Kondô [74] and Addison [1]). Suppose that R ⊆ 2ω × 2ω is . Then there is a -relation R0 that uniformizes R.

Proof. Suppose that R ⊆ 2ω × 2ω is . By Corollary 3.7.2, there is a Σ0-formula φ(u, v, w) such that

Define R0 ⊆ 2ω × 2ω so that (x, y) ∈ R0 if and only if

By Theorem 4.1.2, if there is a y such that (x, y) ∈ R, then there is one such that R0(x, y). By the definition of R0, R0 uniformizes R. Note that both (i) and (ii) above are Σ1-statements. By Proposition 3.3.3, (iii) is also a Σ1-statement. By Corollary 3.7.2, R0 is a -relation.

There are a number of interesting applications of the -Uniformization Theorem (4.2.1) which we now discuss:

Proposition 4.2.2 Given -sets A0 and B0, there exist disjoint -sets A1 ⊆ A0, B1 ⊆ B0 such that A0 ∪ B0 = A1 ∪ B1.

Proof. Let R ⊆ 2ω ×2 be a -relation such that (x, i) ∈ R if and only if either i = 0 and x ∈ A0 or i = 1 and x ∈ B0. By Theorem 4.2.1, there is a -relation R0 uniformizing R. Define x ∈ A1 if and only if (x, 0) ∈ R0 and x ∈ B1 if and only if (x, 1) ∈ R1. Then A1, B1 are as required.

Corollary 4.2.3. Given disjoint -sets A0, B0, there exist disjoint -sets A1, B1 such that A0 ⊆ A1, B0 ⊆ B1 and A1 ∪ B1 = 2ω.

Proof. The hypothesis implies that 2ω A0 and 2ω B0 are . By Proposition 4.2.2, there exist two -sets A1 ⊇ B0, B1 ⊇ A0 such that A1 and B1 are disjoint and A1 ∪B1 = 2ω. Hence these sets are .

4.2.2 Kreisel compactness

Kreisel’s Compactness Theorem is a generalization of the Compactness Theorem in model theory to -logic. In this setting, “recursively enumerable” is , and “finite” is . It is a striking application of the -Uniformization Theorem.

Theorem 4.2.4 (Kreisel). Let A ⊆ ω × 2ω be a -set such that for each n, An ={x | (n, x) ∈ A} is . Let z be . If ⋂n∈y An ≠ for every hyperarithmetic y ⊆ z, then .

Proof. Suppose not. Then z is properly and ⋂n∈z An = . Then for each x, there is an n such that x ∉ An. Define a -relation R ⊆ 2ω × ω such that R(x, n)⇔ n ∈ z ∧ x ∉ An. By the Uniformization Theorem (4.2.1), there is a total -function f uniformizing R. Then the set

is contained in z and is . If x ∈ ⋂n∈y An, then f(x) ∈ ω y. But no m ∈ ω y belongs to f[2ω]. Thus ⋂n∈y An = . By Corollary 4.2.3 restricted to ω, there is a -real y0 with y ⊆ y0 ⊆ z. Then ⋂n∈y0 An = , which is a contradiction.

Theorem 4.2.4 was further generalized by Barwise [3] to countable admissible sets as a compactness theorem for infinitary logic.

4.2.3 -singletons

Proposition 4.2.5 Every nonempty -set of reals contains a -singleton.

Proof. Suppose that A ⊆ 2ω is and nonempty. Let (n, x) ∈ R if and only if x ∈ A. Then R is a -relation. By Theorem 4.2.1, there is a -relation R0 uniformizing R. Then the uniquereal x such that (0, x) ∈ R0 is a -singleton.

By Proposition 4.2.5, we know that every nonempty -set contains a -singleton.

Proposition 4.2.6 The set {x | x is a -singleton} is .

Proof. Let P ⊆ ω × 2ω be a universal -set. By Proposition 4.2.5, there is -set P0 ⊆ P uniformizing P. Let A ={x |(∃n)(n, x) ∈ P0}. Then A is a set which contains precisely all the -singletons.

Since there are only countably many -singletons, there is a countable -set which is a basis for -sets of reals. This gives the following basis result for -sets.

Corollary 4.2.7. Every nonempty -set of reals contains a -member.

Proof. Suppose A is a nonempty -set of reals. Then x ∈ A if and only if (∃y)B(x, y) for some -relation B. By Proposition 4.2.5, there is a -singleton, and hence a -real, (x0, y0) such that B(x0, y0). Then x0 ∈ A is .

By the proof of Corollary 4.2.7, we have the following characterization of -reals.

Corollary 4.2.8. A real x is if and only if x is recursive in a -singleton. Hence the set of -reals is .

Corollary 4.2.9. (Shoenfield [129]).(i) If A ⊆ 2ω is nonempty and , then there is an x ∈ A ∩ L recursive in a -singleton.

(ii) Every -real is constructible.

Proof. (i) If A ⊆ 2ω is a nonempty -set, then there is a -set B ⊆ 2ω × 2ω such that x ∈ A if and only if there exists a y such that B(x, y). By Proposition 4.2.5, there is a -singleton B(x0, y0). By Corollary 4.1.3, (x0, y0) ∈ L. Thus x0 ∈ A is a constructible real recursive in the -singleton x0 ⊕ y0.

(ii) Immediate from (i), since every -real is a -singleton.

Corollary 4.2.9 (i) is known in the literature as the Shoenfield Absoluteness Lemma. There are many applications of this in set theory. For example, given a -predicate P, one has 〈L, ∈〉 ⊨ P if and only if 〈V, ∈〉 ⊨ P.

4.2.4 Exercises

Exercise 4.2.1. Prove that there is a -relation R ⊆ 2ω × 2ω which is not uniformizable by a Σ11-relation.

Exercise 4.2.2. Prove that there is no -set x ⊆ where <o restricted to x is a well-ordering of order type and such that there is a partial recursive function p : ω2 → ω satisfying properties (i)–(iii) of Exercise 1.4.1.

Exercise 4.2.3. Prove Theorem 4.1.2 from Theorem 4.2.1.

4.3 Characterizing thin -sets

A set is thin if it contains no perfect subset. There is a beautiful characterization of -thin sets in terms of constructibility.

4.3.1 The largest thin -set

Let ={x | x ∈ }.

Lemma 4.3.1. is a thin -set.

Proof. x ∈ if and only if . By Theorem 3.3.2 and Corollary 3.7.2, is .

Suppose is not thin. Let

B ={T ⊆ 2<ω | T is a perfect tree in which every infinite path belongs to .}

Then B is a -set. By Theorem 4.1.2, there is a T ∈ B with . By relativizing the Gandy Basis Theorem (2.5.3) to T, there is a real x ∈ [T] ⊆ such that x ≤h T and . Hence x ∉ , a contradiction.

Lemma 4.3.2. (Mansfield [87], Solovay [149]). Let A ⊆ 2ω be . If there is an x ∈ A such that x ∉ , then there is a perfect tree T ∈ L all of whose infinite paths belong to A.

Proof. Let be defined as before. Suppose A ⊆ 2ω is and there is an x ∈ A . Let α0 be the least ordinal α such that α = for some x ∈ A .

Let T0 be a tree presentation of A and be as defined in the proof of Theorem 4.1.2. Since is a -set, there is a recursive tree T1 ⊆ 2<ω × ω<ω such that x ∉ if and only if (∃y)(x, y)∈[T1]. Now let T2 ⊆ 2<ω × αω<ω × 2<ω be a tree defined as follows: (σ, p, τ) ∈ T2 if and only if (σ, p) ∈ and (σ, τ) ∈ T1. By assumption, there is an infinite path (x, f, y) in T2.

We claim that for any (σ, p, τ) ∈ T2, if there is an infinite path in T2,(σ, p, τ) = {(σʹ, pʹ, τʹ) ∈ T2 |(σʹ, pʹ, τʹ) ≻ (σ, p, τ)}, then there are (σ0, p0, τ0) and (σ1, p1, τ1) in T2,(σ, p, τ), with σ0 and σ1 incompatible, such that both T2,(σ0, p0, τ0) and T2,(σ1, p1, τ1) have infinite paths. Otherwise, fix a (σ, p, τ) ∈ T2 for which this is false. Then there is an infinite path (x, f, y) in T2,(σ, p, τ). Note that ≥ α0. By assumption, for any σʹ ≻ σ that is not an initial segment of x, the tree

T2, σʹ ={(σʺ, pʺ, τʺ) ∈ T2,(σ, p, τ) | σʹ ≻ σ}

is wellfounded. Then by the same proof as that of Theorem 4.1.2, there is a γ < such that the set {σʹ | σʹ x ∧(∃pʹ)(∃τʹ)(σʹ, pʹ, τʹ) ∈ T2,(σ, p, τ)} belongs to Lγ. Then x ∈ Lγ+1 ⊆ , contradicting the fact that x ∉ .

By the claim, one may carry out the first construction of Theorem 1.1.10 to obtain a perfect tree all of whose paths belong to A. Thus the set {T | T is perfect ∧[T]⊆ A} is a nonempty -set. By Theorem 4.1.2, there is a perfect tree T ∈ L such that [T]⊆ A.

By Lemma 4.3.1 and Lemma 4.3.2, we have the following characterization of the largest thin -set.

Theorem 4.3.3. is the largest thin -set.

4.3.2 Some properties of

Since every -set of reals contains an x ∈ that is also a -singleton, one may ask if every real in is a -singleton. This is false since is uncountable in L.

Proposition 4.3.4 For any real x ∈ L, there is a z ∈ such that z ≥T x.

Proof. Let x ∈ L. By Corollary 3.3.8, x ∈ Jα+1 Jα for some α <(ω1)L. Then x is Σn(Jα+1) for some n. By Theorem 3.4.11, there is a real z ∈ Jα+1 Jα which is a Σn-master code. Thus = ω. By the definition of Σn-master code, there is a z-recursive well-ordering of α. In other words, > α. Thus z ∈ and x ≤T z.

Proposition 4.3.5. There is an x ∈ in which every -singleton is recursive.

Proof. By Proposition 4.1.3, every -singleton is in L. Since 〈L, ∈〉 ⊨ ZFC, the statement “there are only countably many -singletons” is true in L. Hence there is a real y ∈ L in which every -singleton in L is recursive. By Proposition 4.3.4, y ≤T z for some z ∈ .

Corollary 4.3.6.

(i) is the largest countable -set of reals if and only if (ω1)L < ω1.

(ii)There is an uncountable thin -set if and only if (ω1)L = ω1.

Proof. (i) By Proposition 4.3.4, if is countable, then L ∩ 2ω is countable. So (ω1)L is countable.

Suppose that (ω1)L is countable. Then by Proposition 4.3.2, every -countable set of reals is a subset of . By Corollary 3.3.8, is countable.

(ii) follows from (i).

4.3.3 Exercise

Exercise 4.3.1. Show that if ω1 =(ω1)L, then there is no largest countable -set of reals.

4.4 -sets

-sets and -sets of reals are similar in several respects. We list some of them here.

Corollary 4.4.1. 2ω ∩ L is .

Proof. By Proposition 4.3.4, x ∈ L if and only if there is a y ∈ such that y ≥T x.

Proposition 4.4.2 x ≤L y is a -relation.

Proof. x ≤L y if and only if x, y ∈ L and there is a binary relation E ⊆ ω such that

–〈ω, E〉 is wellfounded;

–〈ω, E〉 ⊨ V = L + KP;

–〈ω, E〉 ⊨ x ≤L y.

Thus the relation x ≤L y is .

The following is an analog of the Spector–Gandy Theorem for -sets.

Proposition 4.4.3 A set A ⊆ 2ω is if and only if there is a Σ1-formula φ such that

Proof. Suppose that A ⊆ 2ω is . Then there is a -relation B ⊆ 2ω × 2ω such that

x ∈ A ⇔ (∃y)B(x, y).

By Corollary 3.7.2, there is a Σ1-formula ψ such that

Since for every x, Bx ={y | B(x, y)} is (x), by relativizing Theorem 4.1.2 there is a y ∈ Bx such that

Hence

Now let φ be

By Theorem 3.3.2, φ is Σ1. By the discussion above, x ∈ A if and only if 〈L[x], ∈〉 ⊨ φ if and only if 〈L(ω1)L[x] [x], ∈〉 ⊨ φ

For the other direction, suppose there is a Σ1-formula φ such that x ∈ A ⇔ 〈L[x], ∈〉 ⊨ φ. Then for each x, there is a cardinal κ such that x ∈ A ⇔〈Lκ[x], ∈〉 ⊨ φ. By the Condensation Theorem (3.3.7), there is a countable admissible ordinal α such that x ∈ A ⇔〈Lα[x], ∈〉 ⊨ φ. Since φ is Σ1, we have x ∈ A ⇔〈L[x], ∈〉 ⊨ φ ⇔ 〈L(ω1)L[x] [x], ∈〉 ⊨ φ.

By Theorem 3.3.4, 〈L(ω1)L[x] [x], ∈〉 ⊨ φ if and only if there is a countable transitive wellfounded model 〈M, ∈〉 ⊨ KP + “V = L[x]” + φ. Hence 〈L(ω1)L[x] [x], ∈〉 ⊨ φ if and only if

(∃E)(〈ω, E〉 codes a wellfounded transitive model ∧〈ω, E〉 ⊨ KP + “V = L[x]” + φ).

By Proposition 3.6.2, the set {x | 〈L(ω1)L[x] [x], ∈〉 ⊨ φ ={x |〈L[x], ∈〉 ⊨ φ} is .

Thus one may regard Lω1 as the structure where -sets are based. In a way, -ness draws the boundary between recursion theory and set theory. Within ZFC, it is not possible to generalize results in the previous sections to a level beyond . One needs additional set-theoretic assumptions for this. How this is to be implemented is a major subject in descriptive set theory. From this perspective, higher recursion theory serves as a launch pad for the study of descriptive set theory beyond the level of . Let

and

Proposition 4.4.4 δ = .

Proof. If α < δ, then there is a -singleton x ∈ Lδ Lα. Since x ∈ and is a (x) well-ordering, α < < . Hence δ ≤ .

If α < , then there is a well-ordering relation R ⊆ ω × ω of order type α. Then there exist arithmetical relations S, T ⊆(ωω)2 × ω2 such that

Define -sets

R0 ={(h, 〈n, m〉) | h(0)= 0 ∧(∃f)(∀g)S(f, g, n, m)∧(∀n)(f(n)= h(n + 1)))}

and

R1 ={(h, 〈n, m〉) | h(0)= 1 ∧(∃f)(∀g)T(f, g, n, m)∧(∀n)(f(n)= h(n + 1)))}.

By the -Uniformization Theorem (4.2.1), the two relations may be uniformized by partial -functions pR0 and pR1 : ω → ωω. Let p = pR0 ∪ pR1. Then p is a total -function and may be viewed as a -singleton. Then R is arithmetical in p and hence α < < δ. Thus = δ.

This gives a finer version of the Spector–Gandy Theorem for -sets:

Proposition 4.4.5 A real x is if and only if x is Σ1-definable over 〈, ∈〉.

Proof. Suppose that x is . Then there is a Σ0-formula φ(n, y) such that

By Corollary 4.2.9 and Proposition 4.4.4, we have

Assume and fix such a real y. Then Hence n ∈ x. Thus x is Σ1-definable over 〈, ∈〉.

Conversely, suppose that x is Σ1-definable over 〈, ∈〉 via the formula φ(n). By Proposition 4.4.4, we have n ∈ x if and only if there exists a z ∈ such that 〈, ∈〉 ⊨ φ(n). Thus x is .

It is possible to relativize “-ness” in the obvious way and define the relation “x is in y” and thereby introduce the notion of a -degree. Let be the supremum of all well-orderings of ω that are in x. The following result says in a strong way that Post’s problem has a negative solution for the -degrees.

Proposition 4.4.6

(i)If x is constructible and not , then > .

(ii) Assume V = L. Then is a well-ordering of the -degrees and its order type is ω1. Moreover, if then .

Proof. (i) Let

A ={r | r codes a well-ordering of ω ∧ x ∈ L|r|},

where |r| denotes the order type of r as a well-ordering. Then A is (x). Let r ∈ A. Since x is not we must have |r|> . Hence > .

(ii) If V = L, then by Proposition 4.4.2, ≤L is a well-ordering of the reals. Suppose that x ≤L y. Then by the proof of (i), there is a (y)-real r coding a well-ordering of ω such that y ∈ L|r| and so x ∈ L|r|. Then and hence x ≤h r y. Thus x y. So is a well-ordering of -degrees and its order type is ω1. If x y, then by the same argument as that in (i) but relativized to y, we have .

Proposition 4.4.6 indicates that while L is an appropriate ground model for hyperarithmetic theory, it is less so for a -theory as the well-ordering of the relation makes the structure of the corresponding degrees relatively simple and hence less interesting.

4.4.1 Exercises

Exercise 4.4.1 (Solovay [149] and Mansfield [87]). Prove that every -set of reals containing a nonconstructible real has a perfect subset.

Exercise 4.4.2. 2ω ∩ L is the largest countable -set of reals if and only if (ω1)L < ω1.

Exercise 4.4.3. If ω1 =(ω1)L, then there is no largest countable -set of reals.

Exercise 4.4.4. Prove that there is a real x and a nonempty -set P ⊆ 2ω such that > but there is no real z ∈ P such that z x.

Exercise 4.4.5. Suppose that is a countable language and T is a consistent theory of . Then T has, up to elementary equivalence, either ≤ℵ0 or 2ℵ0 -many countable models.