Recursion Theory

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 ...