1 An introduction to higher recursion theory
1.1 Projective predicates
1.1.1 Recursive and arithmetical predicates
A recursive predicate R on ω is a total recursive function Φ : ω → 2 such that R(n) ⇔ Φ(n) = 1. With a standard coding of ω<ω in ω, one may define recursive predicates on ω<ω. Similarly one may code ωn in ω to obtain recursive n-ary predicates on ω, as well as recursive predicates on (ω<ω)m × ωn. The class of arithmetical predicates on ωω × ω is now defined as follows:
Definition 1.1.1. A predicate R(x, n) on ωω × ω is partial recursive if there is a partial recursive function Φ(σ, n) on ω<ω × ω such that
(i)(∀σ)(∀τ)(∀n)[Φ(σ, n) ↓ ∧ σ τ → (Φ(τ, n) ↓ ∧ Φ(σ, n) = Φ(τ, n))].
(ii)For any x ∈ ωω and n ∈ ω, R(x, n) if and only if (∃