Descriptive set theory
Encyclopedia
In mathematical logic
, descriptive set theory is the study of certain classes of "well-behaved
" subsets of the real line
and other Polish space
s. As well as being one of the primary areas of research in set theory
, it has applications to other areas of mathematics such as functional analysis
, ergodic theory
, the study of operator algebras and group actions, and mathematical logic
.
s.
A Polish space
is a second countable topological space
that is metrizable with a complete metric. Equivalently, it is a complete separable metric space whose metric has been "forgotten". Examples include the real line
, the Baire space
, the Cantor space
, and the Hilbert cube
.
Because of these universality properties, and because the Baire space
has the convenient property that it is homeomorphic to 
, many results in descriptive set theory are proved in the context of Baire space alone.
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:
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.
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
s. For each nonzero countable ordinal α there are classes
, 
, 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.
. 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.
s 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.
considerations and the properties of ordinal
and cardinal number
s. This phenomenon is particularly apparent in the projective sets. These are defined via the projective hierarchy on a Polish space X:
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, 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 degrees, 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.
s. A Borel equivalence relation on a Polish space X is a Borel subset of
that is an equivalence relation
on X.
combines the methods of descriptive set theory with those of generalized recursion theory (especially hyperarithmetical theory
). In particular, it focuses on lightface analogues of hierarchies of classical descriptive set theory. Thus the hyperarithmetic hierarchy is studied instead of the Borel hierarchy, and the analytical hierarchy
instead of the projective hierarchy. This research is related to weaker version of set theory such as Kripke-Platek set theory and second-order arithmetic
.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, descriptive set theory is the study of certain classes of "well-behaved
Well-behaved
Mathematicians very frequently speak of whether a mathematical object — a function, a set, a space of one sort or another — is "well-behaved" or not. The term has no fixed formal definition, and is dependent on mathematical interests, fashion, and taste...
" subsets of the real line
Real line
In mathematics, the real line, or real number line is the line whose points are the real numbers. That is, the real line is the set of all real numbers, viewed as a geometric space, namely the Euclidean space of dimension one...
and other Polish space
Polish space
In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named because they were first extensively studied by Polish...
s. As well as being one of the primary areas of research in set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, it has applications to other areas of mathematics such as functional analysis
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 and the linear operators acting upon these spaces and respecting these structures in a suitable sense...
, ergodic theory
Ergodic theory
Ergodic theory is a branch of mathematics that studies dynamical systems with an invariant measure and related problems. Its initial development was motivated by problems of statistical physics....
, the study of operator algebras and group actions, and mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
.
Polish spaces
Descriptive set theory begins with the study of Polish spaces and their Borel setBorel set
In mathematics, a Borel set is any set in a topological space that can be formed from open sets through the operations of countable union, countable intersection, and relative complement...
s.
A Polish space
Polish space
In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named because they were first extensively studied by Polish...
is a second countable topological space
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
that is metrizable with a complete metric. Equivalently, it is a complete separable metric space whose metric has been "forgotten". Examples include the real line
Real line
In mathematics, the real line, or real number line is the line whose points are the real numbers. That is, the real line is the set of all real numbers, viewed as a geometric space, namely the Euclidean space of dimension one...
, the Baire spaceBaire space (set theory)
In set theory, the Baire space is the set of all infinite sequences of natural numbers with a certain topology. This space is commonly used in descriptive set theory, to the extent that its elements are often called “reals.” It is often denoted B, N'N, or ωω...
, the Cantor spaceCantor space
In mathematics, a Cantor space, named for Georg Cantor, is a topological abstraction of the classical Cantor set: a topological space is a Cantor space if it is homeomorphic to the Cantor set. In set theory, the topological space 2ω is called "the" Cantor space...
, and the Hilbert cubeHilbert cube
In mathematics, the Hilbert cube, named after David Hilbert, is a topological space that provides an instructive example of some ideas in topology...
.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 to a Gδ subspaceSubspace topologyIn topology and related areas of mathematics, a subspace of a topological space X is a subset S of X which is equipped with a natural topology induced from that of X called the subspace topology .- Definition :Given a topological space and a subset S of X, the...
of the Hilbert cubeHilbert cubeIn mathematics, the Hilbert cube, named after David Hilbert, is a topological space that provides an instructive example of some ideas in topology...
, 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 to , many results in descriptive set theory are proved in the context of Baire space alone.Borel sets
The class of Borel setBorel set
In mathematics, a Borel set is any set in a topological space that can be formed from open sets through the operations of countable union, countable intersection, and relative complement...
s of a topological space X consists of all sets in the smallest σ-algebra
Sigma-algebra
In mathematics, a σ-algebra is a technical concept for a collection of sets satisfying certain properties. The main use of σ-algebras is in the definition of measures; specifically, the collection of sets over which a measure is defined is a σ-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 An 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 hierarchyBorel hierarchy
In mathematical logic, the Borel hierarchy is a stratification of the Borel algebra generated by the open subsets of a Polish space; elements of this algebra are called Borel sets. Each Borel set is assigned a unique countable ordinal number called the rank of the Borel set...
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
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
ordinal number
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
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 ⟨ Ai ⟩ 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 propertyPerfect set property
In descriptive set theory, a subset of a Polish space has the perfect set property if it is either countable or has a nonempty perfect subset...
. 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 setAnalytic set
In descriptive set theory, a subset of a Polish space X is an analytic set if it is a continuous image of a Polish space. These sets were first defined by and his student .- Definition :There are several equivalent definitions of analytic set...
s 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-theoreticSet theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
considerations and the properties of ordinal
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
and cardinal number
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
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
Axiom of constructibility
The axiom of constructibility is a possible axiom for set theory in mathematics that asserts that every set is constructible. The axiom is usually written as V = L, where V and L denote the von Neumann universe and the constructible universe, respectively.- Implications :The axiom of...
, not all projective sets have the perfect set property or the property of Baire. However, under the assumption of projective determinacy, 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 degrees, that generalize the projective hierarchy. These degrees are ordered in the Wadge hierarchy
Wadge hierarchy
In descriptive set theory, 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.- Wadge degrees :...
. The axiom of determinacy
Axiom of determinacy
The axiom of determinacy is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person games of length ω with perfect information...
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 relationBorel equivalence relation
In mathematics, a Borel equivalence relation on a Polish space X is an equivalence relation on X that is a Borel subset of X × X....
s. A Borel equivalence relation on a Polish space X is a Borel subset of
that is an equivalence relationEquivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
on X.
Effective descriptive set theory
The area of effective descriptive set theoryEffective 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. Thus effective descriptive set theory combines descriptive set theory with recursion theory....
combines the methods of descriptive set theory with those of generalized recursion theory (especially hyperarithmetical theory
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...
). In particular, it focuses on lightface analogues of hierarchies of classical descriptive set theory. Thus the hyperarithmetic hierarchy is studied instead of the Borel hierarchy, and the analytical hierarchy
Analytical hierarchy
In mathematical logic and descriptive set theory, the analytical hierarchy is a higher type analogue of the arithmetical hierarchy. It thus continues the classification of sets by the formulas that define them.-The analytical hierarchy of formulas:...
instead of the projective hierarchy. This research is related to weaker version of set theory such as Kripke-Platek set theory and second-order arithmetic
Second-order arithmetic
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. It was introduced by David Hilbert and Paul Bernays in their...
.
External links
- Descriptive set theory, David Marker, 2002. Lecture notes.