Techniques of admissible recursion theory (Q1059069)

Recursion theory has been generalized mainly in two directions, one where the finitary aspect of recursion theory is kept and one where it is not. Recursion theory generalized to ordinals and admissible structures is one main example of the second kind. Kreisel pointed out that in generalizing recursion theory it is important to generalize 'finiteness' and that this will be the key to the proper theory. An admissible structure is a transitive set satisfying a fragment of ordinary set theory. An admissible ordinal \(\alpha\) is one for which \(L_{\alpha}\), the hierarchy of constructible sets up to \(\alpha\), is an admissible structure. It turned out that admissible ordinals and certain admissible structures are suitable as domains for generalized recursion theory, 'finite' is then replaced with 'element of the structure \(/L_{\alpha}'.\) The theory of Turing degrees has been a main subject in standard recursion for the last quarter of a centennium, and related problems have been central in the generalized theory. This involves transferring non trivial combinatorial arguments to a situation where various degrees of definability and various notions of smallness must replace the finite. It is to this world the author introduces us. Chapter 1 introduces the main concepts of ordinal recursion theory; recursive enumerability, finite sets etc., and some combinatorial properties of these. In Chapter 2 the notion of a Turing-jump is generalized and likewise the result that any degree above O' is the jump of some other degree. The finite injury method is one of the most elegant methods of recursion theory. Two examples of this method generalized to admissible ordinals is given in chapter 3, one solving the analogue of Post's problem and one generalizing Sacks' splitting theorem. In chapters 4-6 various categories of r.e. sets are studied and the connection with the classical theory is discussed, in chapters 7 and 8 infinite injury arguments leading to the construction of minimal pairs and to the proof of the density theorem are given. In chapter 9 the author leaves the r.e. degrees and studies the problem of minimal degrees. A generalization of the classical construction is given for certain ordinals. In chapter 10 recent results using methods from set theory, Jensen's fine structure theory for the constructible sets, are exploited. In an appendix we find Harrington's construction of an admissible structure where Post's problem fails. The book is a valuable text on the theory of recursion theory on admissible ordinals. It is well written, the proofs are well structurized and the material is organized in a coherent way. Though some results about general admissible structures are mentioned, mainly problems of \(\alpha\)-recursion theory are discussed. The book is however recommended for anyone interested in a coherent text on that subject, either for learning or as a reference-book.