## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

#### 11.2.2 The proof of Harrington’s Theorem

We follow the presentation of Hjorth . 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 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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required