Page 83 - Textos de Matemática Vol. 38

ORDINALS, COMPUTATIONS, AND MODELS OF SET THEORY 75
Theorem 9.2. (Ord, S, <, =, ∈, G) is a model of the theory SO.
Proof. The axioms (1)-(7) are obvious. The proofs of axiom schemas (8) and
(9) rest on a Levy-type reflection principle. For θ ∈ Ord define Sθ = {T(μ,α)|μ,α ∈ θ}.
Then for any LSO-formula φ(v0,...,vn−1) and η ∈ Ord there is some limit ordinal θ > η such that
∀ξ0,...,ξn−1 ∈ θ((Ord,S,<,=,∈,G) φ[ξ0,...,ξn−1] iff (θ,Sθ,<,=,∈,G) φ[ξ0,...,ξn−1]).
Since all elements of Sθ can be defined from the truth function T and ordinals < θ, the right-hand side can be evaluated in the structure (θ, <, G ∩ θ3, T ) by an LT -formula φ∗which can be recursively computed from φ. Hence
∀ξ0,...,ξn−1 ∈ θ((Ord,S,<,=,∈,G) φ[ξ0,...,ξn−1] iff
(θ,<,G ∩ θ3,T) φ∗[ξ0,...,ξn−1]).
So sets witnessing axioms (8) and (9) can be defined over (θ, <, G ∩ θ3, T ) and are thus elements of S.
The powerset axiom can be shown by a similar reflection argument. ✷ 9.1 Ordinal computability corresponds to constructibility
Kurt Go¨del [4] defined the inner model L of constructible sets as the union of a hierarchy of levels Lα:
L= Lα α∈Ord
where the hierarchy is defined by: L0 = ∅, Lδ = α<δ Lα for limit ordinals δ, and Lα+1 =the set of all sets which are first-order definable in the structure (Lα, ∈). The model L is the ⊆-smallest inner model of set theory. The standard reference for the theory of the model L is the monograph [3].
The following main result provides a characterization of ordinal register computability which does not depend on a specific machine model or coding of language:
Theorem 9.3. A set x of ordinals is ordinal computable if and only if it is an element of the constructible universe L.
Proof. Let x ⊆ Ord be ordinal computable by the program P from the ordinals δ1,...,δn−1, so that for every α ∈ Ord:
P : (α,δ1,...,δn−1,0,0,...) → χx(α).