3.7 The Spector–Gandy Theorem – Recursion Theory

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 |〈ω, Ecodes 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 |〈ω, Ecodes 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 =〈ω, Ecodes 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 fE.

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

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

for any j < n, kjEkj+1 ∧(∀k)(kEkj+1kEkjk = kj), and

for all j < n, kjEm.

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

(ii) Given x, let m code x in . Then for any n, nx 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, ix if and only if f(i)En, so that xT Ef.

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ω, Ecodes an ω-model, then there is a nicely coded ω-model 〈ω, E0〉 ≅ 〈ω, E〉. Moreover, the set {E |〈ω, Eis 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) ⊨ iEjjEm}

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 \{fnm}, 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 \{fnm}∈ , by Theorem 3.3.2 and the Σ-Collection Theorem (3.1.6), there is a βm < such that βσ < βm for all σωm \{fnm}. 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 fnLβ+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 zM1 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γ2f(γ1)= Tγ1T and is a perfect subtree of T.

Proof. Since T is recursive, we have TLω+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, τ1Tγτ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, τ1Tβ, 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 fh R0R1 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 R0R1 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 nx ⇔ 〈, ∈〉 ⊨ φ(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 nx 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, nx ⇒ 〈, ∈〉 ⊨ φ(n). On the other hand, if 〈, ∈〉 ⊨ φ(n), then Tf(n) is wellfounded. Thus nx.

For the other direction, suppose that there is a Σ1-formula φ(u) such that nx ⇔ 〈, ∈〉 ⊨ φ(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 ⋅ 3mz}. 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 | jo* 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 nx ⇔ (∃z)(B(n, z)).

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

Suppose that x is . Then there is a recursive function f such that nxf(n)∈ . Let A(n, z) be as defined earlier. If nx, 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 jo 2m, (z)j = Hj and (z)j = for the other j’s. Then . Clearly z is hyperarithmetic. Thus nx 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, HkT (z)2m, contradicting the fact that z is hyperarithmetic. Thus and so nx.

Let B(n, z) be A(f(n), z). Then nx 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 xA ⇔ (∃zh xy)(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 xA ⇔ 〈[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 yA,

(∀x)(xAφ(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 xA ⇔ (∃zh x)(B(x, z)). If xA, choose nx 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 xy.

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) xx,*;

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

(iii) for any n, nx 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 yA, then (∀x)(xAφ(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| be the order of n under the ordering rα. Then xRα if and only if

(∀nx)(∃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 xRα 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)⇔ yh xxRα is (rα).

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

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

Lemma 3.7.9. Every -set of reals is the union of1-many Boral sets.
(ii) Every -set of reals is the union of1-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 xA ⇔ (∃zh x)(A(x, z)). For any α < ω1, let Aα = ARα. 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 xA if and only if (∃f)B(f, x). For α < ω1, let Aα = ARα. By Lemma 3.7.7, Aα is (rα).

By the Gandy Basis Theorem 2.5.3, xA if and only if (∃f <h x)B(f, x). Since , we have . Relativizing the proof of Corollary 2.4.10 to rα gives xh xrα. Thus xAα if and only if xRα and (∃fh xrα)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 α > αω, xAα implies that there exists an n such that xDn, αω. 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 xA 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 than1 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, xh 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, xnT 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 xh .

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

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