Page 52 - Textos de Matemática Vol. 38

44
PETER KOEPKE
The class
S = {T(μ,α)|μ,α ∈ Ord}
is the class of sets of ordinals of a transitive proper class model of set theory. Since the ordinal computations can be carried out in the ⊆-smallest such model, namely Go¨del’s model L of constructible sets, we obtain the main result char- acterizing ordinal computability:
Theorem 1.1. A set x ⊆ Ord is ordinal computable if and only if x ∈ L.
This theorem may be viewed as an analogue of the Church-Turing the- sis: ordinal computability defines a natural and absolute class of sets, and it is stable with respect to technical variations in its definition. Register machines on ordinals were first considered by Ryan Bissell-Siders [1]; the results proved in this article were guided by the related theory of ordinal Turing machines [7] which generalizes the infinite-time Turing machines of [5].
There are several open questions and projects connected with ordinal com- putability:
− how can other notions of computability be lifted from natural numbers to ordinals?
− how do recursion theoretic notions lift to ordinal machines, and what is their set-theoretic significance?
− can ordinal machines be used for the fine-structural analysis of the con- structible universe?
− can we generate larger models of set theory by some stronger notions of ordinal computation?
Our tutorial on ordinal computations will be structured as follows: − A review of the theory of ordinals.
− A short review of standard register machines.
− Definition of ordinal register machines.
− The theory SO of sets of ordinals.
− Interpreting ZFC within SO.
− A recursion theorem for ordinal computability.
− Computing a model of SO.
− Every constructible set of ordinals is ordinal computable. − An application: the generalized continuum hypothesis in L.