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