Introduction

Summary

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.