1 An introduction to higher recursion theory

1.1 Projective predicates

1.1.1 Recursive and arithmetical predicates

A recursive predicate R on ω is a total recursive function Φ : ω → 2 such that R(n) ⇔ Φ(n) = 1. With a standard coding of ω<ω in ω, one may define recursive predicates on ω<ω. Similarly one may code ωn in ω to obtain recursive n-ary predicates on ω, as well as recursive predicates on (ω<ω)m × ωn. The class of arithmetical predicates on ωω × ω is now defined as follows:

Definition 1.1.1. A predicate R(x, n) on ωω × ω is partial recursive if there is a partial recursive function Φ(σ, n) on ω<ω × ω such that

(i)(∀σ)(∀τ)(∀n)[Φ(σ, n) ↓ ∧ σ τ → (Φ(τ, n) ↓ ∧ Φ(σ, n) = Φ(τ, n))].

(ii)For any x ∈ ωω and n ∈ ω, R(x, n) if and only if (∃m)(Φ(x ↾ m, n) ↓ = 0).

A predicate R(x, n) on ωω × ω is recursive if the partial recursive function Φ above also satisfies the following property:

(iii)(∀x)(∀n)(∃m)(Φ(x ↾ m, n)↓).

Remark 1.1.2. We may similarly define recursive predicates on (ωω)n ×(ω<ω)m × ωk. In general, there is no effective enumeration of recursive predicates on ωω × ω.

The hierarchy of arithmetical predicates is defined by induction on n < ω.

Definition 1.1.3.

(i) = {P | P is a partial recursive predicate}.

(ii)P is if {(x, m)|¬P(x, m)} is .

(iii)P is if there is a -predicate R(x, 〈m, k〉) such that

P(x, m) ⇔ (∃k)R(x, 〈m, k〉).

(iv)P is if it is and .

We say that a predicate P is arithmetical if P ∈ for some n.

It follows from results in classical recursion theory that a predicate P(x, m) is if and only if there is a recursive predicate R(x, m, n) such that P(x, m) ⇔ (∃n)R(x, m, n).

Fix an effective enumeration of partial recursive functions {Φe(σ, n)}e<ω which satisfies property (i) in Definition 1.1.1. For each real x, Φe(x, n) denotes Φe(x ↾ m, n) for the least m such that Φe(x ↾ m, n)↓ at stage m. If no such m exists, then Φe(x, n) is undefined. We say that Φe(x, n) is an x-partial recursive function. Hence there is a uniform enumeration of partial recursive functions {Φe(x, n)}e<ω with oracle x. In other words, the predicate P(e, x, n, m) ⇔ Φe(x, n) ↓ = m is .

There is an obvious generalization of the above to allow parameters in ωω, yielding the class of -predicates relative to a real or a finite set of reals.

Definition 1.1.4. Let a ∈ ωω.

(i)A predicate Pa(y, m) is (a) if there is a partial recursive predicate R(a, y, m) such that for all y and m, Pa(y, m) ⇔ R(a, y, m).

(ii)Pa(y, m) is (a) if ¬Pa(y, m) is (a).

(iii)Pa(y, m) is (a) if there is a (a)-predicate Ra(y, m, k) such that Pa(y, m) if (∃k)Ra(y, m, k).

(iv)Pa(y, m) is (a) if it is (a) and (a).

Given a collection of predicates Γ, we say that a set a ⊆ ω (resp. P∗ ⊆ ωω) is a Γ-set, or a member of Γ, if m ∈ a ⇔ P(, m) (resp. x ∈ P∗ ⇔ P(x, 0)) for some predicate P(x, m) ∈ Γ. For each n < ω, let , and denote respectively the class of , and -predicates. The following lemma is well known. A proof may be found in [53].

Lemma 1.1.5.

(i)Let n < ω. There is a -set U ⊆ ωω × ωω such that for each P ∈ , P = {x | (x, y) ∈ U} for some y.

(ii)For each n, ⊂ ⊂ and ⊂ ⊂ .

In classical recursion theory, a set a ⊆ ω is if and only if a is (n). However, it is not generally true for sets of reals. For example, the set {(ω)} is but is not (x) (as a singleton) for any x ∈ ωω (see Exercise 1.1.5).

1.1.2 Analytical predicates

Definition 1.1.6.

(i)A predicate P(x, m) is if it is ;

(ii)A predicate P(x, m) is if ¬P(x, m) is .

(iii)A predicate P(x, m) is if there is a -predicate R(x, y, m) ⊆ ωω × ωω × ω such that P(x, m) if and only if (∃y)R(x, y, m).

(iv)A predicate P(x, m) is if it is both and .

(v)A predicate P is analytical if P ∈ for some n.

As in Lemma 1.1.5, we have the following facts which are straightforward to verify.

Lemma 1.1.7.

(i)Let n < ω. There is a -set U ⊆ ωω × ωω such that for each P ∈ , P = {x | (x, y) ∈ U} for some y.

(ii)For each n, ⊂ ⊂ and ⊂ ⊂ .

(iii)Every arithmetical set is .

More basic facts about analytical sets may be found in Jech [53]. For σ ∈ ω<ω, let [σ] denote the set of functions in ωω which extend σ. We say that a function f : ωω → ωω is in the class Γ if {(x, σ) ∈ ωω × ω<ω | x ∈ f−1([σ])} ∈ Γ. Note that every -function is continuous.

The following proposition is immediate.

Proposition 1.1.8.

(i)If f : ω → ω is total, then f ∈ ⇔ f ∈ .

(ii)A function f : ωω → ωω is if and only if its graph Gf = {(x, y)| f(x) = y} is ; if f is then Gf is ; if f is then Gf is .

(iii)If f is total, then Gf is if and only if f is .

(iv)If f : ωω → ωω is total, then f ∈ ⇔ f ∈ ⇔ f ∈ .

Proof. (i) is obvious. For (ii), note that (x, y) ∈ Gf if and only if (∀σ)(y ≻ σ → x ∈ f−1([σ])). Hence if f is (resp. ) then Gf is (resp. ). Moreover, if Gf is , then x ∈ f−1([σ]) if and only if (∃y)(y ≻ σ ∧(x, y) ∈ Gf ). So f is if and only if its graph Gf = {(x, y)| f(x) = y} is .

(iii). If f is total, then x ∈ f−1([σ]) if and only if (∀τ)(τ | σ → x ∉ f−1([τ])).

(iv). If f is total, then x ∈ f−1([σ]) if and only if . So if Gf is , then f is . By (iii), f is .

Given σi and in ω<ω, where i ≤ n, we say that is a substring of (σ0,…, σn) if for each i. A tree T ⊆ ω<ω × … × ω<ω (n-fold product) is assumed to have the property that if (σ0,…, σn) ∈ T then all of its substrings are in T. For our purpose, all trees grow downwards with root at the top. The following tree representation theorem provides a useful picture of -sets of reals.

Proposition 1.1.9. A predicate P(x, m) is if and only if there is a recursive sequence of recursive trees {Tm}m<ω such that Tm ⊆ ω<ω × ω<ω and

P(x, m) ⇔ (∃y)(∀n)((x ↾ n, y ↾ n) ∈ Tm).

Proof. A predicate P(x, m) is if and only if there is a partial recursive function Φ(σ, τ, m) which satisfies properties (i)–(iii) of Definition 1.1.1, so that P(x, m) ⇔ (∃y)(∀k)(Φ(x ↾ k, y ↾ k, m)↓ → Φ(x ↾ k, y ↾ k, m) ≠ 0). At stage max{|σ|, |τ|}, put (σ, τ) in Tm if and only if Φ(σ, τ, m)↑ or Φ(σ, τ, m) ≠ 0. We leave it to the reader to verify that {Tm}m∈ω satisfies the requirement.

1.1.3 -sets of reals

A set of reals is if there is a -predicate P (possibly with a number parameter m) such that P(x, m) holds if and only if x belongs to the set. A set of reals is if its complement is . Both and -sets of reals play significant roles in higher recursion theory. In this section, we introduce some basic facts about these sets.

Recall that P ⊆ ωω is perfect if it is a closed set with no isolated point. The next theorem shows that every uncountable -set of reals has what may be described as the perfect set property.

Theorem 1.1.10 (Suslin [162]). If P is and uncountable, then it contains a perfect subset.

Proof. Suppose P(x) is (for simplicity assume that there is no number variable defining P). We give two proofs of Theorem 1.1.10. One is set-theoretic while the other is recursion-theoretic.

Set-theoretic proof. By Proposition 1.1.9, there is a recursive tree T ⊆ ω<ω × ω<ω such that x ∈ P if and only if (∃y)(∀n)(x ↾ n, y ↾ n) ∈ T. Let T ʹ be a subtree of T such that

(σ, τ) ∈ T ʹ ⇔|{x ≻ σ | (∃y ≻ τ)(∀n)(x ↾ n, y ↾ n) ∈ T}| > ℵ0.

Define

Q = {x | (∃y)(∀n)(x ↾ n, y ↾ n) ∈ T′}.

Since P is uncountable, Q is not empty. Obviously Q ⊆ P. Note that if (σ, τ) ∈ T′ then there exist k and k′ such that (σ⌢k, τ⌢k′) ∈ T′. We show that Q contains a perfect set. By induction on n, build a perfect tree S0 and a tree S1 with the following properties:

(i) S1 ⊆ T′;

(ii) let [S0] denote the set of infinite paths in S0. Then [S0] is contained in {x | (∃y)(∀n)(x ↾ n, y ↾ n) ∈ S1};

(iii) (∀(σ, τ) ∈ S1)(|{x ≻ σ | (∃y ≻ τ)(∀n)((x ↾ n, y ↾ n) ∈ T)}| > ℵ0).

We begin with setting S0 and S1 to be empty at level 0. Suppose we are at level n + 1. Let σ ∈ S0 be defined at level n with |σ| = n. By induction, there is a τ such that (σ, τ) ∈ S1 was defined at level n and Qσ,τ = {x ≻ σ | (∃y ≻ τ)(∀n)((x ↾ n, y ↾ n) ∈ T)} is uncountable.

Claim. There exist incompatible extensions σ0, σ1 of σ such that Qσ0,τ and Qσ1,τ are both uncountable.

If the Claim is false, then there is a unique x ≻ σ such that if σ′ ≻ σ is incompatible with x, then Qσ′, τ is countable. But this would imply that is countable, which is a contradiction.

Fix (σ0, σ1) as in the Claim. Then there exist τ0, τ1 ≻ τ such that |{x ≻ σi | (∃y ≻ τi)(∀n)((x ↾ n, y ↾ n) ∈ T)}| > ℵ0 for i = 0, 1. Put σ0 and σ1 into S0 and (σi, τi), for i = 0, 1, into S1. This procedure is carried out for every σ ∈ S0.Clearly S0 is a perfect tree and for each x ∈ [S0] there is a y such that (∀n)(x ↾ n, y ↾ n) ∈ S1. Since S1 ⊆ T′ ⊆ T, [S0] ⊆ Q ⊆ P.

Recursion-theoretic proof. As above, we have a recursive tree T ⊆ ω<ω × ω<ω such that x ∈ P if and only if (∃y)(∀n)(x ↾ n, y ↾ n) ∈ T. We perform a Cantor–Bendixon style operation on the tree as follows:

At stage 0, let T0 = T.

At limit stage α, let Tα = ⋂β<α Tβ.

At successor stage α + 1, let

Tα+1 = {(σ, τ) ∈ Tα | (∃σ0 ≻ σ)(∃τ0 ≻ τ)(∃σ1 ≻ σ)(∃τ1 ≻ τ)((σ0, τ0) ∈ Tα∧ (σ1, τ1) ∈ Tα ∧ σ0|σ1)}.

Observe that Tα ⊆ Tβ for all α ≥ β. Moreover, for any successor ordinal α + 1, if Tα+1 ≠ Tα, then there is a (σα, τα) ∈ Tα Tα+1. Note that (σα, τα) ≠ (σβ, τβ) for any α ≠ β if these are defined. Since the set ω<ω × ω<ω is countable, there is a least countable ordinal γ such that (σγ, τγ) does not exist. Then Tγ = Tγ+1 and so Tγ = Tα for any α ≥ γ. By replacing T′ in the set-theoretic proof above with Tγ, we conclude that P contains a perfect subset.

Remark 1.1.11.

(i)The proofs above raise two interesting questions. First, what is the complexity of the perfect subset obtained? Since the statement, “P is uncountable” is not second-order definable in arithmetic, the perfect subset defined is generally neither nor . However, we will show later by a more powerful recursion-theoretic argument that its complexity can be controlled (see Exercise 1.5.5). Second, what is the least ordinal γ for which Tγ = Tγ+1 ? We will give a calculation of this ordinal later (see Proposition 3.6.10).

(ii)In general, not every uncountable set has the perfect set property. In fact, “-ness” is the best possible since it is not provable in ZFC that every -set has the perfect set property (see Corollary 4.3.6).

Proposition 1.1.12. Suppose {Pi}i<ω is a sequence of sets of reals such that for any nonempty -set A and i < ω, A ∩ Pi contains a nonempty -set. Let P be and nonempty. Then .

Proof. By hypothesis, there is a nonempty -set F0 ⊆ P ∩ P0. By Proposition 1.1.9, there is a recursive tree T ⊆ ω<ω × ω<ω such that x ∈ F0 ⇔ (∃y)(∀n)((x ↾ n, y ↾ n) ∈ T). Fix such a pair (x, y) so that (∀n)(x ↾ n, y ↾ n) ∈ T. Define σ0 = x ↾ 1 and τ0 = y ↾ 1. Note that G0 = {x ≻ σ0 | (∃y ≻ τ0)(∀n)(x ↾ n, y ↾ n) ∈ T)} is a nonempty -set. Assume by induction that for all i′ ≤ i, a pair (σi′, τi′) ∈ T and a nonempty -set Gi′ ⊆ Pi′ are defined such that

Since Gi is , there is a nonempty -set Fi+1 ⊆ Pi+1 ∩ Gi. Furthermore, by (3) every x ∈ Fi+1 extends σi and there is a y ≻ τi such that for all n, (x ↾ n, y ↾ n) ∈ T. Fix such a pair (x, y). Define σi+1 = x ↾(|σi|+ 1) and τi+1 = y ↾(|τi|+ 1). Let

Gi+1 = {x ∈ Fi+1 | x ≻ σi+1 ∧(∃y ≻ τi+1)(∀n)((x ↾ n, y ↾ n) ∈ T)}.

Then Gi+1 is a nonempty -subset of Fi+1 and hence of Pi+1. Let x(i) = m if and only if σi+1(i) = m and y(i) = m if and only if τi+1(i) = m. Then for all i, x ∈ Gi and for all n, (x ↾ n, y ↾ n) ∈ T. Hence x ∈ P ∩ ⋂i<ω Pi.

As a consequence of Proposition 1.1.12, we may define the Gandy topology as follows.

Definition 1.1.13. The Gandy topology on ωω is the topology generated by taking all -sets as basic open sets.

Proposition 1.1.12 implies that the Gandy topology satisfies the Baire category theorem: The intersection of a countable collection of dense open sets is dense.

1.1.4 -sets of reals

By Proposition 1.1.9, we have the following:

Proposition 1.1.14. A predicate P(x, m) is if and only if there is a recursive sequence of recursive trees Tm ⊆ ω<ω × ω<ω such that P(x, m) ⇔ (∀y)(∃n)((x ↾ n, y ↾ n) ∉ Tm).

For each real x, define a binary relation ≤x on ω such that m ≤x n if and only if x(〈m, n〉) = 1. Define

WF1 = {x ∈ ωω |≤x is a wellfounded relation}.

Then x ∈ WF1 if and only if

so that WF1 is a -set of reals. Fix a standard effective enumeration {σn}n<ω of ω<ω. We say that x codes a tree relation if

Now let P be a -set of reals and let T be a recursive tree such that x ∈ P ⇔ (∀y)(∃n)((x ↾ n, y ↾ n) ∉ T). Define Tx = {σ | (x ↾|σ|, σ) ∈ T}. Then x ∈ P if and only if Tx is wellfounded. Define the Kleene–Brouwer ordering <KB on strings so that for any σ, τ ∈ ω<ω, σ <KB τ if and only if

In other words, σ <KB τ whenever either σ extends τ or σ is “to the left” of τ. Then for each x, x codes a wellfounded tree if and only if x codes a well-ordering under <KB.

Let T ⊆ ω<ω × ω<ω be a recursive tree which witnesses P being . Thus x ∈ P if and only if (∀y)(∃n)(x ↾ n, y ↾ n) ∉ T. Define f(x) = z if and only if z is the unique real coding the tree Tx. Obviously f is a well-defined recursive function. Furthermore, P(x) if and only if f(x) ∈ WF1.

Define

WO1 = {x | x codes a well-ordering}.

Then x ∈ WO1 if and only if x ∈ WF1 ∧(∀n)(∀m)(n ≤x m ∨ m ≤x n). Hence WO1 is . Then for each -set P, there is a recursive function f such that x ∈ P if and only if f(x) ∈ WO1.

Let {Re}e<ω be an effective enumeration of recursively enumerable (r.e.) binary relations. Then the set

WF0 = {e | Re is wellfounded}

is . Let x ⊆ ω be a -set and T ⊆ ω<ω × ω be a recursive tree such that n ∈ x if and only if (∀y)(∃m)(y ↾ m, n) ∉ T. Clearly there is a recursive function f such that for any n, Tn = {σ | (σ, n) ∈ T} = Rf(n). Then n ∈ x if and only if Rf(n) is a wellfounded binary relation. In other words, x is many-one reducible to WF0. By the same argument above, every -set of numbers is many-one reducible to the -set WO0 = {e | Re is a well-ordering}.

Note that the ordinal height of WF1 may be as high as ω1. An interesting question is the ordinal height of WF0. In other words, what is the least ordinal which is not the ordinal of a wellfounded recursive tree? We shall see that this ordinal, denoted , is a countable ordinal.

The following proposition provides an interesting connection between -sets of reals and -subsets of ω.

Proposition 1.1.15 (Spector [153]). Suppose P is a -set of reals. Then

(i)⋂x∈P x is a -set of integers.

(ii)If P has a unique element x, then x is .

Proof. For (i): n ∈ ⋂x∈P x ⇔ (∀x)(P(x) → n ∈ x).

For (ii): n ∈ x ⇔ (∀y)(P(y) → n ∈ y) ↔ (∃y)(P(y) ∧ n ∈ y).

Proposition 1.1.15 is very useful. First, (i) says that one obtains a -set by taking the intersection of a -condition. Second, (ii) provides a link between sets of numbers and sets of reals. The unique real in (ii) is called a -singleton. By (ii), each -singleton is . As we will see (cf. Proposition 1.2.5), this is the best possible. In general, the link between sets of numbers and sets of reals in terms of singleton sets is weak. For example, it will be shown that a -singleton may itself have a definition much more complex than (see also Exercise 1.1.5).

1.1.5 Relativization

As in classical recursion theory, all the results above may be relativized to a real x. We use boldface symbols with tilde and to denote the corresponding sets (of numbers or reals) relativized to a real. A set is projective if it belongs to for some n.

1.1.6 Exercises

Exercise 1.1.1. Prove that a set P ⊆ 2ω is if and only if it is defined by a recursive predicate.

Exercise 1.1.2. Prove that there is a -total function which is not .

Exercise 1.1.3. Prove that every closed uncountable set P ⊆ ωω can be decomposed into the union of a countable set and a perfect set.

Exercise 1.1.4. Prove that every uncountable set P ⊆ ωω can be decomposed into the union of a countable set and a set without isolated members.

Exercise 1.1.5. Prove that (ω) ∈ 2ω is a -singleton but not a (x)-singleton for any .

1.2 Ordinal notations

A key goal in descriptive set theory is to investigate properties of real numbers and sets of real numbers within the system ZFC. However, many statements about complexity classes above the -level are independent of ZFC. Hence it is natural to study in greater depth properties of -sets. Higher recursion theory provides an ideal platform as well as powerful tools for this purpose. In this section, we introduce the notion of a recursive ordinal and an ordinal notation which is at the heart of analysis of -sets. The recursive ordinals allow one to carry out effective transfinite induction over the ordinal similar to what is done over ω1 for transfinite induction.

1.2.1 Kleene’s

Let 〈, 〉 : ω × ω → ω be a recursive bijection. Define an arithmetical set P ⊆ 2ω such that x ∈ P if and only if x satisfies the following conditions:

(i)〈1, 2〉 ∈ x;

(ii)(∀m)(∀n)(〈m, n〉 ∈ x → 〈n, 2n〉 ∈ x);

(iii)(∀e)((∀n)Φe(n)↓∧(∀n)〈Φe(n), Φe(n + 1)〉 ∈ x) → (∀n)(〈Φe(n), 3 ⋅ 5e〉 ∈ x));

(iv)(∀n)(∀m)(∀k)(〈n, m〉 ∈ x ∧〈m, k〉 ∈ x → 〈n, k〉 ∈ x).

Thus (i) implies that x is nonempty; (ii) says that x is “closed under successor”, and (iii) that it is “closed under limit”; (iv) asserts that x defines a transitive relation. We introduce the following notations.

Definition 1.2.1. <o= ⋂x∈P x.

= {n | (∃m)(n <o m)}.

By Proposition 1.1.15, <o is a -relation and is . We define a set a by induction: Stage 0. Put 〈1, 2〉 into a0.

Stage β + 1. Put 〈n, 2n〉 and 〈m, 2n〉 into aβ+1 if 〈m, n〉 ∈ aβ at stage β.

Stage λ, for λ a limit ordinal. For each e such that Φe is total and (∀n)(∃β < λ)(〈Φe(n), Φe(n+1)〉 ∈ aβ), put 〈Φe(n), 3⋅5e〉 into aλ for each n. Furthermore, if 〈m, Φe(n)〉 ∈ aβ for some β < λ, then 〈m, 3 ⋅ 5e〉 ∈ aλ.

Let a = ⋃β aβ.

It is straightforward to verify that a ∈ P and for each x ∈ P, a ⊆ x. Hence a = <o.

Define a function such that |1|=0 and |n| is the least ordinal β for which there is a number m with 〈m, n〉 ∈ aβ. If n ∈ , then n is said to be a notation for the ordinal |n|. An ordinal β is constructive if β =|n| for some n ∈ . Obviously m <o n implies |m| < |n|. Hence <o is a wellfounded partial ordering.

Definition 1.2.2. = the least ordinal α greater than |n| for every n ∈ .

By induction on ordinals β < , it is easy to see that for each is a linear ordering under <o.

Remark 1.2.3.

(i)A path x ⊆ is a set such that

An interesting question is whether every path can be extended to one whose ordinal height is . Such a path is necessary for carrying out effective transfinite induction. However, this is in general not true. Note that there are many possible choices of notations at a limit stage β below . If every path up to β were extendible to one of ordinal height , then there would be 2ℵ0 many sets of notations. Hence to obtain a path through <o, one must choose the notations judiciously. We will show that there exists a “well-behaved” -path through <o.

(ii)It is not difficult to see that the set of constructive ordinals forms an initial segment, and hence is equal to .