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