CHAPTER 1
Introduction
The study of recursive ordinals and hyperarithmetic sets that began with the
work of Church and Kleene [CK37], Church [Chu38] and Kleene [Kle38] suggested
many analogies between the II} and hyperarithmetic sets and the recursively enu-
merable and recursive ones, respectively. The analogy was not perfect, however.
At the basic level, for example, the range of a hyperarithmetic function on a hy-
perarithmetic set is always hyperarithmetic rather than an arbitrary II} set. At a
deeper level, all nonhyperarithmetic II} sets are of the same hyperarithmetic degree.
Kreisel [Kre61] studied this situation and came to the realization that while II} is
analogous to r.e., the correct analog for hyperarithmetic is not recursive but finite.
This insight lead first to the development by Kreisel and Sacks [KS63, KS65]
of metarecursion theory as the study of recursion theory on the recursive ordinals
(those less than cjfK, the first nonrecursive ordinal) or, equivalently, on their no-
tations in a II} path through Kleene's O. In this setting, the meta-r.e. subsets of
UJ are the 11} ones and the metafinite ones are hyperarithmetic.
Another approach to generalizing recursion theory to ordinals started with
Takeuti's [Tak60, Tak65] development of Godel's [G39] constructible universe L
through a recursion theory on the class of all ordinals. These two approaches came
together in the common generalization of recursion on admissible ordinals of Kripke
[Kri64] and Platek [Pla65]. Here the domain of discourse is an ordinal a or the
initial segment La of L up to a for admissible a, i.e. La satisfies Ei-replacement.
In this vein, a-r.e. is Ei over La, a-recursive is then Ai over La while a-finite
means a member of La. These notions coincide with those of metarecursion theory
when a
UJ^_K
.
We should also note that care has to be taken in the definition of "a-recursive
in", the analog of Turing reducibility. Here too, the crucial issue is that of finiteness.
It no longer suffices to require that one be able to answer single membership question
about A in a computation from B to say that A is reducible to B. Instead one
defines a-reducible, ^
a
, by requiring that all a-finite sets of such questions about
A can be computed on the basis of a-finitely much information about B.
The motivation and goals for generalizing recursion theory in this way included
the hopes of elucidating the underlying nature of the notions fundamental to recur-
sion theory and the essences of the constructions that are used to prove its most
important theorems. In accordance by Kreisel's insight, a prominent role should
be played by the analysis of finiteness along with recursive and recursively enu-
merable. Such an analysis might lead to a good axiomatic treatment or reveal
approaches that would be less dependent on the specific combinatorial properties
of UJ exploited in these notions and constructions. In this way the study might
also produce applications to both classical recursion theory and other domains (set
Previous Page Next Page