Recursion Theory

Lemma 14.3.6. If x is -random and y ≤h x, then there is a recursive ordinal γ such that y ≤T x ⊕(γ).

Proof. Since x is -random, we have = . Let y ≤h x. Then there is a formula with rank at most β0 < such that

By Lemma 13.1.1, there is a recursive ordinal ...