In
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...
, descriptive set theory (DST) is the study of certain classes of "
well-behaved"
subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
s of the
real line
In elementary mathematics, a number line is a picture of a graduated straight line that serves as visual representation of the real numbers. Every point of a number line is assumed to correspond to a real number, and every real number to a po ...
and other
Polish spaces. As well as being one of the primary areas of research in
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
, it has applications to other areas of mathematics such as
functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (e.g. inner product, norm, topology, etc.) and the linear functions defi ...
,
ergodic theory, the study of
operator algebras
In functional analysis, a branch of mathematics, an operator algebra is an algebra of continuous linear operators on a topological vector space, with the multiplication given by the composition of mappings.
The results obtained in the stud ...
and
group actions
In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphism ...
, and
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...
.
Polish spaces
Descriptive set theory begins with the study of Polish spaces and their
Borel set
In mathematics, a Borel set is any set in a topological space that can be formed from open sets (or, equivalently, from closed sets) through the operations of countable union, countable intersection, and relative complement. Borel sets are na ...
s.
A
Polish space is a
second-countable
In topology, a second-countable space, also called a completely separable space, is a topological space whose topology has a countable base. More explicitly, a topological space T is second-countable if there exists some countable collection \ma ...
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called poin ...
that is
metrizable with a
complete metric
In mathematical analysis, a metric space is called complete (or a Cauchy space) if every Cauchy sequence#In a metric space, Cauchy sequence of points in has a Limit of a sequence, limit that is also in .
Intuitively, a space is complete if ther ...
. Heuristically, it is a complete
separable metric space
In mathematics, a topological space is called separable if it contains a countable, dense subset; that is, there exists a sequence \_^ of elements of the space such that every nonempty open subset of the space contains at least one element of th ...
whose metric has been "forgotten". Examples include the
real line
In elementary mathematics, a number line is a picture of a graduated straight line that serves as visual representation of the real numbers. Every point of a number line is assumed to correspond to a real number, and every real number to a po ...
, the
Baire space , the
Cantor space , and the
Hilbert cube
In mathematics, the Hilbert cube, named after David Hilbert, is a topological space that provides an instructive example of some ideas in topology. Furthermore, many interesting topological spaces can be embedded in the Hilbert cube; that is ...
.
Universality properties
The class of Polish spaces has several universality properties, which show that there is no loss of generality in considering Polish spaces of certain restricted forms.
* Every Polish space is
homeomorphic
In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomor ...
to a ''G''
δ subspace of the
Hilbert cube
In mathematics, the Hilbert cube, named after David Hilbert, is a topological space that provides an instructive example of some ideas in topology. Furthermore, many interesting topological spaces can be embedded in the Hilbert cube; that is ...
, and every ''G''
δ subspace of the Hilbert cube is Polish.
* Every Polish space is obtained as a continuous image of Baire space; in fact every Polish space is the image of a continuous bijection defined on a closed subset of Baire space. Similarly, every compact Polish space is a continuous image of Cantor space.
Because of these universality properties, and because the Baire space
has the convenient property that it is
homeomorphic
In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomor ...
to
, many results in descriptive set theory are proved in the context of Baire space alone.
Borel sets
The class of
Borel set
In mathematics, a Borel set is any set in a topological space that can be formed from open sets (or, equivalently, from closed sets) through the operations of countable union, countable intersection, and relative complement. Borel sets are na ...
s of a topological space ''X'' consists of all sets in the smallest
σ-algebra containing the open sets of ''X''. This means that the Borel sets of ''X'' are the smallest collection of sets such that:
* Every open subset of ''X'' is a Borel set.
* If ''A'' is a Borel set, so is
. That is, the class of Borel sets are closed under complementation.
* If ''A''
''n'' is a Borel set for each natural number ''n'', then the union
is a Borel set. That is, the Borel sets are closed under countable unions.
A fundamental result shows that any two uncountable Polish spaces ''X'' and ''Y'' are
Borel isomorphic: there is a bijection from ''X'' to ''Y'' such that the preimage of any Borel set is Borel, and the image of any Borel set is Borel. This gives additional justification to the practice of restricting attention to Baire space and Cantor space, since these and any other Polish spaces are all isomorphic at the level of Borel sets.
Borel hierarchy
Each Borel set of a Polish space is classified in the
Borel hierarchy based on how many times the operations of countable union and complementation must be used to obtain the set, beginning from open sets. The classification is in terms of
countable ordinal number
In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets.
A finite set can be enumerated by successively labeling each element with the leas ...
s. For each nonzero countable ordinal ''α'' there are classes
,
, and
.
* Every open set is declared to be
.
* A set is declared to be
if and only if its complement is
.
* A set ''A'' is declared to be
, ''δ'' > 1, if there is a sequence 〈 ''A''
''i'' 〉 of sets, each of which is
for some ''λ''(''i'') < ''δ'', such that
.
* A set is
if and only if it is both
and
.
A theorem shows that any set that is
or
is
, and any
set is both
and
for all ''α'' > ''β''. Thus the hierarchy has the following structure, where arrows indicate inclusion.
Regularity properties of Borel sets
Classical descriptive set theory includes the study of regularity properties of Borel sets. For example, all Borel sets of a Polish space have the
property of Baire and the
perfect set property. Modern descriptive set theory includes the study of the ways in which these results generalize, or fail to generalize, to other classes of subsets of Polish spaces.
Analytic and coanalytic sets
Just beyond the Borel sets in complexity are the
analytic sets and
coanalytic sets. A subset of a Polish space ''X'' is analytic if it is the continuous image of a Borel subset of some other Polish space. Although any continuous preimage of a Borel set is Borel, not all analytic sets are Borel sets. A set is coanalytic if its complement is analytic.
Projective sets and Wadge degrees
Many questions in descriptive set theory ultimately depend upon
set-theoretic considerations and the properties of
ordinal and
cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. ...
s. This phenomenon is particularly apparent in the projective sets. These are defined via the
projective hierarchy on a Polish space ''X'':
* A set is declared to be
if it is analytic.
* A set is
if it is coanalytic.
* A set ''A'' is
if there is a
subset ''B'' of
such that ''A'' is the projection of ''B'' to the first coordinate.
* A set ''A'' is
if there is a
subset ''B'' of
such that ''A'' is the projection of ''B'' to the first coordinate.
* A set is
if it is both
and
.
As with the Borel hierarchy, for each ''n'', any
set is both
and
The properties of the projective sets are not completely determined by ZFC. Under the assumption
''V = L'', not all projective sets have the perfect set property or the property of Baire. However, under the assumption of
projective determinacy In mathematical logic, projective determinacy is the special case of the axiom of determinacy applying only to projective sets.
The axiom of projective determinacy, abbreviated PD, states that for any two-player infinite game of perfect informatio ...
, all projective sets have both the perfect set property and the property of Baire. This is related to the fact that ZFC proves
Borel determinacy, but not projective determinacy.
More generally, the entire collection of sets of elements of a Polish space ''X'' can be grouped into equivalence classes, known as
Wadge degree In descriptive set theory, within mathematics, Wadge degrees are levels of complexity for sets of reals. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge degrees. These concepts are named after William W. Wa ...
s, that generalize the projective hierarchy. These degrees are ordered in the
Wadge hierarchy. The
axiom of determinacy implies that the Wadge hierarchy on any Polish space is well-founded and of length
Θ, with structure extending the projective hierarchy.
Borel equivalence relations
A contemporary area of research in descriptive set theory studies
Borel equivalence relations. A Borel equivalence relation on a Polish space ''X'' is a Borel subset of
that is an
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relatio ...
on ''X''.
Effective descriptive set theory
The area of
effective descriptive set theory
Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter (Moschovakis 1980). Thus effective descriptiv ...
combines the methods of descriptive set theory with those of
generalized recursion theory
A generalization is a form of abstraction whereby common properties of specific instances are formulated as general concepts or claims. Generalizations posit the existence of a domain or set theory, set of elements, as well as one or more commo ...
(especially
hyperarithmetical theory In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an import ...
). In particular, it focuses on
lightface
In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a ''point'' is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by ...
analogues of hierarchies of classical descriptive set theory. Thus the
hyperarithmetic hierarchy In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an im ...
is studied instead of the Borel hierarchy, and the
analytical hierarchy instead of the projective hierarchy. This research is related to weaker versions of set theory such as
Kripke–Platek set theory and
second-order arithmetic.
Table
See also
*
Pointclass
*
Prewellordering
In set theory, a prewellordering on a set X is a preorder \leq on X (a transitive and strongly connected relation on X) that is wellfounded in the sense that the relation x \leq y \land y \nleq x is wellfounded. If \leq is a prewellordering o ...
*
Scale property
References
*
* {{cite book , authorlink=Yiannis N. Moschovakis , author=Moschovakis, Yiannis N. , title=Descriptive Set Theory, url=https://www.math.ucla.edu/~ynm/books.htm , publisher=North Holland , year=1980, page=2 , isbn=0-444-70199-0
External links
Descriptive set theory David Marker, 2002. Lecture notes.