Descriptive set theory

The branch of set theory whose subject is the study of sets in dependence of those operations by which these sets may be constructed from relatively simple sets (e.g. closed or open subsets of a given Euclidean, metric or topological space). These operations include union, intersection, taking a complement or projection, etc. Descriptive set theory was created in the early 20th century by the studies of E. Borel, R. Baire and H. Lebesgue in connection with the measurability of sets. Borel-measurable sets received the name of Borel sets or $ B $- sets (cf. Borel set). On the other hand, Baire proposed a classification of functions, in so-called Baire function classes, and proved a number of theorems concerning these functions (cf. Baire classes; Baire theorem). Lebesgue showed that $ B $- sets are identical to Lebesgue sets of Baire functions (cf. Lebesgue set), gave the first classification of $ B $- sets and showed that none of its classes was empty.

The study of $ B $- sets became an important task of descriptive set theory, and the first such problem was the cardinality of $ B $- sets. After the introduction of the Lebesgue measure it was found that the class of measurable sets is much wider than the class of $ B $- sets, and there arose the problem of determining whether or not a given set is measurable. The solution of this problem for a particular set usually involves the classification of the process by which this set may be constructed, i.e. its descriptive structure. This defines another important circle of problems dealt with by descriptive set theory, viz., to find the widest possible class (with preservation of measurability) of operations over sets and the study of the properties of the results of these operations. The solution of these problems, which arose as a results of studies by French mathematicians, must be credited, in essence, to Russian mathematicians, viz. N.N. Luzin and his school.

One of the most important problems, viz. the problem of the cardinality of $ B $- sets, was solved by P.S. Aleksandrov [1] in 1916, who constructed the $ {\mathcal A} $- operation for this purpose. He showed that the use of the $ {\mathcal A} $- operation, while taking intervals as the starting point, makes it possible to construct any desired $ B $- set, and that any uncountable set obtained by way of the $ {\mathcal A} $- operation (and called an $ {\mathcal A} $- set) contains a perfect set and thus has the cardinality of the continuum. This result was also independently obtained by F. Hausdorff. M.Ya. Suslin [2] showed that there exists an $ {\mathcal A} $- set which is not a Borel set. He also introduced the name $ {\mathcal A} $- set and $ {\mathcal A} $- operation, in honour of Aleksandrov. $ {\mathcal A} $- sets are also known as Suslin sets, or as analytic sets (cf. Analytic set). For an $ {\mathcal A} $- set to be a $ B $- set it is necessary and sufficient: 1) for its complement to be again an $ {\mathcal A} $- set (the Suslin criterion); or 2) for it to be the result of an $ {\mathcal A} $- operation with non-intersecting components (the Luzin criterion). All $ {\mathcal A} $- sets are measurable and display the Baire property. The following new methods for obtaining $ {\mathcal A} $- sets, equivalent to $ {\mathcal A} $- operations, were found: $ {\mathcal A} $- sets are projections of $ B $- sets (and even of $ G _ \delta $- sets); $ {\mathcal A} $- sets are continuous images of the space $ \mathbf I $ of irrational numbers; and, as a consequence, $ {\mathcal A} $- sets are continuous images of $ B $- sets [3]. At the same time, a continuous one-to-one (and even a countably-to-multiple [4]) image of a $ B $- set is a $ B $- set, and any uncountable $ B $- set is the union of an at most countable set and a one-to-one continuous image of $ \mathbf I $[3]. Finally, Luzin found yet another important way of defining $ {\mathcal A} $- sets with the aid of his sieve operation (cf. Luzin sieve). Transfinite sieve indices and constituents have become a powerful tool in the study of the properties of $ {\mathcal A} $- sets and their complements: $ C {\mathcal A} $- sets (cf. $ C {\mathcal A} $- set).

In the course of his studies on the cardinality of $ C {\mathcal A} $- sets, Luzin introduced projective sets (cf. Projective set). Each class $ \alpha $ of projective sets contains sets which do not belong to classes $ < \alpha $[3], [5]. The concept of a universal set [3], [6], [5] is an important tool in the demonstration of this and other theorems asserting that certain classes of sets are non-empty. The study of projective sets, even those of the second class, encounters difficulties which have not yet been overcome. One problem which has thus remained unsolved is the measurability of $ ( B _ {2} ) $- sets, the cardinality of these sets, and whether or not they display the Baire property. Important results in this matter were obtained by P.S. Novikov [4]: There exists an uncountable $ C {\mathcal A} $- set for which the assumption that it contains no perfect subset is not self-contradictory; there exists a $ ( B _ {2} ) $- set for which the assumption that it is non-measurable is not self-contradictory.

The introduction by Aleksandrov [7] of the $ \Gamma $- operation, which is complementary to the $ {\mathcal A} $- operation, was the first step in the development of A.N. Kolmogorov's [8] and Hausdorff's [9] general theory of set-theoretic operations; however, the fundamental class of operations is constituted by positive set-theoretic operations, or the so-called $ \delta $- $ \sigma $- operations. For each such $ \delta $- $ \sigma $- operation $ \Phi $ a complementary $ \delta $- $ \sigma $- operation $ \Phi ^ {c} $ was defined and the formula

$$ \Phi ^ {c} ( \{ E _ {n} \} ) = \ C [ \Phi ( \{ C E _ {n} \} ) ] , $$

which may be considered as the definition of $ \Phi ^ {c} $, was given. The concept of a normal $ \delta $- $ \sigma $- operation (for any family $ M $ of sets $ \Phi ( \Phi ( M) ) = \Phi ( M) $[8]) was also introduced. The $ {\mathcal A} $- operation and the $ \Gamma $- operation are mutually complementary normal $ \delta $- $ \sigma $- operations. The same applies to the operations of countable union and countable intersection. One of the key theorems of the general theory of operations over sets in topological spaces is Kolmogorov's complements theorem: If a space contains a discontinuum, if $ M $ is the system of all closed subsets of this space and if $ \Phi $ is an arbitrary set-theoretic operation, then the complement of at least one set of the family $ \Phi ( M) $ does not belong to it [8], [5], [9]. The application to a given family $ M $ of sets of $ \delta $- $ \sigma $- operations $ \Phi $ and $ \Phi ^ {c} $ in alternation makes it possible to construct an increasing transfinite sequence of classes $ M _ {0} = M , M _ {1} \dots M _ \alpha \dots $ $ \alpha < \omega _ {1} $, which satisfies the Kolmogorov theorem on non-emptyness of classes: If $ \Phi $ is a normal $ \delta $- $ \sigma $- operation of greater cardinality than the operation of countable union (or of countable intersection), while $ M $ is the family of all closed subsets of a metric space containing a discontinuum, then all the classes $ M _ \alpha $, $ \alpha < \omega _ {1} $, generated by the operation $ \Phi $ from the family $ M $ are pairwise different. Here, a $ \delta $- $ \sigma $- operation $ \Phi $ is considered to be of greater cardinality than a $ \delta $- $ \sigma $- operation $ \Psi $ if $ \Phi ( M) \supseteq \Psi ( M) $ for any family $ M $ of sets [8], [5]. If $ \Phi = \cup _ {1} ^ \infty $( or $ \cap _ {1} ^ \infty $), then the classes $ M _ \alpha $, $ \alpha < \omega _ {1} $, generated by the operation $ \Phi $ on the family $ M $ represent the classes of $ B $- sets generated by the family $ M $( the Hausdorff classification). In a similar manner, an $ {\mathcal A} $- operation generates classes $ M _ \alpha $, $ \alpha < \omega _ {1} $, of $ C $- sets (Luzin sets, cf. Luzin set) out of the family $ M $ of Borel sets. All $ C $- sets are measurable and have the Baire property. All $ C $- sets form part of the class $ ( B _ {2} ) $, but do not exhaust it.

The concept of separation [4], introduced by Luzin, plays a highly important part in descriptive set theory. The first separation principle: Any two non-intersecting $ {\mathcal A} $- sets are $ ( B) $ separable. The second separation principle: If $ E $ and $ P $ are two $ {\mathcal A} $- sets (or $ C {\mathcal A} $- sets), then the sets $ E \setminus P $ and $ P \setminus E $ are ( $ C {\mathcal A} $) separable. There exists two $ C {\mathcal A} $- sets which are not $ ( B) $ separable. The problem of separation of second-class projective sets was solved by Novikov [4] and its separation principles are invertible: they are obtained from the respective theorems for projective sets of the first class by replacing $ ( {\mathcal A} ) $ by $ ( C {\mathcal A} _ {2} ) $, $ ( C {\mathcal A} ) $ by $ ( {\mathcal A} _ {2} ) $ and $ ( B) $ by $ ( B _ {2} ) $. Novikov [4] also solved the separation problem in the class of $ C $- sets (see also [3]). He also generalized the concept of separation of sets to include the concept of simultaneous or multiple separation of sets, as well as the principle of equality of indices [4], which is a principal instrument in proving the theorems on multiple separation.

An important stage in the development of descriptive set theory was the solution of the uniformization problem. A set $ P $ uniformizes a set $ E \subset X \times Y $ if $ P \subset E $, if $ P $ has the same projection on $ X $ as does $ E $ and if it is projected on $ X $ in a one-to-one manner. All $ B $- sets are uniformized by $ C {\mathcal A} $- sets. The process of effective selection of a point [4] in a non-empty $ C {\mathcal A} $- set yielded a stronger result: All $ C {\mathcal A} $- sets are uniformized by a $ C {\mathcal A} $- set. Any $ {\mathcal A} $- set is uniformized by a set of type $ {\mathcal A} _ {\rho \sigma \theta } $[3], [10]. There exists an $ {\mathcal A} $- set in the Euclidean plane which is not uniformized either by an $ {\mathcal A} $- set or by a $ C {\mathcal A} $- set (see, for example, [11]). The problem of the conditions under which a $ B $- set can be uniformized by a $ B $- set can be most generally answered as follows: Any plane $ B $- set intersecting the straight lines $ x = {\textrm{ const } } $ in $ F _ \sigma $- sets is uniformized by a $ B $- set. The problem of uniformization arose in solving the problem of implicit $ B $- functions [3]. Other problems arose at the same time: the nature of projections of $ B $- sets, splitting of sets, covering of sets, and the nature of the set of all projection points of a given $ B $- set $ E $ whose pre-images (in intersection with $ E $) display a certain given property. The following theorems [3] give some idea of the second and third problems: a $ B $- set with a countable-to-multiple projection is the union of a countable number of uniform $ B $- sets and, for any two such sets, one of them will lie beneath the other (splitting theorem of a $ B $- set); any $ {\mathcal A} $- set with a countable-to-multiple projection is contained in some $ B $- set with this property (covering theorem of an $ {\mathcal A} $- set).

In addition to the Lebesgue and Hausdorff classification of $ B $- sets, there is also their classification according to Luzin–de la Vallée Poussin. In this classification, the structure of sets of a given class $ K _ \alpha $, $ \alpha < \omega _ {1} $, is studied by means of sets which can be represented as an intersection but not as a union of a countable number of sets of classes $ < \alpha $; these sets are said to be elements of class $ \alpha $. Any set of class $ K _ \alpha $ is the union of a countable number of pairwise non-intersecting elements of classes $ \leq \alpha $. Each class $ K _ \alpha $ can be subdivided into subclasses $ K _ \alpha ^ \beta $, $ \beta < \omega _ {1} $, each class containing subclasses with numbers $ \beta < \omega _ {1} $ which may be arbitrarily large. Since each set of class $ \alpha $ consists of elements, the problem arose of studying the elements themselves; in particular, of the presence in each class $ K _ \alpha $ of a basic topological type of elements, to be called canonical, such that each element of class $ \alpha $ may be represented as the union of a countable number of canonical elements of classes $ \leq \alpha $( everything being considered in the space $ \mathbf I $ of irrational numbers). The first class includes canonical elements of two types: a one-point set and a topological image of a perfect Cantor set. Each element in the second class [12] is the union of a canonical element of class 2, which is a set homeomorphic to the space $ \mathbf I $, and a set of class $ \leq 1 $. Canonical elements of the third class have also been found; these canonical elements have been constructed by Baire [3]. The problem of existence of canonical elements of higher classes, which was very difficult, was solved by L.V. Keldysh [13], who proved that canonical elements exist in each class $ \alpha < \omega _ {1} $ and clarified their structure. Each element of class $ \alpha > 2 $ is the union of one canonical element of class $ \alpha $ with at most a countable number of sets of classes $ < \alpha $. Yet another difficult problem in this field is connected with the construction of arithmetical examples of $ B $- sets of lower classes. Baire [3] gave such an example for the class 3. Keldysh [13] gave arithmetical examples of elements of all finite classes (see also [3]), and pointed to the possibility, in principle, of constructing such examples for classes $ \alpha \geq \omega _ {0} $.

An important part in descriptive set theory is played by the Lavrent'ev theorem on the extension of homeomorphisms [9]: Let $ X $ and $ Y $ be complete metric spaces, let $ A \subset X $, $ B \subset Y $ and let $ f : A \rightarrow B $ be a homeomorphism; then there exists an extension of $ f $ to a homeomorphism of two $ G _ \delta $- subsets of these spaces. This theorem readily leads to the theorem of topological invariance [9]: Let $ \mathfrak B $ be a system of closed sets and let $ \Phi $ be a $ \delta $- $ \sigma $- operation such that intersection of a $ \Phi ( \mathfrak B ) $- set (i.e. of a set of the family $ \Phi ( \mathfrak B ) $) with a $ G _ \delta $- set is again a $ \Phi ( \mathfrak B ) $- set; then each $ \Phi ( \mathfrak B ) $- subset of a complete metric space is a $ \Phi ( \mathfrak B ) $- set in any metric space in which it is topologically contained. In this theorem, $ \mathfrak B $ may be replaced by a system $ \mathfrak A $ of open sets. Thus, $ \Phi ( \mathfrak B ) $- sets for which $ \Phi $ satisfies the above condition and which form part of complete metric spaces are absolute $ \Phi ( \mathfrak B ) $- sets, and the same applies to $ \Phi ( \mathfrak A ) $- sets (as regards the absolute nature in the class of metric spaces). In a number of special cases, such as $ C {\mathcal A} $- sets [7] ( $ \Phi $ is a $ \Gamma $- operation), this result has been established without having recourse to Lavrent'ev's theorem. Any complete metric space is an absolute $ G _ \delta $. Any metrizable absolute $ G _ \delta $ is homeomorphic to some complete metric space (the Aleksandrov–Hausdorff theorem [9]).

The following Aleksandrov–Urysohn theorem on the topological characterization of the space of irrational numbers is valid: Each zero-dimensional metric space $ X $ with a countable base which has no points of local compactness and which is an absolute $ G _ \delta $, is homeomorphic to the space $ \mathbf I $. Since $ \mathbf I $ is an absolute $ G _ \delta $ and has all the other properties of the space $ X $, it follows that the properties of $ X $ listed in the theorem represent a full topological characterization of $ \mathbf I $. This characterization led to the following result [14]: Any metric space which is a continuous image of $ \mathbf I $( and thus, an absolute $ {\mathcal A} $- set) is also a quotient image of $ \mathbf I $. One may also quote the following related results: A non-empty separable metric space is a continuous open image of $ \mathbf I $ if and only if it is an absolute $ G _ \delta $[15]; here, "open" may be replaced by "closed" . The concept of a $ B $- measurable mapping or a $ B $- function, in particular, of a $ B $- measurable mapping of class $ \alpha $, is a generalization of a continuous mapping; the concepts of a generalized homeomorphism of class $ ( \alpha , \beta ) $ and of a $ B $- isomorphism are generalizations of a homeomorphism. For such mappings see [6].

In formulating the results, the class of spaces to which they are applicable is usually not specified. This is explained by the fact that most of the classical results were obtained for subsets of $ \mathbf I $, but almost-all of them (save specified exceptions) remain valid if $ \mathbf I $ is replaced by any separable absolute $ G _ \delta $( in particular, by a complete metric space with a countable base). Further developments in descriptive set theory involved the generalization of the classical results to include the following cases: 1) complete metric spaces (not necessarily separable); 2) perfectly-normal topological spaces, including, in particular, compact Hausdorff spaces; and 3) general topological spaces. Even in the first case the generalization of the classical theory encounters serious difficulties, and is frequently altogether impossible. A.H. Stone [16] considered the generalization of the theory of $ B $- sets and $ {\mathcal A} $- sets to include this case.

The class of perfectly-normal spaces is a class outside which the important fact that the system of $ B $- sets ( $ {\mathcal A} $- sets) generated by the closed sets of the given space coincides with the system of $ B $- sets ( $ {\mathcal A} $- sets) generated by the open sets of this space, is no longer true. The following important theorem on non-emptiness of classes [11] is valid: In any uncountable perfectly-normal compact Hausdorff space there exists for each class $ \alpha < \omega _ {1} $ a $ B $- set of class $ \alpha $ which is not a $ B $- set of class $ < \alpha $.

The problem of uniformization has become a partial case of the general problem on the section of a multi-valued mapping (cf. Section of a mapping).

The modern development of descriptive set theory in general topological spaces (third case) is connected with the needs of other domains of mathematics (e.g. potential theory). For more details see [17] (in which there is an extensive bibliography).

The ideas and methods of descriptive set theory had a profound effect on the development of several domains in mathematics: analysis, the theory of functions, topology, mathematical logic, etc.

References

[1]	P.S. [P.S. Aleksandrov] Aleksandroff, "Sur la puissance des ensembles mesurables $B$" C.R. Acad. Sci. Paris , 162 (1916) pp. 323–325
[2]	M.Ya. [M.Ya. Suslin] Souslin, "Sur une définition des ensembles mesurables $B$ sans nombres transfinis" C.R. Acad. Sci. Paris , 164 (1917) pp. 88–90
[3]	N.N. [N.N. Luzin] Lusin, "Leçons sur les ensembles analytiques et leurs applications" , Gauthier-Villars (1930)
[4]	A.A. Lyapunov, "On P.S. Novikov's work in the field of descriptive set theory" Proc. Steklov Inst. Math. , 33 (1973) pp. 9–20 Trudy Mat. Inst. Steklov. , 133 (1973) pp. 11–22
[5]	Yu.S. Ochan, "The theory of operations over sets" Uspekhi Mat. Nauk , 10 : 3 (1955) pp. 71–128 (In Russian)
[6]	K. Kuratowski, "Topology" , 1 , PWN & Acad. Press (1966) (Translated from French)
[7]	P.S. Aleksandrov, Fund. Math. , 5 (1924) pp. 160–165
[8]	A.N. Kolmogorov, Mat. Sb. , 35 : 3–4 (1925) pp. 415–422
[9]	F. Hausdorff, "Grundzüge der Mengenlehre" , Leipzig (1914) (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))
[10]	A.A. [A.A. Lyapunov] Ljapunow, E.A. [E.A. Shchegolkov] Stschegolkow, W.J. [V.Ya. Arsenin] Arsenin, "Arbeiten zur deskriptiven Mengenlehre" , Deutsch. Verlag Wissenschaft. (1955) (Translated from Russian)
[11]	V.I. Ponomarev, "Borel sets in perfectly normal bicompacta" Soviet Math. Dokl. , 7 : 5 (1966) pp. 1236–12 Dokl. Akad. Nauk SSSR , 170 : 3 (1966) pp. 520–523
[12]	P.S. Aleksandrov, P.S. Urysohn, "Ueber nulldimensionalen Punktmengen" Math. Ann. , 98 (1927) pp. 89–106
[13]	L.V. Keldysh, Trudy Mat. Inst. Steklov. , 17 (1945) pp. 1–76
[14]	E. Michael, A.H. Stone, "Quotients of the space of irrationals" Pacific J. Math. , 28 : 3 (1969) pp. 629–633
[15]	A.V. Arkhangel'skii, "Open and near open mappings. Connections between spaces" Trans. Moscow Math. Soc. , 15 (1966) pp. 204–250 Trudy Moskov. Mat. Obshch. , 15 (1966) pp. 181–223
[16]	A.H. Stone, "Non-separable Borel sets II" General Topology and its Applications , 2 (1972) pp. 249–270
[17]	Z. Frolik, "A survey of separable descriptive theory of sets and spaces" Czechoslovak. Math. , 20 (1970) pp. 406–467

Comments

First some remarks on a supplementary list of references are presented, then precisions on the various commonly used terminologies and notations, and some complementation to the matter of the article, in which in particular three major events which took place during "modern times" are touched upon: the linkage to the foundational issues of modern set theory, the maturation of a powerful effective descriptive set theory, and the opening of a large field of applications to analysis.

Concerning the classical period (roughly from 1917 to 1945), one may consult in addition to [3], [6], [9], and [10], reference [a1], which is a marvellous long dictionary article.

For the modern period one can add [a2]–[a11]. [a2], [a3], [a4], [a5], which all stay at the level of the first separation theorem, are useful for their numerous applications to other fields. [a10] discusses most of the aspects of the theory: the classical one with its extensions ( $ \kappa $- analytic sets, various topological settings), and the effective one (see also [a11]). [a9] is a modern reference book, more directed to foundations than to applications: it covers in detail most of the classical and effective theories. [a6] is an excellent book in logic, which contains among many topics a chapter on descriptive set theory. [a8], in which some "generalized sieve" problems are solved, reveals the superiority of the effective methods over the classical ones. Finally [a7] is a recent example of what the modern theory can do in analysis.

Now follow some important remarks about terminology and notations in the West:

A topological Hausdorff space homeomorphic to a complete metric separable space (i.e., a regular absolute $ G _ \delta $ with countable base) is called a Polish space. Polish spaces have been and remain (in spite of generalizations) the natural frame of descriptive set theory. The fundamental Polish space $ \mathbf I $ of irrationals is homeomorphic to the Baire space $ \mathbf N ^ {\mathbf N} $( often denoted by $ \omega ^ \omega $ by the logicians who identify $ \mathbf N $ and the first infinite ordinal number $ \omega $).

Let $ {\mathcal N} $ be short for the Baire space $ \mathbf N ^ {\mathbf N} $. A collection $ {\mathcal C} $ of subsets of $ {\mathcal N} ^ {r} $ satisfies the reduction principle if for every pair $ A , B \in {\mathcal C} $ there are disjoint $ A ^ \prime , B ^ \prime \in {\mathcal C} $ such that $ A ^ \prime \subseteq A $, $ B ^ \prime \subseteq B $, $ A ^ \prime \cup B ^ \prime = A \cup B $. The collection $ {\mathcal C} $ satisfies the separation principle if for every pair of disjoint $ A , B \in {\mathcal C} $ there exists an $ E \in {\mathcal C} $ such that its complement $ C E $ is also in $ {\mathcal C} $ and $ A \subseteq E $, $ B \subseteq C E $.

The $ {\mathcal A} $- operation is also called Suslin operation or Suslin scheme, and its results on a class $ {\mathcal C} $ of sets are called the kernels of Suslin schemes on $ {\mathcal C} $. When the surrounding space is Polish, kernels of Suslin schemes on closed (or Borel) sets coincide with the continuous images of $ \mathbf I $. For an arbitrary space $ E $, the first construction gives "relative" analytic sets while the second one gives "absolute" ones. One generally uses "analytic" for one of the notions, and "Suslin" for the other; however, there are variations among the authors to decide which is which. Bourbaki [a2] made popular the notion of an absolute analytic (respectively, absolute Borel) space under the name of Suslin (respectively, Luzin) space; when one only considers the Borel structure of these spaces, one also finds Blackwell (respectively, standard) space.

To denote the classes of the Borel hierarchy in a space $ E $, one replaces more and more often the classical notations by the following ones: $ \Sigma _ \sim {} _ {1} ^ {0} $ denotes the class $ {\mathcal G} $ of open sets and $ \Pi _ \sim {} _ {1} ^ {0} $ the class $ {\mathcal F} $ of closed sets; $ \Sigma _ \sim {} _ {n} ^ {0} $ being defined, $ \Pi _ \sim {} _ {n} ^ {0} $ is its dual class (i.e. consists of the complements in $ E $ of the sets in $ \Sigma _ \sim {} _ {n} ^ {0} $) and $ \Sigma _ \sim {} _ {n+} 1 ^ {0} $ is the class of all countable unions of sets in $ \Pi _ \sim {} _ {n} ^ {0} $; finally $ \Delta _ \sim {} _ {n} ^ {0} $ is the ambiguous class $ \Sigma _ \sim {} _ {n} ^ {0} \cap \Pi _ \sim {} _ {n} ^ {0} $. So one has $ \Sigma _ \sim {} _ {2} ^ {0} = {\mathcal F} _ \sigma $, $ \Pi _ \sim {} _ {2} ^ {0} = {\mathcal G} _ \delta $, $ \Sigma _ \sim {} _ {3} ^ {0} = {\mathcal F} _ {\delta \sigma } $, $ \Pi _ \sim {} _ {3} ^ {0} = {\mathcal F} _ {\sigma \delta } $, etc. (cf. also Borel set of ambiguous class).

Similarly, for denoting the projective classes in a space $ E $ one uses the following notations: $ \Sigma _ \sim {} _ {1} ^ {1} $ denotes the class $ {\mathcal A} $ of analytic sets, projections on $ E $ of the $ \Pi _ \sim {} _ {1} ^ {0} $- subsets of $ E \times \mathbf N ^ {\mathbf N} $, whereas $ \Pi _ \sim {} _ {1} ^ {1} $ is the class $ C {\mathcal A} $ of co-analytic sets; $ \Sigma _ \sim {} _ {n} ^ {1} $ being defined, $ \Pi _ \sim {} _ {n} ^ {1} $ is its dual class and $ \Sigma _ \sim {} _ {n+} 1 ^ {1} $ is the class of projections on $ E $ of $ \Pi _ \sim {} _ {n} ^ {1} $ subsets of $ E \times \mathbf N ^ {\mathbf N} $; finally, $ \Delta _ \sim {} _ {n} ^ {1} $ denotes the class $ \Sigma _ \sim {} _ {n} ^ {1} \cap \Pi _ \sim {} _ {n} ^ {1} $. So one has $ \Sigma _ \sim {} _ {2} ^ {1} = P C {\mathcal A} $, $ \Pi _ \sim {} _ {2} ^ {1} = C P C {\mathcal A} $, $ \Delta _ \sim {} _ {2} ^ {1} = B _ {2} $, etc.

The letters $ \Sigma _ \sim $, $ \Pi _ \sim $, $ \Delta _ \sim $, denoting the classical classes of sets, are to be distinguished from the symbols $ \Sigma $, $ \Pi $, $ \Delta $ of their effective counterparts, which are now introduced (when $ n $ is a finite ordinal number). When $ E $ is Polish and is "reasonable" from the recursivity point of view (which is the case for all usual Polish spaces), one can distinguish inside $ E $ a countable family of simple open sets called effective or semi-recursive (or recursively enumerable in case $ E = \mathbf N $, cf. also Recursive set theory). This class, denoted by $ \Sigma _ {1} ^ {0} $, shares enough closure properties, so one can define, as above, the hierarchies $ \Sigma _ {n} ^ {i} $, $ \Pi _ {n} ^ {i} $, $ \Delta _ {n} ^ {i} $, of effective classes, the operation of countable union being replaced by projection along $ \mathbf N $. All these classes are countable. However, if one defines, for each $ \alpha \in \mathbf N ^ {\mathbf N} $, $ \Sigma _ {n} ^ {i} ( \alpha ) $ to be the class of all sets $ A $ in $ E $ which occur as sections at $ \alpha $ of a $ \Sigma _ {n} ^ {i} $- set in $ E \times \mathbf N ^ {\mathbf N} $, and similarly for $ \Pi _ {n} ^ {i} ( \alpha ) $ and $ \Delta _ {n} ^ {i} ( \alpha ) = \Sigma _ {n} ^ {i} ( \alpha ) \cap \Pi _ {n} ^ {i} ( \alpha ) $, these effective in $ \alpha $ classes, which share properties similar to those of the effective classes, are related to the classical classes by the equalities:

$$ \Sigma _ \sim {} _ {n} ^ {i} = \cup _ {\alpha \in \mathbf I } \Sigma _ {n} ^ {i} ( \alpha ) ,\ \Pi _ \sim {} _ {n} ^ {i} = \ \cup _ {\alpha \in \mathbf I } \Pi _ {n} ^ {i} ( \alpha ) ,\ {\Delta _ \sim } {} _ {n} ^ {i} = \ \cup _ {\alpha \in \mathbf I } \Delta _ {n} ^ {i} ( \alpha ) . $$

One then understands why the effective theory can be used to obtain "classical" results.

The classical part of descriptive set theory has been mainly created and developed by the Russian school between 1917 and 1945. However, during that period, major contributions to the subject have also come from the Polish and the Japanese school. Among the many members of the Polish school who worked on descriptive set theory, one must mention (at least): W. Sierpiński, among other things for his work with Luzin on the constituents of co-analytic sets (the Luzin–Sierpiński index is the model for the modern $ \Pi _ \sim {} _ {1} ^ {1} $- norms); K. Kuratowski, in particular for his work on logical definitions and for the reduction theorem, the modern form of the second separation theorem (for every sequence $ ( C _ {n} ) $ of $ \Pi _ \sim {} _ {1} ^ {1} $- sets there exists a sequence $ ( D _ {n} ) $ of disjoint $ \Pi _ \sim {} _ {1} ^ {1} $- sets with $ C _ {n} \supseteq D _ {n} $ and $ \cup C _ {n} = \cup D _ {n} $); W. Hurewicz, for his characterization of $ {\mathcal G} _ \delta $- sets among co-analytic sets, and of $ {\mathcal F} _ \sigma $- sets among analytic sets (the origin of many recent works) and for the first explicit natural examples of co-analytic non-Borel sets (the set of all countable compact subsets of $ [ 0 , 1 ] $ and the set of all compact subsets of the rationals of $ [ 0 , 1 ] $); finally, S. Mazurkiewicz, for his pioneering work on Polish spaces and his natural example of a co-analytic non-Borel set (the set of everywhere-differentiable functions on $ [ 0 , 1 ] $). From the more recent (and smaller in size) Japanese school one must mention: Kunugui, whose work on Borel sets in product spaces is, with those of Novikov and V.Ya. Arsenin, at the origin of [a8]; and especially Kondô, who proved in 1937 that every co-analytic set in a product can be uniformized by a co-analytic graph (a result which can also be derived from an earlier selection result of Novikov, as was proved in the 1960s by J.W. Addison, one of the logicians who linked the classical theory to the effective theory independently developed by S.C. Kleene on $ \mathbf N $).

All the important questions about projective sets which remained unsolved in the classical theory (cardinality of $ \Pi _ \sim {} _ {1} ^ {1} $- sets, measurability of projective sets, etc.) have received satisfactory answers during the last three decades: they cannot be solved within the usual framework of set theory, but are related to each other and can be solved "positively" by adding new and natural axioms. Proofs rely on one hand on the sophisticated tools of axiomatic set theory, Gödel's constructible universe and its inner models extensions, and the forcing method of P. Cohen, and, on the other hand, on a notion of infinite game which is now central in descriptive set theory (see [a9] for historical comments about this notion). In this canonical form, a game $ G $ is a subset of $ \mathbf N ^ {\mathbf N} $; in a run of the game, two players I and II alternately choose integers (knowing the previous choices) so that at the end of the run they produce an element $ \alpha $ of $ \mathbf N ^ {\mathbf N} $; I wins the run if $ \alpha $ belongs to $ G $. Otherwise I loses; the game $ G $ is determined if one of the players has a winning strategy. The Gale–Stewart theorem, which is easy but fundamental, asserts that all closed (or open) games are determined; it allows one to easily prove the second separation theorem and (cleverly used) that uncountable analytic sets contain perfect subsets. The difficult Martin theorem asserts that all Borel games are determined. On the other hand, one cannot prove in the usual Zermelo–Fraenkel system of axioms ZFC that analytic games are determined, and one is back to the problems unsolvable in ZFC alone (cf. [a9] and [a8] for most of the following results), the surrounding spaces being Polish:

a) The statement "every countable P~11-set contains a perfect subset" , which is false in Gödel's constructible universe, is equivalent to "every S~31-set is measurable" and to "the constituents of a co-analytic non-Borel set are unbounded in Baire class" ; it follows from "all analytic games are determined" , which is equivalent to the "there is only one analytic non-Borel set, up to Borel isomorphism" and which follows from the existence of a measurable cardinal.

b) In Gödel's constructible universe there are $ \Delta _ \sim {} _ {2} ^ {1} $ non-measurable sets or sets without the Baire property. However, every provably in ZFC $ \Delta _ \sim {} _ {2} ^ {1} $- set is measurable and has the Baire property.

c) The axiom of projective determinacy, that all projective games are determined, which is equivalent to a "moderate" large cardinal axiom, implies that the classes $ \Sigma _ \sim {} _ {n} ^ {1} $( respectively, $ \Pi _ \sim {} _ {n+} 1 ^ {1} $) satisfy the separation property for odd $ n $, and the reduction and uniformization properties for even $ n $. Moreover, all projective sets are measurable, have the Baire property and, if uncountable, contain a perfect set.

The logicians who solved these historical problems also merged the classical theory and Kleene's recursion theory on $ \mathbf N $ into a unified effective descriptive set theory (in the frame of Polish spaces). The impact on the classical theory has been varied. First new concepts and techniques have been introduced and theorems proved with no meaning in the classical theory, but which allow one to prove classical-type results for which no classical-type proofs existed; e.g., every co-analytic equivalence relation with uncountably many classes admits a perfect set of pairwise inequivalent elements. Secondly, as said above, it used and developed the game-theoretic techniques, from the classical and effective points of view. Finally, even if one reduces it by neglecting its effective aspects, it allowed one to discover powerful techniques in the realm of the classical theory:

A) Because of Kleene's recursion theorem (cf. Recursion), universal sets are no longer useful only to get counter-examples, but have become fundamental objects. E.g., let $ \Phi $ be a uniformly analytic operation from $ E $ into $ F $, i.e. a mapping from $ \Sigma _ \sim {} _ {1} ^ {1} ( E) $ into $ \Sigma _ \sim {} _ {1} ^ {1} ( F ) $ such that, for all $ H $ in $ \Sigma _ \sim {} _ {1} ^ {1} ( E \times \mathbf N ^ {\mathbf N} ) $, the subset $ K $ of $ F \times \mathbf N ^ {\mathbf N} $ defined by $ ( x , \alpha ) \in K $ $ \iff $ $ x \in \Phi ( H _ \alpha ) $( where $ H _ \alpha $ is the section of $ H $ at $ \alpha \in \mathbf N ^ {\mathbf N} $) is analytic in $ F \times \mathbf N ^ {\mathbf N} $; it follows from Kleene's recursion theorem (and classical ingredients) that $ \Phi $ is increasing and satisfies the following generalization of the first separation theorem: If $ A $ is analytic in $ E $, $ C $ is co-analytic in $ F $ and $ \Phi ( A) $ is a subset of $ C $, there is a Borel set $ B $ with $ A \subseteq B $ and $ \Phi ( B) \subseteq C $.

B) By a sensible abstract understanding of various classical results (Luzin–Sierpiński index, Luzin sieves, Novikov's comparison lemma $ , . . . $), the use of countable ordinals has become both more general and much easier, allowing one to reduce an important part of the classical heritage in the statement "every well-founded analytic relation on setswell-founded analytic relation has a countable length of an analytic relation on setslength" (a particular case of the Kunen–Martin theorem). Used together with A), it allows one to prove that if $ \Phi $ is a uniformly analytic derivation on $ E $( i.e. a uniformly analytic operation from $ E $ into $ E $ such that $ \Phi ( A) \subseteq A $ for each analytic set $ A $), and if $ ( \Phi _ \xi ) _ {\xi < \aleph _ {1} } $ is the transfinite sequence of successive iterates, then i) for each analytic set $ A $, $ \widetilde \Phi ( A) = \cap _ {\xi < \aleph _ {1} } \Phi ^ \xi ( A) $ is analytic, and is the largest $ \Phi $- invariant subset of $ A $; ii) the operation $ \widetilde \Phi $ thus defined is uniformly analytic; and iii) if $ A $ is analytic, $ C $ is co-analytic and contains $ \widetilde \Phi ( A) $, then for some countable ordinal $ \xi $, $ C $ contains $ \Phi ^ \xi ( A) $.

Descriptive set theory has important applications in any branch of analysis using measure theory (probability theory, optimization, game theory), particularly in theories rich in exceptional sets (potential theory, stochastic analysis, Hausdorff measure; harmonic analysis), but also in some others (Banach space theory). These applications rely on the following results about analytic sets in Polish spaces:

1) the stability properties of $ \Sigma _ \sim {} _ {1} ^ {1} $ and the first separation theorem, together with the universal measurability, or the Baire property, of analytic sets;

2) the Jankov–von Neumann theorem, which says that any analytic set in a product can be uniformized by the graph of a universally measurable function (which is much stronger than uniformization by a universally measurable graph);

3) the Choquet theorem, which says that every analytic set is universally capacitable (cf. Capacity), and, more generally, the fact that capacities and analytic sets are intimately linked;

4) finally, the Kunen–Martin theorem (for analytic sets).

Probably the two quite recent theorems on analytic operations quoted just above, which include the first separation theorem, the exterior approximation results in capacity theory and the so-called Kunen–Martin theorem, will be powerful tools in functional analysis.

References

[a1]	W. Sierpiński, "Les ensembles projectifs et analytiques" , Gauthier-Villars (1950)
[a2]	N. Bourbaki, "Elements of mathematics. General topology" , 2 , Addison-Wesley (1966) (Translated from French)
[a3]	G. Choquet, "Outils topologiques et métriques de l'analyse mathématique" , Centre Docum. Univ. Paris (1969) (Rédigé par C. Mayer)
[a4]	J.P.R. Christensen, "Topology and Borel structure" , North-Holland (1977)
[a5]	C. Dellacherie, P.A. Meyer, "Probabilities and potential" , 1–3 , North-Holland (1978–1988) (Translated from French)
[a6]	J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1977) ((especially the article of D.A. Martin on Descriptive set theory))
[a7]	A.S. Kechris, A. Louveau, "Descriptive set theory and the structure of sets of uniqueness" , Cambridge Univ. Press (1988)
[a8]	A. Louveau, "Ensembles analytiques et boréliens dans les espaces produits" Astérique , 78 (1980)
[a9]	Y.N. Moschovakis, "Descriptive set theory" , North-Holland (1980)
[a10]	C.A. Rogers, J.E. Jayne, C. Dellacherie, F. Tøpsoe, J. Hoffman-Jørgensen, D.A. Martin, A.S. Kechris, A.H. Stone, "Analytic sets" , Acad. Press (1980)
[a11]	R. Mansfield, G. Veitkamp, "Recursive aspects of descriptive set theory" , Oxford Univ. Press (1985)
[a12]	D.A. Martin, "Descriptive set theory: projective sets" J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1977) pp. 783–815
[a13]	T.J. Jech, "Set theory" , Acad. Press (1978) pp. Chapt. 7 (Translated from German)