1.2.2 Relativized image

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

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

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.