Recursion Theory

11.2.2 The proof of Harrington’s Theorem

We follow the presentation of Hjorth [50]. By Theorem 2.6.5, for any recursive ordinal β ≥ ω, there is an n ∈ such that |n|= β and the set {m | m <o n} is recursive. We choose such an ordinal β and the corresponding n.

For each m = 3 ⋅ 5k <o n, let {ij, m}j<ω be a sequence of numbers such that

i0, m = Φk(m)

and

ij+1, m = Φk(m + j + 1).

By the proof of Theorem 2.6.5, we may assume that m ≤ ij, m < ij+1, m for all j. Clearly the set {(ij, m, j, m) | (∃k)(m = 3 ⋅ 5k ∧ m <o n ∧ j ∈ ω)} is recursive.

Lemma 11.2.7.

(i)For any m = 3 ⋅ 5k <o n and

(ii)for any l <o n, the set {m | (∃k)(i0, m <o l <o m = 3 ⋅ 5