Page 84 - Textos de Matemática Vol. 38

76 PETER KOEPKE
By the simple nature of the computation procedure the same computation can be carried out inside the inner model L, so that for every α ∈ Ord:
(L,∈) P : (α,δ1,...,δn−1,0,0,...) → χx(α).
Henceχx ∈Landx∈L.
Conversely consider x ∈ L. Since (Ord,S,<,=,∈,G) is a model of the
theory SO there is an inner model M of set theory such that S = {z ⊆ Ord |z ∈ M }.
SinceListhe⊆-smallestinnermodel,L⊆M.Hencex∈M andx∈S.Let x = T (μ, α). By the computability of the truth predicate, x is ordinal register computable from the parameters μ and α. ✷
10 An application: the generalized continuum hypoth- esis in L
Ordinal computability allows to reprove some basic facts about the con- structible universe L. The analogue of the axiom of constructibility, V = L, is the statement that every set of ordinals is ordinal computable.
Theorem 10.1. The constructible model (L, ∈) satisfies that every set of ordinals is ordinal computable.
Proof. Let x ∈ L, x ⊆ Ord, let P be a program and δ1,...,δn−1 ∈ Ord such that for every α ∈ Ord:
P : (α,δ1,...,δn−1,0,0,...) → χx(α).
The same computation can be carried out inside the inner model L:
(L,∈) P : (α,δ1,...,δn−1,0,0,...) → χx(α).
So in L, x is ordinal computable. ✷
The following theorem is proved by a condensation argument for ordinal computations which is a simple analogue of the usual condensation argument for the constructible hierarchy.
Theorem 10.2. Assume that every set of ordinals is ordinal computable. Then: a) Let κ ω be an infinite ordinal and x ⊆ κ. Then there are ordinals α1,...,
αn−1<κ+ such that x is ordinal computable from the parameters α1,...,αn−1. b) Let κ ω be infinite. Then card(P(κ)) = κ+.
c) The generalized continuum hypothesis GCH holds.