Page 82 - Textos de Matemática Vol. 38

74 PETER KOEPKE
The coding of formulas by ordinals φ will satisfy that ξ < φ for every constant symbol cξ occurring in φ. So the meaning of a bounded sentence φ is given by
(φ,<,G,R) φ.
This leads to the recursive definition of a bounded truth predicate T ⊆ Ord over
the ordinals
T(α) iff αisaboundedLT-sentenceand(α,<,G,T∩α)α.
We shall later see that T is a strong predicate which codes a model of set theory. We show that the characteristic function χT of T can be defined according to the recursion scheme
χT(α)= 1iff∃ν<αH(α,ν,χT(ν))=1 0 else
of Section 5 and is thus ordinal register computable provided we can exhibit an appropriate computable recursion function H:
H(α,ν,χ) = 1
iff α is an LT -sentence and
∃ξ,ζ<α(α=cξ ≡cζ ∧ξ=ζ)
or ∃ξ,ζ<α(α=cξ<cζ∧ξ<ζ)
or ∃ξ,ζ,η<α(α=G˙(cξ,cζ,cη)∧η=G(ξ,ζ)) or ∃ξ<α(α=R˙(cξ)∧ν=ξ∧χ=1)
or ∃φ<α(α=¬φ∧ν =φ∧χ=0)
or ∃φ,ψ<α(α=(φ∨ψ)∧(ν=φ∨ν=ψ)∧χ=1)
or ∃n<ω∃ξ<α∃φ<α(α=∃vn <cξφ∧∃ζ<ξν=φcζ ∧χ=1). vn
Assuming that the syntactical operations are computable, H and thus the bounded truth predicate T are computable.
9 Computing a model of set theory
The truth predicate T contains information about a large class of sets of ordinals.
Definition 9.1. For ordinals μ and α define
T(μ,α) = {β < μ|T(G(α,β)) = 1}.
Set
S = {T(μ,α)|μ,α ∈ Ord}.