Effective descriptive set theory is the branch of
descriptive set theory
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 ot ...
dealing with
sets of
reals having
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 ...
definitions; that is, definitions that do not require an arbitrary real
parameter
A parameter (), generally, is any characteristic that can help in defining or classifying a particular system (meaning an event, project, object, situation, etc.). That is, a parameter is an element of a system that is useful, or critical, when ...
(Moschovakis 1980). Thus effective descriptive set theory combines descriptive set theory with
recursion theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
.
Constructions
Effective Polish space
An effective Polish space is a
complete
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable
Mathematics
* The completeness of the real numbers, which implies t ...
separable metric space
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
that has a
computable presentation
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is clos ...
. Such spaces are studied in both effective descriptive set theory and in
constructive analysis
In mathematics, constructive analysis is mathematical analysis done according to some principles of constructive mathematics.
This contrasts with ''classical analysis'', which (in this context) simply means analysis done according to the (more comm ...
. In particular, standard examples of Polish spaces such as the
real line
In elementary mathematics, a number line is a picture of a graduated straight line (geometry), 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 ...
, the
Cantor set
In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of unintuitive properties. It was discovered in 1874 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883.
Thr ...
and the
Baire space
In mathematics, a topological space X is said to be a Baire space if countable unions of closed sets with empty interior also have empty interior.
According to the Baire category theorem, compact Hausdorff spaces and complete metric spaces are ...
are all effective Polish spaces.
Arithmetical hierarchy
The
arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
, arithmetic hierarchy or
Kleene
Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of ...
–
Mostowski hierarchy classifies certain
sets based on the complexity of formulas that define them. Any set that receives a classification is called "arithmetical".
More formally, the arithmetical hierarchy assigns classifications to the formulas in the language of
first-order arithmetic
In first-order logic, a first-order theory is given by a set of axioms in some
language. This entry lists some of the more common examples used in model theory and some of their properties.
Preliminaries
For every natural mathematical structure ...
. The classifications are denoted
and
for natural numbers ''n'' (including 0). The Greek letters here are
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 ...
symbols, which indicates that the formulas do not contain set parameters.
If a formula
is
logically equivalent
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
to a formula with only
bounded quantifier
In the study of formal theories in mathematical logic, bounded quantifiers (a.k.a. restricted quantifiers) are often included in a formal language in addition to the standard quantifiers "∀" and "∃". Bounded quantifiers differ from "∀" and " ...
s then
is assigned the classifications
and
.
The classifications
and
are defined inductively for every natural number ''n'' using the following rules:
*If
is logically equivalent to a formula of the form
, where
is
, then
is assigned the classification
.
*If
is logically equivalent to a formula of the form
, where
is
, then
is assigned the classification
.
References
*
*
Second edition available online
{{settheory-stub, date=November 2005