You are here

Descriptive Set Theory

Yiannis N. Moschovakis
American Mathematical Society
Publication Date: 
Number of Pages: 
Mathematical Surveys and Monographs 155
[Reviewed by
Leon Harkleroad
, on

Lebesgue, Baire, Emile Borel, Luzin, Suslin: The field of descriptive set theory arose around a hundred years ago as analysts explored the nature of subsets of and functions on Rn. Particular attention was paid to sets and functions that are definable by starting with staples of analysis like open sets and continuous functions, and then iteratively applying operations like countable intersections and pointwise limits. As things turned out, many of the questions people studied cannot be resolved by the Zermelo-Fraenkel axioms. Thus the development of classical descriptive set theory blended together real analysis, topology, and mathematical logic.

At mid-twentieth century, considerations in computability theory led Stephen Kleene and others to examine similar matters of definability of sets and functions, but in the context of the natural numbers, rather than the reals. Here the computable functions served as the analog to the continuous functions of the analysts.

Despite the obvious contrast between the discrete and the continuous settings, many parallels became apparent, giving rise to so-called effective descriptive set theory, which encompasses both the naturals and the reals. Moreover, the computability-theoretic techniques involved have brought new insights and results even to the purely classical realm. Over the last two decades, a further development known as invariant descriptive set theory has focused on equivalence relations and involved many other areas of mathematics, including algebra and graph theory. (An earlier MAA Review discusses two recent books that deal with the invariant theory.)

In 1980, North-Holland brought out the first edition of Yiannis Moschovakis' Descriptive Set Theory. This book presented both the classical and effective theories, including some of Moschovakis' own work, which has strongly influenced the field. Besides its extensive coverage, the text featured a large number of exercises, plus a section of historical remarks in each chapter.

Acclaimed at the time of its publication, that book continues to be cited often in the literature, not only in mathematics, but also in theoretical computer science. However, North-Holland let it go out of print. Fortunately, the AMS has made it available again.

The new edition includes an updated bibliography, a short new section, and various rewrites and corrections (along with several new minor typos). But by and large, the original text remains intact. Although this edition does not cover some of the developments that have transpired since the 1980 original, it preserves a book that has been and remains highly valuable in its area.

Although in recent years Leon Harkleroad has mostly concentrated on mathematical aspects of music, he still enjoys revisiting his old stomping grounds of computability theory and mathematical logic.