Preface

… logic is about definability.
– Gerald E. Sacks [124]

The above quote underlines the authors’ view that recursion theory is anchored on the notion of definability. Although classically the theory began with Turing’s conception of effective computability (of various types of objects), it soon took on a much broader perspective. A fundamental theorem states that a set of natural numbers is computable if and only if it is -definable in first order arithmetic. This sets the stage for a general study of sets of natural numbers and their syntactic classes.

The view on definability does not conflict with the fact that computation is the heart of recursion theory. Indeed a definability problem naturally translates into one about (possibly relativized) computation and vice versa. Kleene’s characterization of the -sets of numbers as precisely those that are hyperarithmetic, and the corresponding theorem of Spector and Gandy that these are all the reals in , is a case in point. Once the syntax (the language of first and second order arithmetic) and the structure in which to interpret members of ω and its subsets are specified, definability naturally takes its place. Tools and construction techniques have been introduced to study problems concerning computability for syntactic classes over ω, 2ω and even the power set of 2ω or ωω. Post’s problem for the recursively enumerable sets, the Gandy basis theorem for -sets of reals, characterization of -sets in terms of hyperarithmeticity, the definability of the jump operator, are immediate examples. Indeed it is hard to find a problem in the area that has little to do with definability. The title of this book is chosen to reflect this point.

The idea of writing a book in recursion theory, focusing on the computational aspects of the set of reals and its subsets, evolved over a period of time. The subject was established by Kleene who introduced the notion of hyperarithmetic hierarchy relative to a real and its associated ordinals. It grew in the hands of Spector, Gandy, Kreisel and Sacks. These were major developments in what one now calls higher recursion theory. The theory was a subject of intensive study for almost thirty years beginning in the 1950s, but seemed to lose momentum in the 1980s. In an interview reproduced in the Appendix, Sacks remarked: “I tended over the years to keep predicting the immediate end of recursion theory, but I have been wrong every time.” Despite the rather pessimistic pronouncement by one of the founders of the field, recursion theory is alive and well. However, higher recursion theory in the grand tradition of the pioneers received only occasional attention since, even though a number of highly significant contributions to the subject, such as Slaman and Woodin’s theorem on the rigidity of the hyperdegrees, were made towards the end of the last century, and many interesting as well as challenging problems remain. Indeed Sacks himself bade farewell to higher recursion theory in 1998. Today the subject is not pursued with as much vigor or zeal as it deserves. We view this as rather unfortunate since in it one sees a beautiful illustration of the unity of mathematical logic, where ideas and tools from set theory and model theory are fruitfully applied to study problems about computability. It was a tempting proposition to write another book (following Sacks’s Higher Recursion Theory [123]) to exhibit this interplay. Recent advances in the study of the global theory of Turing and hyperdegrees, and the emergence of higher randomness as a subject of investigation, provided the impetus for us to turn the idea into reality. It is hoped that the reader would agree, at the end of it, that the enterprise of generalizing recursion theory that began more than half a century ago has been mathematically rewarding, and that the subject is both attractive and highly challenging, with many deep and elegant theorems.

This book consists of four main parts. The first six chapters constitute Part I and develop the fundamental theory of -sets and fine structure theory of the constructible universe, the ramified analytical hierarchy, and set theory. They lay the groundwork for the rest of the book. Part II focuses on the structure of Turing degrees. Here we discuss classification of the jump operator in relation to Martin’s conjecture and the construction of -sets, as well as degree-theoretic independence results. We turn our attention to hyperdegrees in Part III. In particular, we prove the rigidity of the structure of the hyperdegrees and its biinterpretability with second order arithmetic. We also include a chapter on basis/antibasis theorems as well as perfect subsets in L. Part IV is devoted to the study of higher randomness, a subject which is naturally linked to the topics covered in the first three parts. Exercises are sprinkled throughout the chapters. Many of them are intended to supplement the topics covered. The most challenging ones are labelled with a *.

The book ends with an interview with Gerald Sacks (in Appendix B) conducted in 2009. We think that it is fitting to conclude the book with a tribute to one whose work has arguably substantially shaped the development of recursion theory, both classical and higher, in the last century.

A word about prerequisites: While this book attempts to cover as much background material as possible, it is not intended to be encyclopedic. The reader is assumed to be familiar with basic logic and set theory, including classical recursion theory, basic set theory (including forcing) and algorithmic randomness. A number of the results are used in proofs, sometimes without explicit mention. In line with our preference and taste, some of the proofs of theorems in set theory presented are discernibly recursion-theoretic in flavor. These proofs are not necessarily the simplest. Our aim is to offer the reader a different perspective to these theorems by highlighting the effective content that is not immediately apparent. Hopefully these provide additional insights to the ideas that went behind the proofs.

The materials in the first two chapters closely follow Sacks’s Higher Recursion Theory [123]. Mansfield and Weitkamp’s monograph Recursive Aspects of Descriptive Set Theory [88] was also one of our key references. Of course one should not fail to mention Hartley Rogers’s classic Theory of Recursive Functions and Effective Computability [116], the book that first made recursion theory accessible to several generations of students in logic and which largely set the style for books on this subject.

In this book we give preference to calling the subject recursion theory rather than computability theory (as it is otherwise known) in deference to its historical origin, although both terms are used interchangeably throughout.

During the preparation of the manuscript, the authors benefited from comments and suggestions of colleagues and students, some of whom read through various portions of the book. Certain chapters were used by the second author in a graduate course given at the National University of Singapore. We thank Laurent Bienvenu, Peter Cholak, Decheng Ding, Qi Feng, Su Gao, Junle Goh, Noam Greenberg, Wei Li, Yiqun Liu, Yong Liu, Benoit Monin, André Nies, Dilip Raghavan, Gerald Sacks, Richard Shore, Stephen Simpson, Theodore A. Slaman, Frank Stephan, Wei Wang, Yue Yang and Jing Zhang for their interest, ideas, suggestions and/or support of this project.

Finally, for this work Chong was partially supported by NUS grant WBS C140-000-025-00, while Yu was supported in part by the National University of Singapore, the Humboldt Foundation and the National Science Foundation of China grant no. 11071114 and 11322112. Their generosity is gratefully acknowledged.

Chitat Chong and Liang Yu
15 June 2015