Introduction

There are two basic properties of a logical system: consistency and completeness. These two properties are important for systems used for particular special purposes (say, in artificial intelligence), as well as for systems proposed as foundations of the all of mathematics. Therefore, any systematic study of the foundations of mathematics should address questions of consistency and completeness. Gödel's theorems provide negative information about both: any reasonable sufficiently strong theory is unable to demonstrate its own consistency and any such system is incomplete.

There has been impressive success in proving independence results for set theory. Cohen's forcing method and its boolean valued version was applied to solve the continuum problem and to prove a lot of other sentences to be independent of set theory. This may give the impression that logic is doing very well in studying the independence phenomenon which is only partly true. The known independent sentences in set theory express statements about infinite sets. The type of the infiniteness in these independence results is, in a sense, of higher order than in classical mathematics. For instance, the continuum hypothesis talks about the cardinality of the set of real numbers, which is in any case uncountable. While most of classical mathematics is about real numbers, almost everything there can be encoded using only a countable number of elements, hence can be expressed as a statement about natural numbers. As an example, consider a continuous real function. Clearly, such a function is described by its values on rationals, thus statements about continuous functions can be written as arithmetical formulas. For arithmetical formulas, current methods of logic almost completely fail. An exception are Paris-Harrington type independence results (28). Still it is true that no problem from classical mathematics (i.e. number theory, algebra, calculus) was proved independent from a logical theory before it had actually been solved. Furthermore, it seems that even the most difficult classical results in number theory and finite combinatorics can be proved in Peano arithmetic, a theory which is much weaker than Zermelo-Fraenkel set theory.

Therefore one of the principal goals of mathematical logic should be development of new techniques for proving independence.

The theory set out in this book is the result of the confluence and common development of two currents of mathematical research, Descriptive Set Theory and Recursion Theory. Both are concerned with notions of definability and, more broadly, with the classification of mathematical objects according to various measures of their complexity. These are the common themes which run through the topics discussed in this book.

Descriptive Set Theory arose around the turn of the century as a reaction among some of the mathematical analysts of the day against the free-wheeling methods of Cantorian set theory. People such as Baire, Borel, and Lebesgue felt uneasy with constructions which required the Axiom of Choice or the set of all countable ordinals and began to investigate what part of analysis could be carried out by more explicit and constructive means. Needless to say, there was vigorous disagreement over the meaning of these terms. Some of the landmarks in the early days of Descriptive Set Theory are the construction of the Borel sets, Suslin's Theorem that a set of real numbers is Borel just in case both it and its complement are analytic, and the discovery that analytic sets have many pleasant properties — they are Lebesgue measurable, have the Baire property, and satisfy the Continuum Hypothesis.

A natural concomitant of this interest in the means necessary to effect mathematical constructions is the notion of hierarchy. Roughly speaking, a hierarchy is a classification of a collection of mathematical objects into levels, usually indexed by ordinal numbers. Objects appearing in levels indexed by larger ordinals are in some way more complex that those at lower levels and the index of the first level at which an object appears is thus a measure of the complexity of the object. Such a classification serves both to deepen our understanding of the objects classified and as a valuable technical tool for establishing their properties.

A familiar example, and one which was an important model in the development of the theory, is the hierarchy of Borel sets of real numbers. This class is most simply characterized as the smallest class of sets containing all intervals and closed under the operations of complementation and countable union.