Page 85 - Textos de Matemática Vol. 38

ORDINALS, COMPUTATIONS, AND MODELS OF SET THEORY 77
Proof. a) Take a program P and α′1, . . . , α′n−1 ∈ Ord such that for every α ∈ Ord:
P : (α,α′1,...,α′n−1,0,0,...) → χx(α).
Let θ be an upper bound for the lengths of these computations for α < κ. Take a transitive ZF−-model (M,∈) such that α′1,...,α′n−1,θ,κ,x ∈ M. Since ordinal computations are absolute for models of set theory, for all α < κ:
(M,∈) P : (α,α′1,...,α′n−1,0,0,...) → χx(α).
The downward Lo¨wenheim-Skolem theorem and the Mostowski isomor-
phism theorem yield an elementary embedding
π : ( M¯ , ∈ ) → ( M , ∈ )
suchthatM¯ istransitive,card(M¯)=κand{α′1,...,α′n−1,θ,κ,x}∪κ⊆π′′M¯. Let π(α1) = α′1,...,π(α′n−1) = αn−1. Then α1,...,αn−1 < κ+ since card(M¯) < κ+. Observe that π(x) = x. Since π is elementary (M¯,∈) satis- fies for α < κ that
(M¯,∈) P : (α,α1,...,αn−1,0,0,...) → χx(α). By the absoluteness of ordinal computations between M¯ and V
P : (α,α1,...,αn−1,0,0,...) → χx(α)
for α < κ. Thus x is ordinal computable from the parameters α1, . . . , αn−1 < κ+. b) follows from a) since there are a countable many programs and κ+ many finite sets of ordinals < κ+.
c) is immediate from b). ✷
Bibliography
[1] Ryan Bissell-Siders. Ordinal computers. Eprint at: arXiv:math.LO/9804076, 1998.
[2] Nigel J. Cutland. Computability: An introduction to Recursive Function Theory. Perspectives in Mathematical Logic. Cambridge University Press, 1980.
[3] Keith Devlin. Constructibility. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1984.
[4] Kurt G¨odel. The Consistency of the Continuum Hypothesis, volume 3 of Ann. of Math. Studies. Princeton University Press, Princeton, 1940.
[5] Joel David Hamkins and Andy Lewis. Infinite Time Turing Machines. J. Symbolic Logic, 65(2):567–604, 2000.