Descriptive set theory

Last updated

In mathematical logic, descriptive set theory (DST) 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.

Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics. It bears close connections to metamathematics, the foundations of mathematics, and theoretical computer science. The unifying themes in mathematical logic include the study of the expressive power of formal systems and the deductive power of formal proof systems.

Set (mathematics) Fundamental mathematical concept related to the notions of belonging or inclusion

SET: Simple definition for set:Set is a well-defined|collection of distinct objects.

Real line Wikimedia disambiguation page

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 R of all real numbers, viewed as a geometric space, namely the Euclidean space of dimension one. It can be thought of as a vector space, a metric space, a topological space, a measure space, or a linear continuum.

Contents

Polish spaces

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

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. Borel sets are named after Émile Borel.

A Polish space is a second-countable topological space that is metrizable with a complete metric. Heuristically, 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 .

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 topologists and logicians—Sierpiński, Kuratowski, Tarski and others. However, Polish spaces are mostly studied today because they are the primary setting for descriptive set theory, including the study of Borel equivalence relations. Polish spaces are also a convenient setting for more advanced measure theory, in particular in probability theory.

In topology and related branches of mathematics, a topological space may be defined as a set of points, along with a set of neighbourhoods for each point, satisfying a set of axioms relating points and neighbourhoods. The definition of a topological space relies only upon set theory and is the most general notion of a mathematical space that allows for the definition of concepts such as continuity, connectedness, and convergence. Other spaces, such as manifolds and metric spaces, are specializations of topological spaces with extra structures or constraints. Being so general, topological spaces are a central unifying notion and appear in virtually every branch of modern mathematics. The branch of mathematics that studies topological spaces in their own right is called point-set topology or general topology.

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 denoted B, NN, ωω, ωω, or .

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.

In topology and related areas of mathematics, a subspace of a topological space X is a subset S of X which is equipped with a topology induced from that of X called the subspace topology.

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, can be viewed as subspaces of 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.

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:

In mathematical analysis and in probability theory, a σ-algebra on a set X is a collection Σ of subsets of X that includes X itself, is closed under complement, and is 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 , , 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 numbers. 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.

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 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 versions of set theory such as Kripke–Platek set theory and second-order arithmetic.

Table

Lightface Boldface
Σ0
0
= Π0
0
= Δ0
0
(sometimes the same as Δ0
1
)
Σ0
0
= Π0
0
= Δ0
0
(if defined)
Δ0
1
= recursive
Δ0
1
= clopen
Σ0
1
= recursively enumerable
Π0
1
= co-recursively enumerable
Σ0
1
= G = open
Π0
1
= F = closed
Δ0
2
Δ0
2
Σ0
2
Π0
2
Σ0
2
= Fσ
Π0
2
= Gδ
Δ0
3
Δ0
3
Σ0
3
Π0
3
Σ0
3
= Gδσ
Π0
3
= Fσδ
Σ0
= Π0
= Δ0
= Σ1
0
= Π1
0
= Δ1
0
= arithmetical
Σ0
= Π0
= Δ0
= Σ1
0
= Π1
0
= Δ1
0
= boldface arithmetical
Δ0
α
recursive)
Δ0
α
countable)
Σ0
α
Π0
α
Σ0
α
Π0
α
Σ0
ωCK
1
= Π0
ωCK
1
= Δ0
ωCK
1
= Δ1
1
= hyperarithmetical
Σ0
ω1
= Π0
ω1
= Δ0
ω1
= Δ1
1
= B = Borel
Σ1
1
= lightface analytic
Π1
1
= lightface coanalytic
Σ1
1
= A = analytic
Π1
1
= CA = coanalytic
Δ1
2
Δ1
2
Σ1
2
Π1
2
Σ1
2
= PCA
Π1
2
= CPCA
Δ1
3
Δ1
3
Σ1
3
Π1
3
Σ1
3
= PCPCA
Π1
3
= CPCPCA
Σ1
= Π1
= Δ1
= Σ2
0
= Π2
0
= Δ2
0
= analytical
Σ1
= Π1
= Δ1
= Σ2
0
= Π2
0
= Δ2
0
= P = projective

See also

Related Research Articles

Dirac delta function pseudo-function δ such that an integral of δ(x-c)f(x) always takes the value of f(c)

In mathematics, the Dirac delta function is a generalized function or distribution introduced by the physicist Paul Dirac. It is used to model the density of an idealized point mass or point charge as a function equal to zero everywhere except for zero and whose integral over the entire real line is equal to one. As there is no function that has these properties, the computations made by the theoretical physicists appeared to mathematicians as nonsense until the introduction of distributions by Laurent Schwartz to formalize and validate the computations. As a distribution, the Dirac delta function is a linear functional that maps every function to its value at zero. The Kronecker delta function, which is usually defined on a discrete domain and takes values 0 and 1, is a discrete analog of the Dirac delta function.

In mathematics and in particular measure theory, a measurable function is a function between the underlying sets of two measurable spaces that preserves the structure of the spaces: the preimage of any measurable set is measurable, analogous to the definition that a function between topological spaces is continuous if it preserves the topological structure: the preimage of each open set is open. In real analysis, measurable functions are used in the definition of the Lebesgue integral. In probability theory, a measurable function on a probability space is known as a random variable.

Arithmetical hierarchy Hierarchy of complexity classes for formulas defining sets

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical.

In the mathematical field of topology, a Gδ set is a subset of a topological space that is a countable intersection of open sets. The notation originated in Germany with G for Gebiet meaning open set in this case and δ for Durchschnitt. The term inner limiting set is also used. Gδ sets, and their dual, Fσ sets, are the second level of the Borel hierarchy.

In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers over both the set of natural numbers, , and over functions from to . The analytical hierarchy of sets classifies sets by the formulas that can be used to define them; it is the lightface version of the projective hierarchy.

In descriptive set theory, a subset of a Polish space is an analytic set if it is a continuous image of a Polish space. These sets were first defined by Luzin (1917) and his student Souslin (1917).

In the mathematical field of descriptive set theory, a subset of a Polish space is projective if it is for some positive integer . Here is

In set theory, a prewellordering is a binary relation that is transitive, total, and wellfounded. In other words, if is a prewellordering on a set , and if we define by

In general relativity, the Gibbons–Hawking–York boundary term is a term that needs to be added to the Einstein–Hilbert action when the underlying spacetime manifold has a boundary.

In calculus, Leibniz's rule for differentiation under the integral sign, named after Gottfried Leibniz, states that for an integral of the form

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists.

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.

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.

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. The Borel hierarchy is of particular interest in descriptive set theory.

The Newman–Penrose (NP) formalism is a set of notation developed by Ezra T. Newman and Roger Penrose for general relativity (GR). Their notation is an effort to treat general relativity in terms of spinor notation, which introduces complex forms of the usual variables used in GR. The NP formalism is itself a special case of the tetrad formalism, where the tensors of the theory are projected onto a complete vector basis at each point in spacetime. Usually this vector basis is chosen to reflect some symmetry of the spacetime, leading to simplified expressions for physical observables. In the case of the NP formalism, the vector basis chosen is a null tetrad: a set of four null vectors—two real, and a complex-conjugate pair. The two real members asymptotically point radially inward and radially outward, and the formalism is well adapted to treatment of the propagation of radiation in curved spacetime. The Weyl scalars, derived from the Weyl tensor, are often used. In particular, it can be shown that one of these scalars— in the appropriate frame—encodes the outgoing gravitational radiation of an asymptotically flat system.

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 some sort of definability property; for example, the collection of all open sets in some fixed collection of Polish spaces is a pointclass.

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 important tool in effective descriptive set theory.

This is a glossary of set theory.

References