Recursion Theory

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 (∃