Descriptive set theory


Descriptive set theory

In mathematical logic, descriptive set theory is the study of certain classes of "well-behaved" subsets of the real line and other Polish spaces. 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.

Contents

Polish spaces

Descriptive set theory begins with the study of Polish spaces and their Borel sets.

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 \mathbb{R}, the Baire space \mathcal{N}, the Cantor space \mathcal{C}, and the Hilbert cube I^{\mathbb{N}}.

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δ subspace of the Hilbert cube, 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 \mathcal{N} has the convenient property that it is homeomorphic to \mathcal{N}^\omega, many results in descriptive set theory are proved in the context of Baire space alone.

Borel sets

The class of Borel sets 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 X \setminus A. 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 \bigcup A_n 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 numbers. For each nonzero countable ordinal α there are classes \mathbf{\Sigma}^0_\alpha, \mathbf{\Pi}^0_\alpha, and \mathbf{\Delta}^0_\alpha.

  • Every open set is declared to be \mathbf{\Sigma}^0_1.
  • A set is declared to be \mathbf{\Pi}^0_\alpha if and only if its complement is \mathbf{\Sigma}^0_\alpha.
  • A set A is declared to be \mathbf{\Sigma}^0_\delta, δ > 1, if there is a sequence 〈 Ai 〉 of sets, each of which is \mathbf{\Pi}^0_{\lambda(i)} for some λ(i) < δ, such that A = \bigcup A_i.
  • A set is \mathbf{\Delta}^0_\alpha if and only if it is both \mathbf{\Sigma}^0_\alpha and \mathbf{\Pi}^0_\alpha.

A theorem shows that any set that is \mathbf{\Sigma}^0_\alpha or \mathbf{\Pi}^0_\alpha is \mathbf{\Delta}^0_{\alpha + 1}, and any \Delta^0_\beta set is both \mathbf{\Sigma}^0_\alpha and \mathbf{\Pi}^0_\alpha for all α > β. Thus the hierarchy has the following structure, where arrows indicate inclusion.


\begin{matrix}
& & \mathbf{\Sigma}^0_1 & & & & \mathbf{\Sigma}^0_2 & & \cdots \\
& \nearrow & & \searrow & & \nearrow \\
\mathbf{\Delta}^0_1 & & & & \mathbf{\Delta}^0_2 & & & & \cdots \\
& \searrow & & \nearrow & & \searrow \\
& & \mathbf{\Pi}^0_1 & & & & \mathbf{\Pi}^0_2 & & \cdots 
\end{matrix}\begin{matrix}
& &  \mathbf{\Sigma}^0_\alpha & & & \cdots \\
& \nearrow & & \searrow \\
\quad \mathbf{\Delta}^0_\alpha &  & & & \mathbf{\Delta}^0_{\alpha + 1} & \cdots \\
& \searrow & & \nearrow \\
& & \mathbf{\Pi}^0_\alpha & & & \cdots 
\end{matrix}

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 numbers. 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 \mathbf{\Sigma}^1_1 if it is analytic.
  • A set is \mathbf{\Pi}^1_1 if it is coanalytic.
  • A set A is \mathbf{\Sigma}^1_{n+1} if there is a \mathbf{\Pi}^1_n subset B of X \times X such that A is the projection of B to the first coordinate.
  • A set A is \mathbf{\Pi}^1_{n+1} if there is a \mathbf{\Sigma}^1_n subset B of X \times X such that A is the projection of B to the first coordinate.
  • A set is \mathbf{\Delta}^1_{n} if it is both \mathbf{\Pi}^1_n and \mathbf{\Sigma}^1_n .

As with the Borel hierarchy, for each n, any \mathbf{\Delta}^1_n set is both \mathbf{\Sigma}^1_{n+1} and \mathbf{\Pi}^1_{n+1}.

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.

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 X \times X that is an equivalence relation on X.

Effective descriptive set theory

The area of effective descriptive set theory 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.

See also

References

  • Kechris, Alexander S. (1994). Classical Descriptive Set Theory. Springer-Verlag. ISBN 0-387-94374-9. 

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 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… …   Wikipedia

  • Tree (descriptive set theory) — In descriptive set theory, a tree on a set X is a set of finite sequences of elements of X that is closed under subsequences. More formally, it is a subset T of X^{ …   Wikipedia

  • Descriptive complexity theory — For other uses, see Kolmogorov complexity. Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For… …   Wikipedia

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • Tree (set theory) — In set theory, a tree is a partially ordered set (poset) ( T …   Wikipedia

  • Cabal (set theory) — The Cabal was, or perhaps is, a grouping of set theorists in Southern California, particularly at UCLA and Caltech, perhaps also at UC Irvine. Organization and procedures range from informal to nonexistent, so it is difficult to say whether it… …   Wikipedia

  • List of set theory topics — Logic portal Set theory portal …   Wikipedia

  • Baire space (set theory) — In mathematics field of set theory, especially descriptive 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… …   Wikipedia

  • Set of uniqueness — M set redirects here. For the CityRail train, see CityRail M set. In mathematics, a set of uniqueness is a concept relevant to trigonometric expansions which are not necessarily Fourier series. Their study is a relatively pure branch of harmonic… …   Wikipedia

  • Theory — The word theory has many distinct meanings in different fields of knowledge, depending on their methodologies and the context of discussion.In science a theory is a testable model of the manner of interaction of a set of natural phenomena,… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.