Namespaces
Variants
Actions

Difference between revisions of "Descriptive set theory"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (→‎References: latexify)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d0313802.png" />-sets (cf. [[Borel set|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 classes]]; [[Baire theorem|Baire theorem]]). Lebesgue showed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d0313803.png" />-sets are identical to Lebesgue sets of Baire functions (cf. [[Lebesgue set|Lebesgue set]]), gave the first classification of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d0313804.png" />-sets and showed that none of its classes was empty.
+
<!--
 +
d0313802.png
 +
$#A+1 = 407 n = 2
 +
$#C+1 = 407 : ~/encyclopedia/old_files/data/D031/D.0301380 Descriptive set theory
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
The study of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d0313805.png" />-sets became an important task of descriptive set theory, and the first such problem was the cardinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d0313806.png" />-sets. After the introduction of the [[Lebesgue measure|Lebesgue measure]] it was found that the class of measurable sets is much wider than the class of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d0313807.png" />-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.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
One of the most important problems, viz. the problem of the cardinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d0313808.png" />-sets, was solved by P.S. Aleksandrov [[#References|[1]]] in 1916, who constructed the [[A-operation|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d0313809.png" />-operation]] for this purpose. He showed that the use of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138010.png" />-operation, while taking intervals as the starting point, makes it possible to construct any desired <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138011.png" />-set, and that any uncountable set obtained by way of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138012.png" />-operation (and called an [[A-set|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138013.png" />-set]]) contains a [[Perfect set|perfect set]] and thus has the cardinality of the continuum. This result was also independently obtained by F. Hausdorff. M.Ya. Suslin [[#References|[2]]] showed that there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138014.png" />-set which is not a Borel set. He also introduced the name <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138015.png" />-set and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138016.png" />-operation, in honour of Aleksandrov. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138017.png" />-sets are also known as Suslin sets, or as analytic sets (cf. [[Analytic set|Analytic set]]). For an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138018.png" />-set to be a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138019.png" />-set it is necessary and sufficient: 1) for its complement to be again an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138020.png" />-set (the [[Suslin criterion|Suslin criterion]]); or 2) for it to be the result of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138021.png" />-operation with non-intersecting components (the [[Luzin criterion|Luzin criterion]]). All <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138022.png" />-sets are measurable and display the [[Baire property|Baire property]]. The following new methods for obtaining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138023.png" />-sets, equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138024.png" />-operations, were found: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138025.png" />-sets are projections of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138026.png" />-sets (and even of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138027.png" />-sets); <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138028.png" />-sets are continuous images of the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138029.png" /> of irrational numbers; and, as a consequence, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138030.png" />-sets are continuous images of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138031.png" />-sets [[#References|[3]]]. At the same time, a continuous one-to-one (and even a countably-to-multiple [[#References|[4]]]) image of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138032.png" />-set is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138033.png" />-set, and any uncountable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138034.png" />-set is the union of an at most countable set and a one-to-one continuous image of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138035.png" /> [[#References|[3]]]. Finally, Luzin found yet another important way of defining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138036.png" />-sets with the aid of his sieve operation (cf. [[Luzin sieve|Luzin sieve]]). Transfinite sieve indices and constituents have become a powerful tool in the study of the properties of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138037.png" />-sets and their complements: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138038.png" />-sets (cf. [[CA-set|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138039.png" />-set]]).
+
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|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 classes]]; [[Baire theorem|Baire theorem]]). Lebesgue showed that  $  B $-
 +
sets are identical to Lebesgue sets of Baire functions (cf. [[Lebesgue set|Lebesgue set]]), gave the first classification of $  B $-
 +
sets and showed that none of its classes was empty.
  
In the course of his studies on the cardinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138040.png" />-sets, Luzin introduced projective sets (cf. [[Projective set|Projective set]]). Each class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138041.png" /> of projective sets contains sets which do not belong to classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138042.png" /> [[#References|[3]]], [[#References|[5]]]. The concept of a [[Universal set|universal set]] [[#References|[3]]], [[#References|[6]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138043.png" />-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 [[#References|[4]]]: There exists an uncountable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138044.png" />-set for which the assumption that it contains no perfect subset is not self-contradictory; there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138045.png" />-set for which the assumption that it is non-measurable is not self-contradictory.
+
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|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.
  
The introduction by Aleksandrov [[#References|[7]]] of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138047.png" />-operation, which is complementary to the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138048.png" />-operation, was the first step in the development of A.N. Kolmogorov's [[#References|[8]]] and Hausdorff's [[#References|[9]]] general theory of set-theoretic operations; however, the fundamental class of operations is constituted by positive set-theoretic operations, or the so-called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138049.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138050.png" />-operations. For each such [[Delta-sigma-operation|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138051.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138052.png" />-operation]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138053.png" /> a complementary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138054.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138055.png" />-operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138056.png" /> was defined and the formula
+
One of the most important problems, viz. the problem of the cardinality of  $  B $-
 +
sets, was solved by P.S. Aleksandrov [[#References|[1]]] in 1916, who constructed the [[A-operation| $  {\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 [[A-set| $  {\mathcal A} $-
 +
set]]) contains a [[Perfect set|perfect set]] and thus has the cardinality of the continuum. This result was also independently obtained by F. Hausdorff. M.Ya. Suslin [[#References|[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|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|Suslin criterion]]); or 2) for it to be the result of an  $  {\mathcal A} $-
 +
operation with non-intersecting components (the [[Luzin criterion|Luzin criterion]]). All  $  {\mathcal A} $-
 +
sets are measurable and display the [[Baire property|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 [[#References|[3]]]. At the same time, a continuous one-to-one (and even a countably-to-multiple [[#References|[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 $[[#References|[3]]]. Finally, Luzin found yet another important way of defining  $  {\mathcal A} $-
 +
sets with the aid of his sieve operation (cf. [[Luzin sieve|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. [[CA-set| $  C {\mathcal A} $-
 +
set]]).
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138057.png" /></td> </tr></table>
+
In the course of his studies on the cardinality of  $  C {\mathcal A} $-
 +
sets, Luzin introduced projective sets (cf. [[Projective set|Projective set]]). Each class  $  \alpha $
 +
of projective sets contains sets which do not belong to classes  $  < \alpha $[[#References|[3]]], [[#References|[5]]]. The concept of a [[Universal set|universal set]] [[#References|[3]]], [[#References|[6]]], [[#References|[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 [[#References|[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.
  
which may be considered as the definition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138058.png" />, was given. The concept of a normal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138059.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138060.png" />-operation (for any family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138061.png" /> of sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138062.png" /> [[#References|[8]]]) was also introduced. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138063.png" />-operation and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138064.png" />-operation are mutually complementary normal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138065.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138066.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138067.png" /> is the system of all closed subsets of this space and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138068.png" /> is an arbitrary set-theoretic operation, then the complement of at least one set of the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138069.png" /> does not belong to it [[#References|[8]]], [[#References|[5]]], [[#References|[9]]]. The application to a given family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138070.png" /> of sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138071.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138072.png" />-operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138073.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138074.png" /> in alternation makes it possible to construct an increasing transfinite sequence of classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138075.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138076.png" />, which satisfies the Kolmogorov theorem on non-emptyness of classes: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138077.png" /> is a normal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138078.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138079.png" />-operation of greater cardinality than the operation of countable union (or of countable intersection), while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138080.png" /> is the family of all closed subsets of a metric space containing a discontinuum, then all the classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138081.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138082.png" />, generated by the operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138083.png" /> from the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138084.png" /> are pairwise different. Here, a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138085.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138086.png" />-operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138087.png" /> is considered to be of greater cardinality than a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138088.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138089.png" />-operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138090.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138091.png" /> for any family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138092.png" /> of sets [[#References|[8]]], [[#References|[5]]]. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138093.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138094.png" />), then the classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138095.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138096.png" />, generated by the operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138097.png" /> on the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138098.png" /> represent the classes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d03138099.png" />-sets generated by the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380100.png" /> (the Hausdorff classification). In a similar manner, an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380102.png" />-operation generates classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380103.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380104.png" />, of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380105.png" />-sets (Luzin sets, cf. [[Luzin set|Luzin set]]) out of the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380106.png" /> of Borel sets. All <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380107.png" />-sets are measurable and have the Baire property. All <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380108.png" />-sets form part of the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380109.png" />, but do not exhaust it.
+
The introduction by Aleksandrov [[#References|[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 [[#References|[8]]] and Hausdorff's [[#References|[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| $  \delta $-
 +
$  \sigma $-
 +
operation]] $  \Phi $
 +
a complementary  $  \delta $-
 +
$  \sigma $-
 +
operation  $  \Phi  ^ {c} $
 +
was defined and the formula
  
The concept of separation [[#References|[4]]], introduced by Luzin, plays a highly important part in descriptive set theory. The first separation principle: Any two non-intersecting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380110.png" />-sets are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380111.png" /> separable. The second separation principle: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380112.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380113.png" /> are two <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380114.png" />-sets (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380115.png" />-sets), then the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380116.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380117.png" /> are (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380118.png" />) separable. There exists two <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380119.png" />-sets which are not <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380120.png" /> separable. The problem of separation of second-class projective sets was solved by Novikov [[#References|[4]]] and its separation principles are invertible: they are obtained from the respective theorems for projective sets of the first class by replacing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380121.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380122.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380123.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380124.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380125.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380126.png" />. Novikov [[#References|[4]]] also solved the separation problem in the class of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380127.png" />-sets (see also [[#References|[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 [[#References|[4]]], which is a principal instrument in proving the theorems on multiple separation.
+
$$
 +
\Phi  ^ {c} ( \{ E _ {n} \} ) = \
 +
C [ \Phi ( \{ C E _ {n} \} ) ] ,
 +
$$
  
An important stage in the development of descriptive set theory was the solution of the uniformization problem. A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380128.png" /> uniformizes a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380129.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380130.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380131.png" /> has the same projection on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380132.png" /> as does <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380133.png" /> and if it is projected on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380134.png" /> in a one-to-one manner. All <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380135.png" />-sets are uniformized by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380136.png" />-sets. The process of effective selection of a point [[#References|[4]]] in a non-empty <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380137.png" />-set yielded a stronger result: All <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380138.png" />-sets are uniformized by a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380139.png" />-set. Any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380140.png" />-set is uniformized by a set of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380141.png" /> [[#References|[3]]], [[#References|[10]]]. There exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380142.png" />-set in the Euclidean plane which is not uniformized either by an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380143.png" />-set or by a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380144.png" />-set (see, for example, [[#References|[11]]]). The problem of the conditions under which a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380145.png" />-set can be uniformized by a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380146.png" />-set can be most generally answered as follows: Any plane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380147.png" />-set intersecting the straight lines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380148.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380149.png" />-sets is uniformized by a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380150.png" />-set. The problem of uniformization arose in solving the problem of implicit <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380151.png" />-functions [[#References|[3]]]. Other problems arose at the same time: the nature of projections of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380152.png" />-sets, splitting of sets, covering of sets, and the nature of the set of all projection points of a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380153.png" />-set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380154.png" /> whose pre-images (in intersection with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380155.png" />) display a certain given property. The following theorems [[#References|[3]]] give some idea of the second and third problems: a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380156.png" />-set with a countable-to-multiple projection is the union of a countable number of uniform <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380157.png" />-sets and, for any two such sets, one of them will lie beneath the other (splitting theorem of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380159.png" />-set); any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380160.png" />-set with a countable-to-multiple projection is contained in some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380161.png" />-set with this property (covering theorem of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380163.png" />-set).
+
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) $[[#References|[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 [[#References|[8]]], [[#References|[5]]], [[#References|[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 [[#References|[8]]], [[#References|[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|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.
  
In addition to the Lebesgue and Hausdorff classification of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380164.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380165.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380166.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380167.png" />; these sets are said to be elements of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380169.png" />. Any set of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380170.png" /> is the union of a countable number of pairwise non-intersecting elements of classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380171.png" />. Each class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380172.png" /> can be subdivided into subclasses <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380173.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380174.png" />, each class containing subclasses with numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380175.png" /> which may be arbitrarily large. Since each set of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380176.png" /> consists of elements, the problem arose of studying the elements themselves; in particular, of the presence in each class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380177.png" /> of a basic topological type of elements, to be called canonical, such that each element of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380179.png" /> may be represented as the union of a countable number of canonical elements of classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380180.png" /> (everything being considered in the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380181.png" /> 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|Cantor set]]. Each element in the second class [[#References|[12]]] is the union of a canonical element of class 2, which is a set homeomorphic to the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380182.png" />, and a set of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380183.png" />. Canonical elements of the third class have also been found; these canonical elements have been constructed by Baire [[#References|[3]]]. The problem of existence of canonical elements of higher classes, which was very difficult, was solved by L.V. Keldysh [[#References|[13]]], who proved that canonical elements exist in each class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380184.png" /> and clarified their structure. Each element of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380185.png" /> is the union of one canonical element of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380186.png" /> with at most a countable number of sets of classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380187.png" />. Yet another difficult problem in this field is connected with the construction of arithmetical examples of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380188.png" />-sets of lower classes. Baire [[#References|[3]]] gave such an example for the class 3. Keldysh [[#References|[13]]] gave arithmetical examples of elements of all finite classes (see also [[#References|[3]]]), and pointed to the possibility, in principle, of constructing such examples for classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380189.png" />.
+
The concept of separation [[#References|[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 [[#References|[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 [[#References|[4]]] also solved the separation problem in the class of $  C $-
 +
sets (see also [[#References|[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 [[#References|[4]]], which is a principal instrument in proving the theorems on multiple separation.
  
An important part in descriptive set theory is played by the [[Lavrent'ev theorem|Lavrent'ev theorem]] on the extension of homeomorphisms [[#References|[9]]]: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380190.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380191.png" /> be complete metric spaces, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380192.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380193.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380194.png" /> be a homeomorphism; then there exists an extension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380195.png" /> to a homeomorphism of two <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380196.png" />-subsets of these spaces. This theorem readily leads to the theorem of topological invariance [[#References|[9]]]: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380197.png" /> be a system of closed sets and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380198.png" /> be a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380199.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380200.png" />-operation such that intersection of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380201.png" />-set (i.e. of a set of the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380202.png" />) with a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380203.png" />-set is again a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380204.png" />-set; then each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380205.png" />-subset of a complete metric space is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380206.png" />-set in any metric space in which it is topologically contained. In this theorem, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380207.png" /> may be replaced by a system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380208.png" /> of open sets. Thus, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380209.png" />-sets for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380210.png" /> satisfies the above condition and which form part of complete metric spaces are absolute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380211.png" />-sets, and the same applies to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380212.png" />-sets (as regards the absolute nature in the class of metric spaces). In a number of special cases, such as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380213.png" />-sets [[#References|[7]]] (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380214.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380215.png" />-operation), this result has been established without having recourse to Lavrent'ev's theorem. Any complete metric space is an absolute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380216.png" />. Any metrizable absolute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380217.png" /> is homeomorphic to some complete metric space (the Aleksandrov–Hausdorff theorem [[#References|[9]]]).
+
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 [[#References|[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 }  $[[#References|[3]]], [[#References|[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, [[#References|[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 [[#References|[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 [[#References|[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).
  
The following Aleksandrov–Urysohn theorem on the topological characterization of the space of irrational numbers is valid: Each zero-dimensional metric space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380218.png" /> with a countable base which has no points of local compactness and which is an absolute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380219.png" />, is homeomorphic to the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380220.png" />. Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380221.png" /> is an absolute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380222.png" /> and has all the other properties of the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380223.png" />, it follows that the properties of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380224.png" /> listed in the theorem represent a full topological characterization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380225.png" />. This characterization led to the following result [[#References|[14]]]: Any metric space which is a continuous image of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380226.png" /> (and thus, an absolute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380227.png" />-set) is also a quotient image of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380228.png" />. One may also quote the following related results: A non-empty separable metric space is a continuous open image of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380229.png" /> if and only if it is an absolute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380230.png" /> [[#References|[15]]]; here,  "open"  may be replaced by  "closed" . The concept of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380232.png" />-measurable mapping or a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380234.png" />-function, in particular, of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380237.png" />-measurable mapping of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380238.png" />, is a generalization of a continuous mapping; the concepts of a generalized homeomorphism of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380240.png" /> and of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380242.png" />-isomorphism are generalizations of a homeomorphism. For such mappings see [[#References|[6]]].
+
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|Cantor set]]. Each element in the second class [[#References|[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 [[#References|[3]]]. The problem of existence of canonical elements of higher classes, which was very difficult, was solved by L.V. Keldysh [[#References|[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 [[#References|[3]]] gave such an example for the class 3. Keldysh [[#References|[13]]] gave arithmetical examples of elements of all finite classes (see also [[#References|[3]]]), and pointed to the possibility, in principle, of constructing such examples for classes  $  \alpha \geq  \omega _ {0} $.
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380243.png" />, but almost-all of them (save specified exceptions) remain valid if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380244.png" /> is replaced by any separable absolute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380245.png" /> (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 [[#References|[16]]] considered the generalization of the theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380246.png" />-sets and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380247.png" />-sets to include this case.
+
An important part in descriptive set theory is played by the [[Lavrent'ev theorem|Lavrent'ev theorem]] on the extension of homeomorphisms [[#References|[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 [[#References|[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 [[#References|[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 [[#References|[9]]]).
  
The class of perfectly-normal spaces is a class outside which the important fact that the system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380248.png" />-sets (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380249.png" />-sets) generated by the closed sets of the given space coincides with the system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380250.png" />-sets (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380251.png" />-sets) generated by the open sets of this space, is no longer true. The following important theorem on non-emptiness of classes [[#References|[11]]] is valid: In any uncountable perfectly-normal compact Hausdorff space there exists for each class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380252.png" /> a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380253.png" />-set of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380254.png" /> which is not a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380255.png" />-set of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380256.png" />.
+
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 [[#References|[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  $[[#References|[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 [[#References|[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 [[#References|[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 [[#References|[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|Section of a mapping]]).
 
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|Section of a mapping]]).
Line 34: Line 284:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  P.S. [P.S. Aleksandrov] Aleksandroff,  "Sur la puissance des ensembles mésurables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380257.png" />"  ''C.R. Acad. Sci. Paris'' , '''162'''  (1916)  pp. 323–325</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  M.Ya. [M.Ya. Suslin] Souslin,  "Sur une définition des ensembles measurables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380258.png" /> sans nombres transfinis"  ''C.R. Acad. Sci. Paris'' , '''164'''  (1917)  pp. 88–90</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  N.N. [N.N. Luzin] Lusin,  "Leçons sur les ensembles analytiques et leurs applications" , Gauthier-Villars  (1930)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  Yu.S. Ochan,  "The theory of operations over sets"  ''Uspekhi Mat. Nauk'' , '''10''' :  3  (1955)  pp. 71–128  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  K. Kuratowski,  "Topology" , '''1''' , PWN &amp; Acad. Press  (1966)  (Translated from French)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  P.S. Aleksandrov,  ''Fund. Math.'' , '''5'''  (1924)  pp. 160–165</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  A.N. Kolmogorov,  ''Mat. Sb.'' , '''35''' :  3–4  (1925)  pp. 415–422</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  F. Hausdorff,  "Grundzüge der Mengenlehre" , Leipzig  (1914)  (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  P.S. Aleksandrov,  P.S. Urysohn,  "Ueber nulldimensionalen Punktmengen"  ''Math. Ann.'' , '''98'''  (1927)  pp. 89–106</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  L.V. Keldysh,  ''Trudy Mat. Inst. Steklov.'' , '''17'''  (1945)  pp. 1–76</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  E. Michael,  A.H. Stone,  "Quotients of the space of irrationals"  ''Pacific J. Math.'' , '''28''' :  3  (1969)  pp. 629–633</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  A.H. Stone,  "Non-separable Borel sets II"  ''General Topology and its Applications'' , '''2'''  (1972)  pp. 249–270</TD></TR><TR><TD valign="top">[17]</TD> <TD valign="top">  Z. Frolik,  "A survey of separable descriptive theory of sets and spaces"  ''Czechoslovak. Math.'' , '''20'''  (1970)  pp. 406–467</TD></TR></table>
+
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  P.S. [P.S. Aleksandrov] Aleksandroff,  "Sur la puissance des ensembles mesurables $B$"  ''C.R. Acad. Sci. Paris'' , '''162'''  (1916)  pp. 323–325</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  N.N. [N.N. Luzin] Lusin,  "Leçons sur les ensembles analytiques et leurs applications" , Gauthier-Villars  (1930)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  Yu.S. Ochan,  "The theory of operations over sets"  ''Uspekhi Mat. Nauk'' , '''10''' :  3  (1955)  pp. 71–128  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  K. Kuratowski,  "Topology" , '''1''' , PWN &amp; Acad. Press  (1966)  (Translated from French)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  P.S. Aleksandrov,  ''Fund. Math.'' , '''5'''  (1924)  pp. 160–165</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  A.N. Kolmogorov,  ''Mat. Sb.'' , '''35''' :  3–4  (1925)  pp. 415–422</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  F. Hausdorff,  "Grundzüge der Mengenlehre" , Leipzig  (1914)  (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  P.S. Aleksandrov,  P.S. Urysohn,  "Ueber nulldimensionalen Punktmengen"  ''Math. Ann.'' , '''98'''  (1927)  pp. 89–106</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  L.V. Keldysh,  ''Trudy Mat. Inst. Steklov.'' , '''17'''  (1945)  pp. 1–76</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  E. Michael,  A.H. Stone,  "Quotients of the space of irrationals"  ''Pacific J. Math.'' , '''28''' :  3  (1969)  pp. 629–633</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  A.H. Stone,  "Non-separable Borel sets II"  ''General Topology and its Applications'' , '''2'''  (1972)  pp. 249–270</TD></TR><TR><TD valign="top">[17]</TD> <TD valign="top">  Z. Frolik,  "A survey of separable descriptive theory of sets and spaces"  ''Czechoslovak. Math.'' , '''20'''  (1970)  pp. 406–467</TD></TR></table>
 
 
 
 
  
 
====Comments====
 
====Comments====
Line 43: Line 291:
 
Concerning the classical period (roughly from 1917 to 1945), one may consult in addition to [[#References|[3]]], [[#References|[6]]], [[#References|[9]]], and [[#References|[10]]], reference [[#References|[a1]]], which is a marvellous long dictionary article.
 
Concerning the classical period (roughly from 1917 to 1945), one may consult in addition to [[#References|[3]]], [[#References|[6]]], [[#References|[9]]], and [[#References|[10]]], reference [[#References|[a1]]], which is a marvellous long dictionary article.
  
For the modern period one can add [[#References|[a2]]]–[[#References|[a11]]]. [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], which all stay at the level of the first separation theorem, are useful for their numerous applications to other fields. [[#References|[a10]]] discusses most of the aspects of the theory: the classical one with its extensions (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380259.png" />-analytic sets, various topological settings), and the effective one (see also [[#References|[a11]]]). [[#References|[a9]]] is a modern reference book, more directed to foundations than to applications: it covers in detail most of the classical and effective theories. [[#References|[a6]]] is an excellent book in logic, which contains among many topics a chapter on descriptive set theory. [[#References|[a8]]], in which some  "generalized sieve"  problems are solved, reveals the superiority of the effective methods over the classical ones. Finally [[#References|[a7]]] is a recent example of what the modern theory can do in analysis.
+
For the modern period one can add [[#References|[a2]]]–[[#References|[a11]]]. [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], which all stay at the level of the first separation theorem, are useful for their numerous applications to other fields. [[#References|[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 [[#References|[a11]]]). [[#References|[a9]]] is a modern reference book, more directed to foundations than to applications: it covers in detail most of the classical and effective theories. [[#References|[a6]]] is an excellent book in logic, which contains among many topics a chapter on descriptive set theory. [[#References|[a8]]], in which some  "generalized sieve"  problems are solved, reveals the superiority of the effective methods over the classical ones. Finally [[#References|[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:
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380260.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380261.png" /> of irrationals is homeomorphic to the [[Baire space|Baire space]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380262.png" /> (often denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380263.png" /> by the logicians who identify <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380264.png" /> and the first infinite [[Ordinal number|ordinal number]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380265.png" />).
+
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|Baire space]] $  \mathbf N  ^ {\mathbf N} $(
 +
often denoted by $  \omega  ^  \omega  $
 +
by the logicians who identify $  \mathbf N $
 +
and the first infinite [[Ordinal number|ordinal number]] $  \omega $).
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380266.png" /> be short for the Baire space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380267.png" />. A collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380268.png" /> of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380269.png" /> satisfies the reduction principle if for every pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380270.png" /> there are disjoint <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380271.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380272.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380273.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380274.png" />. The collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380275.png" /> satisfies the separation principle if for every pair of disjoint <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380276.png" /> there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380277.png" /> such that its complement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380278.png" /> is also in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380279.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380280.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380281.png" />.
+
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 [[A-operation|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380282.png" />-operation]] is also called Suslin operation or Suslin scheme, and its results on a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380283.png" /> of sets are called the kernels of Suslin schemes on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380284.png" />. When the surrounding space is Polish, kernels of Suslin schemes on closed (or Borel) sets coincide with the continuous images of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380285.png" />. For an arbitrary space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380286.png" />, 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 [[#References|[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.
+
The [[A-operation| $  {\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 [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380287.png" />, one replaces more and more often the classical notations by the following ones: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380288.png" /> denotes the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380289.png" /> of open sets and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380290.png" /> the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380291.png" /> of closed sets; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380292.png" /> being defined, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380293.png" /> is its dual class (i.e. consists of the complements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380294.png" /> of the sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380295.png" />) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380296.png" /> is the class of all countable unions of sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380297.png" />; finally <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380298.png" /> is the ambiguous class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380299.png" />. So one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380300.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380301.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380302.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380303.png" />, etc. (cf. also [[Borel set of ambiguous class|Borel set of ambiguous class]]).
+
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|Borel set of ambiguous class]]).
  
Similarly, for denoting the projective classes in a space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380304.png" /> one uses the following notations: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380305.png" /> denotes the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380306.png" /> of analytic sets, projections on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380307.png" /> of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380308.png" />-subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380309.png" />, whereas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380310.png" /> is the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380311.png" /> of co-analytic sets; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380312.png" /> being defined, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380313.png" /> is its dual class and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380314.png" /> is the class of projections on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380315.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380316.png" /> subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380317.png" />; finally, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380318.png" /> denotes the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380319.png" />. So one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380320.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380321.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380322.png" />, etc.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380323.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380324.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380325.png" />, denoting the classical classes of sets, are to be distinguished from the symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380326.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380327.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380328.png" /> of their effective counterparts, which are now introduced (when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380329.png" /> is a finite [[Ordinal number|ordinal number]]). When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380330.png" /> is Polish and is  "reasonable"  from the recursivity point of view (which is the case for all usual Polish spaces), one can distinguish inside <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380331.png" /> a countable family of simple open sets called effective or semi-recursive (or recursively enumerable in case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380332.png" />, cf. also [[Recursive set theory|Recursive set theory]]). This class, denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380333.png" />, shares enough closure properties, so one can define, as above, the hierarchies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380334.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380335.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380336.png" />, of effective classes, the operation of countable union being replaced by projection along <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380337.png" />. All these classes are countable. However, if one defines, for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380338.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380339.png" /> to be the class of all sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380340.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380341.png" /> which occur as sections at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380342.png" /> of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380343.png" />-set in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380344.png" />, and similarly for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380345.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380346.png" />, these effective in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380348.png" /> classes, which share properties similar to those of the effective classes, are related to the classical classes by the equalities:
+
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|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|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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380349.png" /></td> </tr></table>
+
$$
 +
\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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380350.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380351.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380352.png" />-sets there exists a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380353.png" /> of disjoint <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380354.png" />-sets with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380355.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380356.png" />); W. Hurewicz, for his characterization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380357.png" />-sets among co-analytic sets, and of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380358.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380359.png" /> and the set of all compact subsets of the rationals of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380360.png" />); 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380361.png" />). 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 [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380362.png" />).
+
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 [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380363.png" />-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|axiomatic set theory]], Gödel's constructible universe and it's inner models extensions (cf. [[Gödel constructive set|Gödel constructive set]]), and the [[Forcing method|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 [[#References|[a9]]] for historical comments about this notion). In this canonical form, a game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380364.png" /> is a subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380365.png" />; 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380366.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380367.png" />; I wins the run if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380368.png" /> belongs to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380369.png" />. Otherwise I loses; the game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380370.png" /> 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. [[#References|[a9]]] and [[#References|[a8]]] for most of the following results), the surrounding spaces being Polish:
+
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|axiomatic set theory]], Gödel's [[constructible universe]] and its inner models extensions, and the [[Forcing method|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 [[#References|[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. [[#References|[a9]]] and [[#References|[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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380371.png" /> non-measurable sets or sets without the [[Baire property|Baire property]]. However, every provably in ZFC <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380372.png" />-set is measurable and has the Baire property.
+
b) In Gödel's constructible universe there are $  \Delta _  \sim  {} _ {2}  ^ {1} $
 +
non-measurable sets or sets without the [[Baire property|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380373.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380374.png" />) satisfy the separation property for odd <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380375.png" />, and the reduction and uniformization properties for even <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380376.png" />. Moreover, all projective sets are measurable, have the Baire property and, if uncountable, contain a perfect set.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380377.png" /> 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:
+
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|Recursion]]), universal sets are no longer useful only to get counter-examples, but have become fundamental objects. E.g., let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380378.png" /> be a uniformly analytic operation from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380379.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380380.png" />, i.e. a mapping from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380381.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380382.png" /> such that, for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380383.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380384.png" />, the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380385.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380386.png" /> defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380387.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380388.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380389.png" /> (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380390.png" /> is the section of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380391.png" /> at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380392.png" />) is analytic in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380393.png" />; it follows from Kleene's recursion theorem (and classical ingredients) that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380394.png" /> is increasing and satisfies the following generalization of the first separation theorem: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380395.png" /> is analytic in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380396.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380397.png" /> is co-analytic in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380398.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380399.png" /> is a subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380400.png" />, there is a Borel set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380401.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380402.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380403.png" />.
+
A) Because of Kleene's recursion theorem (cf. [[Recursion|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<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380404.png" />), 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380405.png" /> is a uniformly analytic derivation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380406.png" /> (i.e. a uniformly analytic operation from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380407.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380408.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380409.png" /> for each analytic set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380410.png" />), and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380411.png" /> is the transfinite sequence of successive iterates, then i) for each analytic set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380412.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380413.png" /> is analytic, and is the largest <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380414.png" />-invariant subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380415.png" />; ii) the operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380416.png" /> thus defined is uniformly analytic; and iii) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380417.png" /> is analytic, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380418.png" /> is co-analytic and contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380419.png" />, then for some countable ordinal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380420.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380421.png" /> contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380422.png" />.
+
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|probability theory]], optimization, game theory), particularly in theories rich in exceptional sets ([[Potential theory|potential theory]], stochastic analysis, [[Hausdorff measure|Hausdorff measure]]; [[Harmonic analysis|harmonic analysis]]), but also in some others ([[Banach space|Banach space]] theory). These applications rely on the following results about analytic sets in Polish spaces:
 
Descriptive set theory has important applications in any branch of analysis using measure theory ([[Probability theory|probability theory]], optimization, game theory), particularly in theories rich in exceptional sets ([[Potential theory|potential theory]], stochastic analysis, [[Hausdorff measure|Hausdorff measure]]; [[Harmonic analysis|harmonic analysis]]), but also in some others ([[Banach space|Banach space]] theory). These applications rely on the following results about analytic sets in Polish spaces:
  
1) the stability properties of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031380/d031380423.png" /> and the first separation theorem, together with the universal measurability, or the Baire property, of analytic sets;
+
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);
 
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);

Latest revision as of 11:40, 26 March 2023


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)
How to Cite This Entry:
Descriptive set theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Descriptive_set_theory&oldid=11920
This article was adapted from an original article by A.G. El'kinV.I. Ponomarev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article