1.2.2 Relativized

As in § 1.2.1, one may relativize the notion of ordinal notations to any real x ∈ ωω. Let {Φe(x, n)}e<ω be an effective enumeration of partial recursive functions with oracle x (cf. § 1.1.1). Define an arithmetical set P ⊆ ωω × 2ω such that (x, y) ∈ P if and only if y satisfies the following conditions:

(i)〈1, 2〉 ∈ y;

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

(iii)(∀e)((Φe(x, ⋅) is total ∧(∀n)〈Φe(x, n), Φe(x, n + 1)〉 ∈ y) → (∀n)(〈Φe(x, n), 3 ⋅ 5e〉 ∈ y)), and

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

Definition 1.2.4. .

.

One may also let relativized . Then ax = <ox and the function is a well-defined rank function so that |1|x=0 and |n|x is the least ordinal β for which there is a number m with .

Note that there is a subtle difference between and : An enumeration of oracle functionals is used to define . Hence the set of indices used in the definition of may be different from that of , resulting in possibly different notations at limit stage. However, such a difference does not affect the overall properties of . Indeed, one may redefine as if desired.

By the relativized version of Proposition 1.1.15, both <ox and are (x). The following proposition is immediate.

Proposition 1.2.5.

(i)The sets {(n, x)| n ∈ } and {(〈m, n〉, x)| m <ox n} are .

(ii)The sets {(x, y)| y =<0x} and {(x, y)| y = } are .

Proof. Let P be the set of reals defined before Definition 1.2.4. For (i), n ∈ if and only if (∃m)〈n, m〉 ∈<ox if and only if (∃m)(∀y)((x, y) ∈ P → 〈n, m〉 ∈ y).

For (ii), note that y = <ox if and only if (x, y) ∈ P and (∀z)((x, z) ∈ P → (∀n)(n ∈ y → n ∈ z)) which is . We leave the other part of (ii) as an exercise.

Proposition 1.2.5 has some interesting consequences. Consider for example the set O = {}. Then x ∈ O if and only if . Hence O is a -singleton whose unique member is also .

As in § 1.2.1, one may define the notion of an x-constructive ordinal and denote the least non-x-constructive ordinal as . Note that at limit stage, different oracle sets x may use different indices e for the notation. Hence may be different for different x’s. Moreover, for x’s with “sufficient computational power”, one may have > . We will present a characterization of this property in due course.

1.2.3 Exercise

Exercise 1.2.1. Complete the proof of Proposition 1.2.5.

1.3 Effective transfinite induction

1.3.1 Recursion theorem

The motivation for introducing recursive ordinals is to perform effective transfinite induction. We make it precise in this section, by first recalling the following theorem famously known as the Recursion Theorem (also called the Kleene Fixed Point Theorem).

Theorem 1.3.1 (Kleene). Suppose f : ω → ω is recursive. Then Φf(e) = Φe for some e.

Proof. By the s-m-n Theorem, there is a recursive function g such that Φg(e) = ΦΦe(e) for each e. Let i be the index of the recursive function f ∘ g. Then Φf(g(i)) = ΦΦi(i) = Φg(i).

The Recursion Theorem is a powerful tool in the study of effective computability in classical recursion theory. In higher recursion theory, it is used for effective transfinite induction. The following proposition is the first illustration of such an application.

Proposition 1.3.2 (Sacks [123]). Let <R be an ordering relation on ω with a minimal element. Suppose f is a recursive function such that for all e ∈ ω:

(i)For each n in the field of <R, Φe(n) is defined whenever Φf(e)(m) is defined for all m <R n;

(ii)Φf(e) is defined on every minimal element of <R.

Then there is an index i such that Φi = Φf(i) and Φi is defined on every wellfounded initial segment of R.

Proof. By Theorem 1.3.1, there is an i such that Φi = Φf(i). By (i), if n is an <R-minimal element, then Φi(n) is defined. By an easy induction and an application of (ii), Φi is defined on every wellfounded initial segment of R.

In particular, if R is wellfounded then Φi is defined on the field of R. Note that no assumption is made on the complexity of R in Proposition 1.3.2. As long as the recursive function f exists, we may find such an index i. In general, some nice properties concerning R are required to guarantee the existence of f.

Intuitively, Φf(e) is a “one-step effective induction” operator over Φe. For effective transfinite induction, one needs the assumption that Φe itself is produced by f through another function Φe′, i.e. Φe = Φf(e′). The Recursion Theorem says that this is possible. We shall see many applications of Proposition 1.3.2 to effective transfinite induction. In this chapter we give detailed verifications for some of these. In subsequent chapters, such details will be suppressed and left to the reader.

1.3.2 Operators on ordinal notations

We now define an operator +o on . In addition to requiring it to be closed in (i.e. m ∈ and n ∈ implies m +o n ∈ ), we also require |m| + |n| = |m +o n|.

Let g be a a recursive function such that

Φg(e,m,n)(k) = Φe(m, Φn(k))

for all e, k, m, n. Intuitively, g is a function to be used to handle induction at limit stage.

By the s-m-n Theorem, there is a recursive function h such that

By the Recursion Theorem, there is a c such that Φh(c) = Φc. Define

m +o n = Φc(m, n).

It is straightforward to verify that

Note that

Φg(c,m,k)(n) = Φc(m, Φk(n)) = m +o Φk(n)

for all n. Obviously +o is a recursive function on ω × ω. The following is proved by induction on <o.

Proposition 1.3.3. The function +o satisfies the following properties: For all m, n,

An interesting application of effective transfinite induction is the following basic result.

Theorem 1.3.4 (Kleene [71]). There are two recursive functions f and g such that for all n ∈ ,

(i)Wf(n) = {m | m <o n},

(ii)Wg(n) = {〈i, j〉| i <o j <o n}.

Proof. (i) By the s-m-n Theorem, there are two recursive functions p, q such that

Fix e0 such that We0 = . Define a recursive function h as follows:

By the Recursion Theorem, there is a constant c such that Φh(c) = Φc. Set f = Φc. Then

Obviously f is total since both p and q are total. Then

An easy induction shows that Wf(n) = {m | m <o n} for each n ∈ .

(ii) By the s-m-n Theorem, there are two functions p and q such that

where f was defined in (i). Fix e0 so that We0 = . Let

By the Recursion Theorem, there is a constant c such that Φh(c) = Φc. Set g = Φc. Hence

Note that g is total since both p and q are total. Then

An easy induction shows that Wg(n) = {〈i, j〉| i <o j <o n} for n ∈ .

Theorem 1.3.4 allows one to carry out transfinite induction uniformly for e ∈ . Here we give two applications of Proposition 1.3.3.

Lemma 1.3.5. There is a recursive function g such that for all e:

(i)g(e) ∈ ⇔ We ⊆ .

(ii)g(e) ∈ ⇔|n| < |g(e)| for every n ∈ We.

Proof. By the s-m-n Theorem, there is a recursive function r such that Φr(e)(0) = 1 and the range of Φr(e) is (We {0}) ∪ {1}. By the s-m-n Theorem again, there is a recursive function s such that Φs(e)(0) = 1 and (∀n)(Φs(e)(n + 1) = Φs(e)(n)+o 2Φr(e)(n+1)). Define

g(e) = 3 ⋅ 5s(e).

Note that if We ⊆ , then g(e) ∈ by Proposition 1.3.3. If g(e) ∈ , then Φs(e)(n) ∈ for each n. Hence We ⊆ by Proposition 1.3.3.

Assume g(e) ∈ and n ∈ We. Then n <o Φs(e)(m)+o 2n = Φs(e)(m+1) <o 3⋅5s(e) = g(e) where m is the least number such that Φr(e)(m + 1) = n.

As a consequence of the proof of Lemma 1.3.5, we have

Corollary 1.3.6. There is a recursive function g such that for all e, if We ⊆ and <o on We is linear, then g(e) ∈ and (∀n)(n ∈ We → n <o g(e)).

Corollary 1.3.6 may be viewed as a -boundedness principle, i.e. there is an effective way to find an upper bound for any r.e. subset of . Lemma 1.3.5 will be significantly strengthened in Theorem 1.5.5.

1.4 Recursive ordinals

What are the possible order types of a recursive well-ordering? What is the connection between a recursive well-ordering and a constructive ordinal? We answer these questions in this section.

Definition 1.4.1. An ordinal β is recursive if there is a recursive well-ordering R whose order type is β.

Lemma 1.4.2. Let {Re}e<ω be an effective list of partial recursive binary relations. There exists a recursive function f such that for all e,

(i)Re is wellfounded if and only if f(e) ∈ .

(ii)If Re is wellfounded, then |Re| ≤ |f(e)|, where |Re| is the height of Re.

Proof. By the s-m-n Theorem, there is a recursive function h such that

Rh(e,k)(m, n) ⇔ Re(m, n) ∧ Re(m, k) ∧ Re(n, k)

for all e, k, m and n. Rh(e,k) is the initial segment of Re preceding k. The idea is to define a one-one, order-preserving map from the field of Re into . Fix the recursive function g in Lemma 1.3.5. If k is a minimal element of Re, then k is mapped to an element in determined by applying Wh(e,k) = in Lemma 1.3.5. Otherwise, by induction Rh(e,k) is mapped to an r.e. set W ⊂ with index e′. By Lemma 1.3.5, g(e′) ∈ and |n| < g(e′) for all n ∈ W. Hence we may define f(k) = g(e′).

We now turn to the formal proof. First of all, there is a recursive function p such that

Hence there is a recursive function q such that Φq(i)(e) = g(p(i, e)). By the Recursion Theorem, there is a fixed point c such that Φq(c) = Φc. Define

f(e) = Φc(e)

and

p(e) = p(c, e).

Then

Note that f(e) = Φc(e) = Φq(c)(e) = g(p(c, e)) = g(p(e)).

Now suppose Re is wellfounded. If Re is empty, then by Lemma 1.3.5, and f(e) ∈ . Assume for all wellfounded relations Re with |Re| < α, (i) and (ii) hold. Fix a wellfounded relation Re with |Re| = α. Then for each k in the field of Re, |Rh(e,k)| < α. Hence Wp(h(e,k)) ⊂ and f(h(e, k)) ∈ . Thus Wp(e) = {f(h(e, k))| k ∈ ω} ⊂ . By Lemma 1.3.5, f(e) = g(p(e)) ∈ and |f(e)| > |n| for all n ∈ Wp(e). Thus |f(e)| ≥ |Re|.

Suppose f(e) ∈ . By Lemma 1.3.5, Wp(e) ⊂ and |f(e)| > |f(h(e, n))| for all n. By induction on <o, Rh(e,n) is wellfounded for all n. Hence

is wellfounded.

We leave the proof of the next lemma to the reader (Exercise 1.5.1):

Lemma 1.4.3. Every partial recursive well-ordering R is isomorphic to a recursive well-ordering.

The main result of this section states:

Theorem 1.4.4 (Kleene [71], Markwald [89]). An ordinal is recursive if and only if it is constructive.

Proof. Suppose R is a recursive well-ordering with |R| = β. By Lemma 1.4.2, there is a constructive ordinal γ ≥ β. Hence β is constructive. Conversely, if β is constructive, then by Theorem 1.3.4, there is a partial recursive well-ordering R with |R| = β. By Lemma 1.4.3, β is recursive.

1.4.1 Exercise

Exercise 1.4.1. Prove that there is a set x ⊆ restricted to which <o is a well-ordering of order type ω2, and a partial recursive function p : ω2 → ω such that

(i)For any n ∈ x, the function pn such that pn(i) = p(n, i) is total;

(ii)for any n <o m ∈ x, (∃i)(∀j > i)(pn(j) < pm(j)), and

(iii)for any recursive function f, there exists an n ∈ x such that (∃i)(∀j > i)(f(j) < pn(j)).

1.5 -completeness and -boundedness

1.5.1 -completeness

Theorem 1.5.1. is -complete. Hence is not .

Proof. By Lemma 1.4.2, WF0 is many-one reducible to . As discussed in § 1.1.4, WF0 is -complete, hence as well.

We now consider sets of reals. Suppose P(x, n) is . By relativizing Theorem 1.5.1, there is a recursive function fP such that P(x, n) ⇔ fP(n) ∈ for all n and x. In particular, a -predicate Q(x) is P(x, 0) for some -predicate P. Hence Q(x) if and only if fQ(0) ∈ for some recursive function fQ. It follows that the set C = {(x, n)| n ∈ } is -universal. In other words, for each -set Q, there is a number n such that Q = {x | (n, x) ∈ C}. It is not difficult to see that C is not . We may also code C into a subset of 2ω by defining D = {0n1⌢x | n ∈ }. Then D is a -complete set.

1.5.2 -boundedness

The next corollary is known as the -bounding principle. We will see a number of applications of this principle later.

Corollary 1.5.2 (Spector [153]). Suppose x ⊆ x ⊆ . Then there exists on n ⊆ such that |m| ≤ |n| for all m ∈ x.

Proof. Otherwise, for each β < there is an element n ∈ x with |n| > β.

Since is , there is a recursive function f such that n ∈ implies f(n) ∈ WF0. Then n ∈ if and only if

(∃m)(m ∈ x ∧(∃h ∈ ωω)(∀i)(∀j)(Rf(n)(i, j) → 〈h(i), h(j)〉 ∈ Wg(m))),

where g is as defined in Theorem 1.3.4. So is , a contradiction.

We now turn to Theorem 1.5.5. This may be viewed as an effective version of Corollary 1.5.2.

Lemma 1.5.3. There is a recursive function f such that n ∈ ⇔ f(n) ∈ WF0∧|n| < |Rf(n)|.

Proof. Since is , there is a recursive function g such that

n ∈ ⇔ g(n) ∈ WF0.

By Theorem 1.3.4, there is a function h such that n ∈ implies Rh(n) = {(i, j)| 〈i, j〉 ∈ Wk(n)}, h(n) ∈ WF0 and |n| = |Rh(n)|, where k(n) is the second function in Theorem 1.3.4. Define a recursive function s such that Rs(m,n) =

Then

So n ∈ ⇔ (g(n) ∈ WF0 ∧ h(n) ∈ WF0) ⇔ s(g(n), h(n)) ∈ WF0 and |n| ≤ |Rs(g(n),h(n))|. Now let f(n) = s(g(n), h(n)).

Given two binary r.e. relations Ri, Rj on ω, define a recursive function t such that Rt(i,j) = Ri ⊗ Rj where

Ri ⊗ Rj = {(〈n1, m1〉, 〈n2, m2〉)| (n1, n2) ∈ Ri ∧(m1, m2) ∈ Rj}.

It is easy to verify that t(i, j) ∈ WF0 ⇔ i ∈ WF0 ∨ j ∈ WF0 and that min{|Ri|, |Rj|} ≤ |Rt(i,j)|. We have the following corollary.

Corollary 1.5.4. There is a recursive function p such that

and if p(m, n) ∈ then

min{|n|, |m|} ≤ |p(m, n)|,

where |m| = ∞ for m ∉ .

Proof. Let f0 be the recursive function “f ” in Lemma 1.4.2, f1 be the recursive function “f ” in Lemma 1.5.3 and let t be as above. Then the function p(i, j) = f0(t(f1(i), f1(j))) is exactly what is required.

Given a standard enumeration Φe(n, m, y) of partial recursive functions, there is an enumeration {xe}e<ω of -reals such that n ∈ xe ⇔ (∃y)(∀m)(Φe(n, m, y) ↓→ Φe(n, m, y) ≠ 0). We have the following effective version of Spector’s -boundedness principle.

Theorem 1.5.5 (Sacks). There is a recursive function ĝ such that

where .

Proof. Since the set {(m, n)| m ∉ xn} is , there is a recursive function h such that m ∈ xn ⇔ h(m, n) ∉ . Let p be the function in Corollary 1.5.4. Define a recursive function f such that Wf(n) = {p(h(m, n), m)| m ∈ ω}. If xn ⊆ , then Wf(n) ⊆ . Let ĝ(n) = 2g(f(n)) where g is the function in Lemma 1.3.5. By Lemma 1.3.5, . If , then by Lemma 1.3.5 again, Wf(n) ⊆ . But h(m, n) ∉ for all m ∈ xn. Then by Corollary 1.5.4, m ∈ for all m ∈ xn and hence xn ⊆ . Moreover, if xn ⊆ , then .

By Theorem 1.5.1, every -set is many-one reducible to . Hence we may view as providing the stages for enumerating a -set (this view will become clearer after the set 1 is introduced). Hence it is natural to think of a -set as analog of a (i.e. recursively enumerable) set. Now if one considers a “finite set” to be one whose members are all enumerated by some stage β < , then Spector’s boundedness principle says that any -set is “finite”. We shall make this precise with the introduction of admissible set theory.

In terms of definability, one would expect a big gap between possible order types of a recursive ordering and a -ordering. The following observation says otherwise.

Proposition 1.5.6. Suppose R is a well-ordering relation on ω. Then |R| < .

Proof. Suppose |R|≥ . Then n ∈ WF0 ⇔ (∃h)(∀i)(∀j)(Rn(i, j) → R(h(i), h(j))). This implies that WF0 is which is a contradiction.

Remark 1.5.7. For sets of reals, there is a boundedness principle for -sets. As discussed in §1.1.4, for each -set A of reals, there is a recursive function f : ωω → ωω such that x ∈ A ⇔ f(x) ∈ WO1. Then if A is , by the same argument as in the proof of Proposition 1.5.6, the supremum β = sup{|f(x)| | x ∈ A} of f(A) is less than .

For well-orderings of reals, by the same argument as in the proof of Corollary 1.5.2, each such well-ordering has order type less than .

1.5.3 Exercises

Exercise 1.5.1. Show that a partial recursive well-ordering is isomorphic to a recursive well-ordering.

Exercise 1.5.2. Prove that if x ∈ ωω is a nonrecursive -singleton, then there is a z ≡T x and a -set P ⊆ 2ω such that z is the unique nonrecursive real in P.

Exercise 1.5.3 (Jockusch and Soare [60]). Prove that if P ⊆ 2ω is a nonempty -set, then there is an x ∈ P such that .

Exercise 1.5.4. Prove that every uncountable -set P ⊆ ωω contains a perfect set [T]= {x ∈ ωω | (∀n)(x ↾ n ∈ T)}, where T is a -tree.

Exercise 1.5.5. Prove that every uncountable -set P ⊆ ωω contains a perfect set [T], where T is a tree recursive in .