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 nimage 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)


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

By the proof of Theorem 2.6.5, we may assume that mij, m < ij+1, m for all j. Clearly the set {(ij, m, j, m) | (∃k)(m = 3 ⋅ 5km <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

Get Recursion Theory now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.