## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required