Analytical hierarchy
Encyclopedia
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.
indicates the class of formulas in the language of second-order arithmetic
with no set quantifiers. This language does not contain set parameters. The Greek letters here are lightface symbols, which indicate this choice of language. Each corresponding boldface symbol denotes the corresponding class of formulas in the extended language with a parameter for each real
; see projective hierarchy for details.
A formula in the language of second-order arithmetic is defined to be
if it is logically equivalent
to a formula of the form
where 
is 
. A formula is defined to be 
if it is logically equivalent to a formula of the form 
where 
is 
. This inductive definition defines the classes 
and 
for every natural number 
.
Because every formula has a prenex normal form
, every formula in the language of second-order arithmetic is
or 
for some 
. Because meaningless quantifiers can be added to any formula, once a formula is given the classification 
or 
for some 
it will be given the classifications 
and 
for all 
greater than 
.
if it is definable by a 
formula. The set is assigned the classification 
if it is definable by a 
formula. If the set is both 
and 
then it is given the additional classification 
.
The
sets are called hyperarithmetical. An alternate classification of these sets by way of iterated computable functionals is provided by hyperarithmetical theory
.
; the definition is particularly simple for Cantor and Baire space because they fit with the language of ordinary second-order arithmetic. Cantor space
is the set of all infinite sequences of 0s and 1s; Baire space
is the set of all infinite sequences of natural numbers. These are both Polish space
s.
The ordinary axiomatization of second-order arithmetic
uses a set-based language in which the set quantifiers can naturally be viewed as quantifying over Cantor space. A subset of Cantor space is assigned the classification
if it is definable by a 
formula. The set is assigned the classification 
if it is definable by a 
formula. If the set is both 
and 
then it is given the additional classification 
.
A subset of Baire space has a corresponding subset of Cantor space under the map that takes each function from
to 
to the characteristic function of its graph. A subset of Baire space is given the classification 
, 
, or 
if and only if the corresponding subset of Cantor space has the same classification. An equivalent definition of the analytical hierarchy on Baire space is given by defining the analytical hierarchy of formulas using a functional version of second-order arithmetic; then the analytical hierarchy on subsets of Cantor space can be defined from the hierarchy on Baire space. This alternate definition gives exactly the same classifications as the first definition.
Because Cantor space is homeomorphic to any finite Cartesian power of itself, and Baire space is homeomorphic to any finite Cartesian power of itself, the analytical hierarchy applies equally well to finite Cartesian power of one of these spaces.
A similar extension is possible for countable powers and to products of powers of Cantor space and powers of Baire space.
, a relativized version of the analytical hierarchy can be defined. The language is extended to add a constant set symbol A. A formula in the extended language is inductively defined to be
or 
using the same inductive definition as above. Given a set 
, a set is defined to be 
if it is definable by a 
formula in which the symbol 
is interpreted as 
; similar definitions for 
and 
apply. The sets that are 
or 
, for any parameter Y, are classified in the projective hierarchy.
we have the following strict containments:
,
,
,
.
A set that is in
for some n is said to be analytical. Care is required to distinguish this usage from the term analytic set
which has a different meaning.
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...
and 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...
, the analytical hierarchy is a higher type analogue of the arithmetical hierarchy
Arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them...
. It thus continues the classification of sets by the formulas that define them.
The analytical hierarchy of formulas
The notationindicates the class of formulas in the language of 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...
with no set quantifiers. This language does not contain set parameters. The Greek letters here are lightface symbols, which indicate this choice of language. Each corresponding boldface symbol denotes the corresponding class of formulas in the extended language with a parameter for each real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
; see projective hierarchy for details.
A formula in the language of second-order arithmetic is defined to be
if it is logically equivalentLogical equivalence
In logic, statements p and q are logically equivalent if they have the same logical content.Syntactically, p and q are equivalent if each can be proved from the other...
to a formula of the form
where is . A formula is defined to be if it is logically equivalent to a formula of the form where is . This inductive definition defines the classes and for every natural number .Because every formula has a prenex normal form
Prenex normal form
A formula of the predicate calculus is in prenex normal form if it is written as a string of quantifiers followed by a quantifier-free part .Every formula in classical logic is equivalent to a formula in prenex normal form...
, every formula in the language of second-order arithmetic is
or for some . Because meaningless quantifiers can be added to any formula, once a formula is given the classification or for some it will be given the classifications and for all greater than .The analytical hierarchy of sets of natural numbers
A set of natural numbers is assigned the classification if it is definable by a formula. The set is assigned the classification if it is definable by a formula. If the set is both and then it is given the additional classification .The
sets are called hyperarithmetical. An alternate classification of these sets by way of iterated computable functionals is provided by hyperarithmetical theoryHyperarithmetical 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...
.
The analytical hierarchy on subsets of Cantor and Baire space
The analytical hierarchy can be defined on any effective Polish spaceEffective Polish space
In mathematical logic, an effective Polish space is a complete separable metric space that has a computable presentation. Such spaces are studied in effective descriptive set theory and in constructive analysis.- Definition :...
; the definition is particularly simple for Cantor and Baire space because they fit with the language of ordinary second-order arithmetic. Cantor space
Cantor 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...
is the set of all infinite sequences of 0s and 1s; Baire space
Baire 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 ωω...
is the set of all infinite sequences of natural numbers. These are both 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.
The ordinary axiomatization of 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...
uses a set-based language in which the set quantifiers can naturally be viewed as quantifying over Cantor space. A subset of Cantor space is assigned the classification
if it is definable by a formula. The set is assigned the classification if it is definable by a formula. If the set is both and then it is given the additional classification .A subset of Baire space has a corresponding subset of Cantor space under the map that takes each function from
to to the characteristic function of its graph. A subset of Baire space is given the classification , , or if and only if the corresponding subset of Cantor space has the same classification. An equivalent definition of the analytical hierarchy on Baire space is given by defining the analytical hierarchy of formulas using a functional version of second-order arithmetic; then the analytical hierarchy on subsets of Cantor space can be defined from the hierarchy on Baire space. This alternate definition gives exactly the same classifications as the first definition.Because Cantor space is homeomorphic to any finite Cartesian power of itself, and Baire space is homeomorphic to any finite Cartesian power of itself, the analytical hierarchy applies equally well to finite Cartesian power of one of these spaces.
A similar extension is possible for countable powers and to products of powers of Cantor space and powers of Baire space.
Extensions
As is the case with the arithmetical hierarchyArithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them...
, a relativized version of the analytical hierarchy can be defined. The language is extended to add a constant set symbol A. A formula in the extended language is inductively defined to be
or using the same inductive definition as above. Given a set , a set is defined to be if it is definable by a formula in which the symbol is interpreted as ; similar definitions for and apply. The sets that are or , for any parameter Y, are classified in the projective hierarchy.Examples
- The set of all natural numbers which are indices of computable ordinals is a
set which is not 
.
- The set of elements of Cantor space which are the characteristic functions of well orderings of
is a 
set which is not 
. In fact, this set is not 
for any element 
of Baire space.
- If the axiom of constructibilityAxiom of constructibilityThe 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...
holds then there is a subset of the product of the Baire space with itself which is
and is the graph of a well ordering of Baire space. If the axiom holds then there is also a 
well ordering of Cantor space.
Properties
For each we have the following strict containments:,,,.A set that is in
for some n is said to be analytical. Care is required to distinguish this usage from the term 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...
which has a different meaning.