I first seriously contemplated writing a book on degree theory in 1976 while I was visiting the University of Illinois at Chicago Circle. There was, at that time, some interest in an Q-series book about degree theory, and through the encouragement of Bob Soare, I decided to make a proposal to write such a book. Degree theory had, at that time, matured to the point where the local structure results which had been the mainstay of the earlier papers in the area were finding a steadily increasing number of applications to global degree theory. Michael Yates was the first to realize that the time had come for a systematic study of the interaction between local and global degree theory, and his papers had a considerable influence on the content of this book.

During the time that the book was being written and rewritten, there was an explosion in the number of global theorems about the degrees which were proved as applications of local theorems. The global results, in turn, pointed the way to new local theorems which were needed in order to make further progress. I have tried to update the book continuously, in order to be able to present some of the more recent results. It is my hope to introduce the reader to some of the fascinating combinatorial methods of Recursion Theory while simultaneously showing how to use these methods to prove some beautiful global theorems about the degrees.

This book has gone through several drafts. An earlier version was used for a one semester course at the University of Connecticut during the Fall Semester of 1979, at which time a special year in Logic was taking place. Many helpful comments were received from visitors to UConn and UConn faculty at that time. Klaus Ambos, David Miller and James Schmerl are to be thanked for their helpful comments. Steven Brackin and Peter Fejer carefully read sizable portions of that version and supplied me with many corrections and helpful suggestions on presentation. Richard Shore, Stephen Simpson and Robert Soare gave helpful advice about content and presentation of material. Other people whose comments, corrections and suggestions were of great help are Richard Epstein, Harold Hodes, Carl Jockusch, Jr. Azriel Levy and George Odifreddi.

This chapter is introductory in nature. We summarize material which is normally covered in a first course in Recursion Theory and which will be assumed within this book. Recursive and partial recursive functions are introduced and Church's Thesis is discussed. Relative recursion is then defined, and the Enumeration and Recursion Theorems are stated without proof. The reader familiar with this material should quickly skim through the chapter in order to become familiar with our notation. We refer the reader to the first five chapters of Cutland [1980] for a careful rigorous treatment of the material introduced in this chapter.

The Recursive and Partial Recursive Functions

The search for algorithms has pervaded Mathematics throughout its history. It was not until this century, however, that rigorous mathematical definitions of algorithm were discovered, giving rise to the class of partial recursive functions.

This book deals with a classification of total functions of the form in terms of the information required to compute such a function. The rules for carrying out such computations are algorithms (partial functions for some) with access to information possessed by oracles. The easiest functions to compute are those for which no oracular information is required, the recursive functions. Thus we begin by defining the (total) recursive functions, and then indicate how to modify this definition to obtain the class of partial recursive functions. The section concludes with discussions of Church's Thesis and of general spaces on which recursive functions can be defined.

Definition. Let is the least y such that if such a y exists, and is undefined otherwise. Henceforth, we will refer to as the least number operator.

Definition. The class R of recursive functions is the smallest class of functions with domain Nk for some and range N which contains:

1. (i) The zero function: Z(x) = 0 for all;

2. (ii) The successor function: S(x) = x + 1 for all;

3. (iii) The projection functions: for all and,

Degree theory, as it is studied today, traces its development back to the fundamental papers of Post [1944] and Kleene and Post [1954]. These papers introduced algebraic structures which arise naturally from the classification of sets of natural numbers in terms of the amount of additional oracular information needed to compute these sets. Thus we say that A is computable from B if there is a computer program which identifies the elements of A, using a computer which has access to an oracle containing complete information about the elements of B.

The idea of comparing sets in terms of the amount of information needed to compute them has been extended to notions of computability or constructibility which are relevant to other areas of Mathematical Logic such as Set Theory, Descriptive Set Theory, and Computational Complexity as well as Recursion Theory. However, the most widely studied notion of degree is still that of degree of unsolvability or Turing degree. The interest in this area lies as much in the fascinating combinatorial proofs which seem to be needed to obtain the results as in the attempt to unravel the mysteries of the structure. An attempt is made, in this book, to present a study of the degrees which emphasizes the methods of proof as well as the results. We also try to give the reader a feeling for the usefulness of local structure theory in determining global properties of the degrees, properties which deal with questions about homogeneity, automorphisms, decidability and definability.

This book has been designed for use by two groups of people. The main intended audience is the student who has already taken a graduate level course in Recursion Theory. An attempt has been made, however, to make the book accessible to the reader with some background in Mathematical Logic and a good feeling for computability. Chapter 1 has been devoted to a summary of basic facts about computability which are used in the book. The reader who is intuitively comfortable with these results should be able to master the book. The second intended use for the book is as a reference to enable the reader to easily locate facts about the degrees.