Loading field map
Descriptive set theory is the study of the definable subsets of Polish spaces—that is, of sets that can be described, or "defined," in some explicit way. A Polish space is a topological space that is separable (has a countable dense subset) and completely metrizable (its topology can be given by a metric in which every Cauchy sequence converges). The real line, the unit interval, the Cantor space of infinite binary sequences, and the Baire space of infinite sequences of natural numbers are all Polish spaces. The subject asks a deceptively simple question: when a set of points in such a space is defined by a formula of some logical complexity, what can we say about its size, its structure, and its measurability?
The field sits at the intersection of mathematical logic and analysis. From logic it takes the tools of recursion theory and the classification of formulas by quantifier complexity. From analysis it inherits the topological and measure-theoretic notions of regularity, such as the Baire property, Lebesgue measurability, and the perfect set property. The central tension of the subject is that the axiom of choice implies the existence of "wild" sets that lack all these regularity properties, yet any set that can be explicitly defined—in a sense made precise below—turns out to be tame. Descriptive set theory is the systematic study of this boundary between the definable and the pathological.
The foundational objects of the field are the Borel sets. Starting with the open sets of a Polish space, one closes under countable unions and countable intersections, iterating this process through the countable ordinals. The resulting hierarchy, the Borel hierarchy, assigns to each countable ordinal a level: the sets at level one are the open sets and the closed sets; level two consists of countable unions of closed sets and countable intersections of open sets; and so on. The Borel sets are exactly those that appear at some countable level. They form the smallest sigma-algebra containing the open sets.
The Borel sets are the first major class of definable sets, and they are already remarkably well behaved. Every Borel set has the Baire property, is Lebesgue measurable, and either is countable or contains a perfect set (a closed set with no isolated points, hence of the same cardinality as the continuum). These three properties—the Baire property, measurability, and the perfect set property—are the classical regularity properties, and the Borel sets satisfy all of them.
The next step is to consider projections of Borel sets. If one takes a Borel subset of a product of two Polish spaces and projects it onto one coordinate, the result need not be Borel. The class of such projections is called the class of analytic sets. These sets are also called Suslin sets, after the mathematician who first isolated them. The analytic sets are closed under countable unions and intersections, but not under complementation. The complement of an analytic set is called coanalytic. The union of the analytic and co-analytic sets forms the first level of the projective hierarchy, which is obtained by iterating the operation of projection and complementation through the natural numbers.
The analytic sets are still well behaved in many respects. They are Lebesgue measurable and have the Baire property, and they have the perfect set property: every uncountable analytic set contains a perfect subset. This last fact, proved by Suslin and Luzin, is a deep theorem that already shows the power of the descriptive approach. But the co-analytic sets are more delicate. Whether every co-analytic set has the regularity properties is independent of the standard axioms of set theory, ZFC. This independence is the first sign of the central phenomenon of the field: the behavior of definable sets beyond the Borel level is not settled by the usual axioms of mathematics.
The projective hierarchy extends the analytic and co-analytic sets by iterating the operation of projection. A set is projective if it can be obtained from a Borel set by a finite sequence of projections and complementations. The levels of this hierarchy are denoted by the symbols Sigma-n and Pi-n, with the analytic sets being the first level and the co-analytic sets the second. The projective sets are the sets that are definable by a formula of second-order arithmetic, that is, a formula that quantifies over real numbers as well as natural numbers.
The study of the projective hierarchy is the heart of descriptive set theory. The classical regularity properties—the Baire property, measurability, and the perfect set property—are known to hold for the first two levels of the hierarchy, but for the higher levels they are independent of ZFC. The reason is that the projective sets are intimately connected with the structure of the universe of sets. A set of reals at the third level of the hierarchy can encode a well-ordering of the reals, and the existence of such a well-ordering is equivalent to the failure of the regularity properties for certain projective sets.
The key to understanding the projective hierarchy is the axiom of determinacy. The axiom of determinacy states that for every subset of the Baire space, one of the two players in a certain infinite game has a winning strategy. The game is played as follows: the players alternately choose natural numbers, producing an infinite sequence; the first player wins if the sequence belongs to the set, and the second player wins otherwise. The axiom of determinacy says that for every set, one of the players has a strategy to force a win. This axiom is not provable from ZFC, and it is inconsistent with the axiom of choice, but it is consistent with the axiom of choice for a restricted class of sets.
The connection between determinacy and the regularity properties is one of the most striking results of the field. If a set is determined, then it has the Baire property and is Lebesgue measurable. Moreover, if all sets in a certain level of the projective hierarchy are determined, then they all have the perfect set property, which implies that the continuum is the second uncountable cardinal. The projective determinacy, the statement that all projective sets are determined, is a strong axiom that settles the behavior of the entire projective hierarchy. It is not provable from ZFC, but it is provable from large cardinal axioms, and it is widely accepted by set theorists as a natural extension of the standard axioms.
The study of determinacy has led to a deep connection between descriptive set theory and the theory of large cardinals. The existence of certain large cardinals, such as Woodin cardinals, implies the determinacy of the projective sets. Conversely, the determinacy of the projective sets implies the consistency of certain large cardinals. This equivalence is one of the most remarkable achievements of modern set theory, and it has transformed the field from a study of the topology of the real line into a branch of the study of the foundations of mathematics.
A parallel development, known as the effective theory or the theory of lightface sets, arose from the connection between descriptive set theory and recursion theory. In this approach, one considers not all definable sets but those that are definable in a computable way. The effective Borel hierarchy is defined by starting with the recursively enumerable sets and iterating the operations of complementation and projection through the recursive ordinals. The effective analytic sets are the projections of the effective Borel sets, and the effective projective hierarchy is defined similarly.
The effective theory is more refined than the classical theory, because it distinguishes between sets that are merely definable and sets that are computable. The classical regularity properties have effective versions: a set is effectively measurable if there is a recursive function that computes its measure, and the effective perfect set theorem states that every effective analytic set that is uncountable contains a perfect subset that is itself effective. The effective theory also provides a natural framework for the study of the degrees of unsolvability, the equivalence classes of sets of natural numbers under the relation of mutual recursion.
The effective theory is not a separate subject but rather a refinement of the classical theory. Many classical theorems have effective versions, and the effective versions often provide the proofs of the classical results. The connection between the two is given by the notion of relativization: a classical set is analytic if and only if it is effective relative to some real number. This relationship allows one to transfer results from the effective theory to the classical theory and back.
A different line of research, initiated by William Wadge in the 1970s, studies the structure of the Borel sets and the projective sets by means of the Wadge order. The Wadge order is a preorder on the subsets of a Polish space defined by the relation of continuous reduction: a set \(A\) is Wadge-reducible to a set \(B\) if there is a continuous function \(f\) such that \(x \in A\) if and only if \(f(x) \in B\). The Wadge order is a well-founded preorder on the Borel sets, and its structure is described by the Wadge hierarchy, which is a refinement of the Borel hierarchy.
The Wadge hierarchy is a linear order of the Borel sets, and it is closely related to the notion of the degree of a set. The Wadge degree of a set is the equivalence class of the set under the relation of mutual Wadge-reducibility. The Wadge degrees of the Borel sets form a well-ordered hierarchy, and the structure of this hierarchy is completely determined by the Borel rank of the set. The Wadge hierarchy has been extended to the projective sets, but the structure of the projective Wadge degrees is not determined by ZFC; it depends on the axioms of determinacy.
The Wadge order is also connected to the theory of games. The Wadge game is a game in which the two players choose elements of the space, and the first player wins if the sequence of choices belongs to the set \(A\) if and only if the sequence of choices of the second player belongs to the set \(B\). The Wadge game is determined for all Borel sets, and the determinacy of the Wadge game for a class of sets is equivalent to the determinacy of the games for that class. This connection has made the Wadge order a central tool in the study of the determinacy of the projective sets.
The modern field of descriptive set theory is characterized by a deep interplay between the classical theory, the effective theory, and the theory of determinacy. The classical theory of the Borel and analytic sets is a well-established body of results that is independent of the axioms of set theory. The theory of the projective sets, on the other hand, is intimately connected with the axioms of set theory, and the modern work has focused on the consequences of determinacy and the large cardinal axioms.
One of the most important developments of the last decades is the theory of the universally Baire sets. A set is universally Baire if its preimage under every continuous function from a Polish space to the space is a set with the Baire property. The universally Baire sets form a class that is closed under the operations of the projective hierarchy, and they have the regularity properties. The theory of the universally Baire sets is connected with the theory of the Woodin cardinals, and it has led to the development of the theory of the inner model program, which aims to construct canonical inner models for the large cardinal axioms.
Another important development is the theory of the determinacy of the games of length \(\omega1\). The axiom of determinacy for the games of length \(\omega1\) is a stronger axiom than the projective determinacy, and it implies that the projective sets are all determined. The study of the games of length \(\omega_1\) has led to the theory of the "large" cardinals and the theory of the "strong" axioms of determinacy.
The field is also connected with the theory of the descriptive set theory of the reals in the context of the theory of the "inner model" of the set theory. The theory of the "core model" and the theory of the "mouse" are the tools of the modern set theory, and they are used to prove the consistency of the determinacy axioms with the large cardinal axioms.
The present landscape of the field is characterized by a deep and fruitful interaction between the descriptive set theory and the rest of set theory. The classical results of the field are the foundation of the subject, and they are used in the analysis of the structure of the real line. The modern results are the results of the theory of the determinacy and the theory of the large cardinals, and they have transformed the field into a central part of the study of the foundations of mathematics. The field is not a closed subject but a living one, and the open problems of the field are the problems of the structure of the projective sets and the problem of the consistency of the axioms of the determinacy with the axioms of the choice.