#### 3.6.3 Coding ω- and wellfounded models

We now work in the language of set theory and use “E” in place of the symbol ̂∈. The best models of set theory are of course those that are wellfounded.

Proposition 3.6.2. {E |〈ω, E〉 codes a wellfounded model} is .

Proof. 〈ω, E〉 codes a wellfounded model if and only if there is no function f : ω → ω such that for any pair (i, j), i < j if and only if 〈ω, E〉 ⊨ f(j)Ef(i).

Coding wellfounded models is a complicated matter, though such models are the “bona fide models” of set theory. The next best thing is to code ω-models. The reason for studying ω-models is that in considering reals or sets of reals in such models, one is assured that the “natural numbers” involved are standard numbers.

Proposition 3.6.3 {E |〈ω, E〉 codes an ω-model} is .

Proof. 〈ω, E〉 codes an ω-model if and only if there is an m ∈ ω and an injection f : ω → ω such that

(i) 〈ω, E〉 ⊨ “m is an infinite ordinal”;

(ii) f is a bijection between ω and {k | kEm}, and

(iii) for any pair (i, j), i < j if and only if 〈ω, E〉 ⊨ f(i)Ef(j) ∧ f(j)Em.

Hence the set {E |〈ω, E〉 is an ω-model} is .

On the other hand, 〈ω, E〉 codes an ω-model if and only if there is an m ∈ ω such that

(iv) 〈ω, E〉 ⊨ “m is an infinite ordinal”;

(v) for every injection f from ω into {k | kEm}, there is a pair (i, j) such that i < j and 〈ω, E〉 ⊨ f(i)Ef(j), and

(vi) for every order-preserving function f from ω into {k | kEm} and for any k with 〈ω, E〉 ⊨ kEm, there is a j such that 〈ω, E〉 ⊨ kEf(j).

Thus {E |〈ω, E〉 is an ω-model} is also and hence .

Proposition 3.6.4.

(i)The set (ω, ωE, )={(n, nE, E)| nE codes n in } is arithmetical;

(ii)Suppose that =〈ω, E〉 codes an ω-model . Then for any real x ∈ , x is arithmetical in E;

(ii) If m codes ω in and f : ω →{k | ⊨ kEm} is an order-preserving bijection, then every real x ∈ is recursive in f ⊕ E.

Proof. (i) (n, m, E)∈(ω, ωE, ) if and only if there is a finite sequence {kj}j≤n such that

–kn = m ∧⊨(∀k)(¬kEk0);

–for any j < n, ⊨ kjEkj+1 ∧(∀k)(kEkj+1 → kEkj ∨ k = kj), and

–for all j < n, ⊨ kjEm.

Hence (ω, ωE, E) is arithmetical.

(ii) Given x ∈ , let m code x in . Then for any n, n ∈ x if and only if (n, nE, E)∈(ω, ωE, ) and ⊨ nEEm. Thus x is arithmetical in E.

(iii) For x ∈ , let n code x in . Then for any i, i ∈ x if and only if ⊨ f(i)En, so that x ≤T E ⊕ f.

By (iii) of Proposition 3.6.4, if f is recursive, then every real in is recursive in E. If such a recursive f exists, we say that 〈ω, E〉 is a nicely coded ω-model.

Proposition 3.6.5. If 〈ω, E〉 codes an ω-model, then there is a nicely coded ω-model 〈ω, E0〉 ≅ 〈ω, E〉. Moreover, the set {E |〈ω, E〉 is a nicely coded ω-model} is .

Proof. Suppose that 〈ω, E〉 codes an ω-model and m codes ω in 〈ω, E〉. Without loss of generality, we may assume that {k |〈ω, E〉 ⊨ kEm} is infinite. Let f : ω →{k | 〈ω, E〉 ⊨ kEm} be an order-preserving bijection. Let g : ω → ω be any bijection such that g(2n)= f(n) for every n. Now define iE0j if and only if g(i)Eg(j). Then g : 〈ω, E〉 ≅ 〈ω, E0〉. Obviously nE0g−1(m) if and only if n is an even number. Let h(n)= 2n. Then h is recursive and h : ω →{i |(ω, E0) ⊨ iE0g−1(m)} is an order-preserving bijection. Thus 〈ω, E0〉 is a nicely coded ω-model.

We leave the proof of the second part of Proposition 3.6.5 to the reader.

From the above it is harmless to assume that an ω-model 〈ω, E〉 is always nicely coded.

#### 3.6.4 The second least admissible ordinal

An application of the previous results yields

Lemma 3.6.6. is the second least admissible ordinal.

Proof. Let α be the second least admissible ordinal. By Proposition 3.3.12, α ≥ .

Let ={E |〈ω, E〉 nicely codes an ω-model of KP}. By Proposition 3.6.5, is a -set. By Gandy’s Basis Theorem (2.5.3), there is an E ∈ such that . Let 〈M, ∈〉 be the ω-model coded by 〈ω, E〉 and M1 its standard part. By Lemma 3.5.4, 〈M1, ∈〉 ⊨ KP. We claim that β < for any β ∈ M1. Assume this is false. Let m ∈ ω be a real which codes in 〈ω, E〉. Then the set

{(i, j)|(ω, E) ⊨ iEj ∧ jEm}

is an E-recursive well-ordering of order type , contradicting . Thus o(M1) = and hence α = . Hence is the second least admissible ordinal.

By Theorem 3.3.6 and Lemma 3.6.6, we have

Corollary 3.6.7. is admissible.

Theorem 3.6.8. A real x is hyperarithmetic if and only if x ∈

Proof. To prove that every hyperarithmetic real belongs to , it suffices to prove Hn ∈ for any n ∈ . By Proposition 2.1.5, Hn is Turing reducible to some -singleton fn ∈ ωω. So it is sufficient to prove that fn ∈

Since fn is a -singleton, there is a recursive tree Tn ∈ ω<ω such that fn is the unique infinite path in T. Then for every m ∈ ω and σ ∈ ωm \{fn ↾ m}, Tσ ={τ ∈ Tn | τ ≻ σ} is wellfounded. Since is admissible, there is an hσ : Tσ → in such that for any τ1 ≻ τ0 in Tσ, hσ(τ1)< hσ(τ0). Hence there is a βσ ∈ such that hσ ∈ Lβσ. Since ωm \{fn ↾ m}∈ , by Theorem 3.3.2 and the Σ-Collection Theorem (3.1.6), there is a βm < such that βσ < βm for all σ ∈ ωm \{fn ↾ m}. By Theorem 3.1.6 again, there is a β < which is an upper bound of all the βm’s. Then σ ≺ fn if and only if

Thus fn ∈ Lβ+1 ⊂ .

Suppose that x ∈ . Since is admissible, we have . Assume that x is not hyperarithmetic. Define

By Proposition 3.6.5, is a -set. By the Kreisel Basis Theorem (2.5.6), there is an E0 ∈ with and . Let 〈M, ∈〉 be the ω-model coded by 〈ω, E0〉 and let M1 be the standard part of M. Then every real z ∈ M1 is recursive in E0. Hence x ∉ M1. By Proposition 3.5.5, ⊆ M1. Thus x ∉ .

This gives a model-theoretic characterization of the set of hyperarithmetic reals:

Corollary 3.6.9. A real x is hyperarithmetic if and only if it belongs to every ω-model of KP.

Proof. By Theorem 3.6.8, x is hyperarithmetic if and only if x ∈ . By Theorem 3.5.5 and Corollary 3.6.7, x ∈ if and only if x belongs to every ω-model of KP.

#### 3.6.5 The Cantor–Bendixon construction revisited

We now return to the recursion-theoretic proof of Theorem 1.1.10 and calculate the least ordinal γ for which Tγ+1 = Tγ.

Proposition 3.6.10 Suppose T ⊆ ω<ω, is a recursive tree with uncountably many infinite paths. Then there is a Σ1()-function f : → such that for any γ1 < γ2 < , f(γ2)= Tγ2 ⊆ f(γ1)= Tγ1 ⊆ T and is a perfect subtree of T.

Proof. Since T is recursive, we have T ∈ Lω+1. By Theorem 3.1.8, there is a Σ1()-function f : → such that

–f(0)= T;

–for any γ < , f(γ + 1)= Tγ+1 ={σ ∈ Tγ |(∃τ0, τ1 ≻ σ)(τ0, τ1 ∈ Tγ ∧ τ0|τ1)} ⊆ f(γ);

–if γ is a limit ordina, then f(γ)= Tγ = ⋂β<γ Tβ.

First note that |[Tγ]\[Tγ+1]| ≤ ℵ0 for each γ < , and hence [] ≠ . We claim that is a perfect tree. First note that given σ ∈ , there is a τ ≻ σ such that τ ∈ . Otherwise, let gσ(n) be the least ordinal γ < for which σ⌢n ∉ Tγ. Then gσ is a total function and Σ1 in . By the admissibility of (Corollary 3.6.7), there is an ordinal β < so that gσ(n)< β for all n. Then σ ∉ Tβ+1, a contradiction.

Now suppose that σ ∈ is an isolated path, i.e. [σ] ∩ [] contains exactly one path. Let hσ(n) be the least ordinal γ < such that |{τ | τ ∈ Tγ ∧ τ ≻ σ ∧|τ|= |σ|+n}| = 1. Then hσ is a total function and Σ1 in . By Corollary 3.6.7 again, there is an ordinal β < such that hσ(n)< β for all n. Then for any τ0, τ1 ≻ σ, if τ0, τ1 ∈ Tβ, then τ0 and τ1 are compatible. So σ ∉ Tβ+1, a contradiction.

#### 3.6.6 Exercises

Exercise 3.6.1. Complete the proof of Proposition 3.6.5.

Exercise 3.6.2. Relativize and prove the results in § 3.6.4.

Exercise 3.6.3. Prove that there is a recursive tree T with uncountably many infinite paths (as in Proposition 3.6.10) such that for each γ < , Tγ is not a perfect tree.

Exercise 3.6.4. Suppose that R0 and R1 code well-ordering relations of ω and the order type of R0 is not greater than that of R1. Show that there is an order-preserving function f ≤h R0 ⊕ R1 which embeds R0 onto an initial segment of R1.

Exercise 3.6.5. Given a hyperarithmetic real x, show that there exist two recursive well-orderings R0 ≅ R1 of ω such that there is no isomorphism between R0 and R1 recursive in x.

Exercise 3.6.6. Without using Kreisel’s Basis Theorem, give a direct proof of Theorem 3.6.8.

### 3.7 The Spector–Gandy Theorem

#### 3.7.1 First version

Theorem 3.7.1 (Spector[156], Gandy[34]). x ∈ 2ω is if and only if there is a Σ1-formula φ(u) such that n ∈ x ⇔ 〈, ∈〉 ⊨ φ(n).

Proof. Suppose that x ∈ 2ω is . By Proposition 1.1.14, there is a recursive tree T ⊆ ω×ω<ω and a recursive function f such that n ∈ x if and only if Tf(n) ={σ |(f(n), σ)∈ T} is a wellfounded tree. Since T is recursive, we have T ∈ . Given n, we say that g : Tf(n) → γ is order preserving if σ ≻ τ implies g(σ) < g(τ). By Corollary 3.6.7, is admissible. Hence by Theorem 3.1.8, there is an ordinal γ < and an order-preserving function g : Tf(n) → γ.

Let φ(n) be the statement

(∃γ)(∃g)(γ is an ordinal ∧ g is an order-preserving function from Tf(n) into γ),

In other words, n ∈ x ⇒ 〈, ∈〉 ⊨ φ(n). On the other hand, if 〈, ∈〉 ⊨ φ(n), then Tf(n) is wellfounded. Thus n ∈ x.

For the other direction, suppose that there is a Σ1-formula φ(u) such that n ∈ x ⇔ 〈, ∈〉 ⊨ φ(n). Since φ(u) is Σ1, by Proposition 3.5.5, 〈, ∈〉 ⊨ φ(n) if and only if for any E, if 〈ω, E〉 codes an ω-model of KP, then 〈ω, E〉 ⊨ φ(nE) where nE denotes the number in 〈ω, E〉 which codes n. By Proposition 3.6.3, x is .

Notwithstanding the remark in [107] that “the Spector–Gandy Theorem does not have many applications but it is undoubtedly one of the jewels of the effective theory”, it is a major result and has seen important applications in higher recursion theory. For example, the theorem allows one to develop a robust computation theory for the structure 〈, ∈〉, including implementation of the priority method to study the metadegrees of -sets.

A generalization of Theorem 3.7.1 that lifts the result to sets of reals is the following.

Corollary 3.7.2. For any real y, a set A ⊆ 2ω is (y) if and only if there is a Σ1-formula φ(u, v) such that .

It should be pointed out that the statement in the corollary remains valid if one replaces 2ω with ωω in Corollary 3.7.2.

#### 3.7.2 Second version

Let ∗ be as defined in § 2.6. Fix a number i ∈ ∗ \ . Then by the results in the same section, the set is an r.e. set such that is an initial segment of ∗ of order type . By Lemma 2.2.4, there is a recursive function g such that if n ∈ , then .

For any real z and n ∈ ω, let (z)n ={m | 2n ⋅ 3m ∈ z}. Let A(n, z) be an arithmetical predicate defined as follows: There is an m <o* i such that

Roughly speaking, A(n, z) says that there is an m <o* i such that z codes an iteration of Turing jumps along the set {j | j ≤o* m} and . Then for any , (z)n = Hn.

Theorem 3.7.3 (Spector [156], Gandy [34]). x ∈ 2ω is if and only if there is an arithmetical predicate B(n, z) such that n ∈ x ⇔ (∃z ∈ )(B(n, z)).

Proof. By Corollary 2.2.12, if there is an arithmetical predicate B(n, z) such that n ∈ x ⇔ (∃z ∈ )(B(n, z)), then x is .

Suppose that x is . Then there is a recursive function f such that n ∈ x ⇔ f(n)∈ . Let A(n, z) be as defined earlier. If n ∈ x, then f(n)∈ 2f(n). Let m <o* i be in so that |m| > |f(n)|. Let z be a real such that for any j ≤o 2m, (z)j = Hj and (z)j = for the other j’s. Then . Clearly z is hyperarithmetic. Thus n ∈ x implies that there exists a hyperarithmetic real z satisfying A(f(n), z)

Now suppose that z is hyperarithmetic and A(f(n), z). Then there is an m <o* i with properties (1)–(5). We claim that m ∈ . Otherwise, for any k ∈ , Hk ≤T (z)2m, contradicting the fact that z is hyperarithmetic. Thus and so n ∈ x.

Let B(n, z) be A(f(n), z). Then n ∈ x if and only if there is a hyperarithmetic real z such that B(n, z).

We leave it to the reader to prove the following generalization of Theorem 3.7.3 to sets of reals:

Corollary 3.7.4. A ⊆ 2ω is (y) if and only if there is an arithmetical predicate B such that x ∈ A ⇔ (∃z ≤h x ⊕ y)(B(x, z, y)).

Theorem 3.7.3 says that if we consider -sets to be r.e. sets, then hyperarithmetic reals are analogs of finite sets. In particular, there are infinite sets of natural numbers which are “finite”. This is a departure from the classical notion where infinite sets are never “finite”.

As mentioned in § 3.7.1, the Gandy–Spector Theorem presents an effective – hence recursion-theoretic – way to enumerate members of a -set. The enumeration is carried out in through ordinals less than .

The situation is more problematic with -sets of reals. Corollary 3.7.2 says that A set A ⊆ 2ω is if and only if there is a Σ1-formula φ(u) such that x ∈ A ⇔ 〈[x], ∈〉 ⊨ φ(x) (rather than 〈, ∈〉 ⊨ φ(x)). This makes analyzing -sets of reals a more delicate proposition. For each real x, one has to work within [x] to search for a solution to the Σ1-formula φ(u). This lack of uniformity is an issue when one wishes to choose the x “enumerated at the least stage” satisfying φ. In the case of the second version of the Gandy–Spector Theorem (3.7.3), the corresponding procedure for “enumerating” a -set of reals is to “enumerate” the Hx-sets in order to compute awitness z. Here we face a problem similar to that for version one, in that there is no uniform way to execute this procedure. We give below an example to illustrate how such a difficulty may be addressed.

Definition 3.7.5. A norm on a set A ⊆ 2ω is a function φ : A → α for some ordinal α.

Norms are among the most important objects in descriptive set theory. A norm on a set A acts as an “enumerating function” for A.

Proposition 3.7.6 Let A ⊆ 2ω be . There is a norm φ on A, a -relation P(x, y) and a -relation Q(x, y) such that for any y ∈ A,

(∀x)(x ∈ A ∧ φ(x)≤ φ(y)↔(P(x, y)↔ Q(x, y))).

Proof. Since A is , by Corollary 3.7.4 there is an arithmetical predicate B(x, z) such that x ∈ A ⇔ (∃z ≤h x)(B(x, z)). If x ∈ A, choose n ∈ x so that |n|x is minimal and holds for some e. Let φ(x) = |n|x. Define P(x, y) as follows:

(i)

(ii) , and

(3) there exists an isomorphism from {m | m <ox n0} onto an initial segment of {m | m <oγ n1}.

Clause (3) is since the isomorphism (if there is one) must be hyperarithmetic in x ⊕ y.

By relativizing the results in § 2.6, there is a -set {(x, x,*)| x ∈ 2ω}⊆ 2ω × ω so that <x,* is a binary realign on x,* with the following properties:

(i) x ⊆ x,*;

(ii) <ox is the restriction of <ox,* to x;

(iii) for any n, n ∈ x if and only if <ox,* restricted to {m | m <ox,* n} is a well-ordering.

Let Q(x, y) be the formula

Now it is easy to see that if y ∈ A, then (∀x)(x ∈ A ∧ φ(x)≤ φ(y)) if and only if P(x, y), and if and only if Q(x, y).

Proposition 3.7.6 essentially says that if y belongs to A, then the collection of reals enumerated into A “before y is enumerated” is (y).

#### 3.7.3 An application

We apply the Spector–Gandy Theorem to study -sets of reals. For each ordinal α < ω1, let rα be a real coding a well-ordering of ω of order type α. In the next two lemmas, let Rα = if α is not a countable admissible ordinal (since is admissible for any x ⊆ ω).

Lemma 3.7.7. For any α < ω1, the set Rα ={x | = α} is (rα).

Proof. For any n, let |n|rα be the order of n under the ordering rα. Then x ∈ Rα if and only if

(∀n ∈ x)(∃f)(f is an embedding of {m | m <ox n} into rα)∧

(∃g)(∃i ∈ ∗, x)(g is an isomorphic map from rα onto an initial segment of ).

Thus Rα is (rα). Let be a well-ordering of ω of order type α + 1. Then x ∈ Rα if and only if

By Exercise 3.6.4, one may take g in the above expression to be hyperarithmetic in rα ⊕{i | i <ox m} which is in turn hyperarithmetic in rα ⊕ x. Hence Rα is also (rα) and thus (rα).

Lemma 3.7.8. For any α < ω1, the relation Cα(x, y)⇔ y ≤h x ∧ x ∈ Rα is (rα).

Proof. By Corollary 2.2.2 and Lemma 3.7.7, Cα is (rα).

We prove that Cα is (rα). Now y ≤h x if and only if there is an n ∈ x such that , and by the previous lemma the latter holds if and only if there is an n ∈ x,* and an f : {m | m ≤ox,∗ n} → ω such that for all i <ox,∗ j, (f(i), f(j)) ∈ rα. Then y ≤h x is (rα). Thus Cα is (rα).

Lemma 3.7.9. Every -set of reals is the union of ℵ1-many Boral sets.

(ii) Every -set of reals is the union of ℵ1-many Borel sets.

Proof. (i) Suppose that A ⊆ 2ω is . By Corollary 3.7.4, there is an arithmetical predicate A(x, z) such that x ∈ A ⇔ (∃z ≤h x)(A(x, z)). For any α < ω1, let Aα = A∩Rα. Then Aα is (rα). By Lemma 3.7.8, Aα is also (rα). Thus Aα is (rα) and hence Borel.

(ii) Suppose that A ⊆ 2ω is . Then there is a set B ⊆ ωω × 2ω such that x ∈ A if and only if (∃f)B(f, x). For α < ω1, let Aα = A ∩ Rα. By Lemma 3.7.7, Aα is (rα).

By the Gandy Basis Theorem 2.5.3, x ∈ A if and only if (∃f <h x)B(f, x). Since , we have . Relativizing the proof of Corollary 2.4.10 to rα gives x ≤h x ⊕ rα. Thus x ∈ Aα if and only if x ∈ Rα and (∃f ≤h x ⊕ rα)B(f, x). We conclude that Aα is (rα) and hence (rα).

Corollary 3.7.10. (Lusin [86]). Every -set of reals is measurable.

Proof. Following the notations of Lemma 3.7.9, for each n ∈ ω and α < ω1, let

Then Dn, α is (rα). By the proof of Lemma 3.7.8 and Exercise 3.6.4,

and is (rα). Thus Dn, α is Borel. Note that Dn, α ∩ Dn, β = for α ≠ β. Hence for any n, thereexistsan αn < ω1 such that μ(Dn, β)= 0for β ≥ αn. Let αω < ω1 be an upper bound of these αn’s.

Now suppose that A is . Then for any α > αω, x ∈ Aα implies that there exists an n such that x ∈ Dn, αω. In other words, ⋃α> αω Aα ⊆ ⋃n Dn, αω. By the choice of αω, μ(⋃α>αω Aα)= 0. But ⋃α≤αω Aα is a Borel set which is measurable. We conclude that A = ⋃α<ω Aα is measurable.

We will compute the value of αω in Chapter 14.

Theorem 3.7.11 (Sierpinski [135]). Every -set of reals is a union of ω1-many Borel sets.

Proof. Suppose that A ⊆ 2ω is . Then there is a -set B ⊆ ωω such that x ∈ A if and only if (∃f ∈ ωω)B(f, x). By (i) of Lemma 3.7.9, there is an ω1-sequence of Borel sets {Bα}α<ω1 such that ⋃α<ω1 Bα = B. Then Cα ={x |(∃f ∈ ωω)Bα(f, x)} is for each α < ω1. Clearly A = ⋃α<ω1 Cα. By relativizing (ii) of Lemma 3.7.9, each Cα is a union of ω1-many Borel sets. Thus A is a union of ω1-many Borel sets.

Corollary 3.7.12. Every -set of reals of cardinality greater than ℵ1 has a perfect subset.

Proof. By Theorem 3.7.11, every -set A of reals is the union of ℵ1-many Borel sets. If A has cardinality greater than ℵ1, then one of these Borel sets is uncountable and so has a perfect subset.

#### 3.7.4 Exercises

Exercise 3.7.1. The following is another proof of Theorem 2.4.7.

(i)Show that O is Σ1-definable over ;

(ii)show that for any reals x and y, x ≤h y if and only if and hence ≤h y and only if .

Exercise 3.7.2. Prove that there exists a sequence of reals {xn}n<ω such that for each n, xn ≥T xʹn+1.

Exercise 3.7.3. Prove that if {xn}n<ω is a sequence as above, then for each n, xn is not hyperarithmetic.

Exercise 3.7.4. Use the first version of the Spector–Gandy Theorem (3.7.1) to prove Theorem 3.7.11.

Exercise 3.7.5. Prove that if x is a real so that every nonempty set A ⊆ ωω has a member hyperarithmetical in x, then x ≥h .

Exercise 3.7.6. Prove that the set {(x, y)| } is but not .

Exercise 3.7.7. Assume MA + 2ℵ0 >ℵ1 (cf. Definition 6.1.5). Prove that every -set is measurable.