Arithmetical hierarchy
Encyclopedia
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.
The arithmetical hierarchy is important in recursion theory
, effective descriptive set theory
, and the study of formal theories such as Peano arithmetic.
The Tarski-Kuratowski algorithm provides an easy way to get an upper bound on the classifications assigned to a formula and the set it defines.
The hyperarithmetical hierarchy and the analytical hierarchy
extend the arithmetical hierarchy to classify additional formulas and sets.
. The classifications are denoted
and 
for natural numbers n (including 0). The Greek letters here are lightface symbols, which indicates that the formulas do not contain set parameters.
If a formula
is logically equivalent to a formula with only bounded quantifier
s then
is assigned the classifications 
and 
.
The classifications
and 
are defined inductively for every natural number n using the following rules:
As well, a
formula is equivalent to a formula that begins with some existential quantifiers and alternates 
times between series of existential and universal quantifiers; while a 
formula is equivalent to a formula that begins with some universal quantifiers and alternates similarly.
Because every formula is equivalent to a formula in prenex normal form
, every formula with no set quantifiers is assigned at least one classification. Because meaningless quantifiers can be added to any formula, once a formula is assigned the classification
or 
it will be assigned the classifications 
and 
for every m greater than n. The most important classification assigned to a formula is thus the one with the least n, because this is enough to determine all the other classifications.
where
is the numeral in the language of arithmetic corresponding to 
. A set is definable in first order arithmetic if it is defined by some formula in the language of Peano arithmetic.
Each set X of natural numbers that is definable in first order arithmetic is assigned classifications of the form
, 
, and 
, where 
is a natural number, as follows. If X is definable by a 
formula then X is assigned the classification 
. If X is definable by a 
formula then X is assigned the classification 
. If X is both 
and 
then 
is assigned the additional classification 
.
Note that it rarely makes sense to speak of
formulas; the first quantifier of a formula is either existential or universal. So a 
set is not defined by a 
formula; rather, there are both 
and 
formulas that define the set.
A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of the natural numbers. Instead of formulas with one free variable, formulas with k free number variables are used to define the arithmetical hierarchy on sets of k-tuple
s of natural numbers.
relative to another set Y by allowing the computation defining X to consult Y as an oracle we can extend this notion to the whole arithmetic hierarchy and define what it means for X to be
, 
or 
in Y, denoted respectively 
and 
. To do so, fix a set of integers Y and add a predicate for membership in Y to the language of Peano arithmetic. We then say that X is in 
if it is defined by a 
formula in this expanded language. In other words X is 
if it is defined by a 
formula allowed to ask questions about membership in Y. Alternatively one can view the 
sets as those sets that can be built starting with sets recursive in Y and alternatively projecting and taking the complements of these sets up to n times.
For example let Y be a set of integers. Let X be the set of numbers divisible by an element of Y. Then X is defined by the formula
so X is in 
(actually it is in 
as well since we could bound both quantifiers by n).
A set is arithmetical (also arithmetic and arithmetically definable) if it is defined by some formula in the language of Peano arithmetic. Equivalently X is arithmetical if X is
or 
for some integer n. A set X is arithmetical in a set Y, denoted 
, if X is definable a some formula in the language of Peano arithmetic extended by a predicate for membership in Y. Equivalently, X is arithmetical in Y if X is in 
or 
for some integer n. A synonym for 
is: X is arithmetically reducible to Y
The relation
is reflexive and transitive, and thus the relation 
defined by the rule
is an equivalence relation. The equivalence classes of this relation are called the arithmetic degrees; they are partially ordered under
.
, denoted
, is the set of all infinite sequences of 0s and 1s; the Baire space
, denoted
or 
, is the set of all infinite sequences of natural numbers. Note that elements of the Cantor space can be identified with sets of integers and elements of the Baire space with functions from integers to integers.
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 
. For example let 
be the set of all infinite binary strings which aren't all 0 (or equivalently the set of all non-empty sets of integers). As 
we see that 
is defined by a 
formula and hence is a 
set.
Note that while both the elements of the Cantor space (regarded as sets of integers) and subsets of the Cantor space are classified in arithmetic hierarchies but these are not the same hierarchy. In fact the relationship between the two hierarchies is interesting and non-trivial. For instance the
elements of the Cantor space are not (in general) the same as the elements 
of the Cantor space so that 
is a 
subset of the Cantor space. However, many interesting results relate the two hierarchies.
There are two ways that a subset of Baire space can be classified in the arithmetical hierarchy.
A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of Baire space or Cantor space, using formulas with several free variables. The arithmetical hierarchy can be defined on any effective Polish space
; the definition is particularly simple for Cantor space and Baire space because they fit with the language of ordinary second-order arithmetic.
Note that we can also define the arithmetic hierarchy of subsets of the Cantor and Baire spaces relative to some set of integers. In fact boldface
is just the union of 
for all sets of integers Y. Note that the boldface hierarchy is just the standard hierarchy of Borel sets
.
. This variation slightly changes the classification of some sets.
A more semantic variation of the hierarchy can be defined on all finitary relations on the natural numbers; the following definition is used. Every computable relation is defined to be
and 
. The classifications 
and 
are defined inductively with the following rules.
This variation slightly changes the classification of some sets. It can be extended to cover finitary relations on the natural numbers, Baire space, and Cantor space.
The subscript
in the symbols 
and 
indicates the number of alternations of blocks of universal and existential number quantifiers that are used in a formula. Moreover, the outermost block is existential in 
formulas and universal in 
formulas.
The superscript
in the symbols 
, 
, and 
indicates the type of the objects being quantified over. Type 0 objects are natural numbers, and objects of type 
are functions that map the set of objects of type 
to the natural numbers. Quantification over higher type objects, such as functions from natural numbers to natural numbers, is described by a superscript greater than 0, as in the analytical hierarchy
. The superscript 0 indicates quantifiers over numbers, the superscript 1 would indicate quantification over functions from numbers to numbers (type 1 objects), the superscript 2 would correspond to quantification over functions that take a type 1 object and return a number, and so on.
of the arithmetical hierarchy. The recursively enumerable sets are exactly the sets at level 
.
No oracle machine
is capable of solving its own halting problem
(a variation of Turing's proof applies). The halting problem for a
oracle in fact sits in 
.
Post's theorem
establishes a close connection between the arithmetical hierarchy of sets of natural numbers and the Turing degree
s. In particular, it establishes the following facts for all n ≥ 1:
The polynomial hierarchy
is a "feasible resource-bounded" version of the arithmetical hierarchy in which polynomial length bounds are placed on the numbers involved (or, equivalently, polynomial time bounds are placed on the Turing machines involved). It gives a finer classification of some sets of natural numbers that are at level
of the arithmetical hierarchy.
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...
, 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.
The arithmetical hierarchy is important in recursion theory
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, effective descriptive set theory
Effective 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....
, and the study of formal theories such as Peano arithmetic.
The Tarski-Kuratowski algorithm provides an easy way to get an upper bound on the classifications assigned to a formula and the set it defines.
The hyperarithmetical 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:...
extend the arithmetical hierarchy to classify additional formulas and sets.
The arithmetical hierarchy of formulas
The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmeticPeano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are a set of axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano...
. The classifications are denoted
and for natural numbers n (including 0). The Greek letters here are lightface symbols, which indicates that the formulas do not contain set parameters.If a formula
is logically equivalent to a formula with only bounded quantifierBounded quantifier
In the study of formal theories in mathematical logic, bounded quantifiers are often added to a language in addition to the standard quantifiers "∀" and "∃". Bounded quantifiers differ from "∀" and "∃" in that bounded quantifiers restrict the range of the quantified variable...
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 
.
As well, a
formula is equivalent to a formula that begins with some existential quantifiers and alternates times between series of existential and universal quantifiers; while a formula is equivalent to a formula that begins with some universal quantifiers and alternates similarly.Because every formula is equivalent to a formula in 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 with no set quantifiers is assigned at least one classification. Because meaningless quantifiers can be added to any formula, once a formula is assigned the classification
or it will be assigned the classifications and for every m greater than n. The most important classification assigned to a formula is thus the one with the least n, because this is enough to determine all the other classifications.The arithmetical hierarchy of sets of natural numbers
A set X of natural numbers is defined by formula φ in the language of Peano arithmetic if the elements of X are exactly the numbers that satisfy φ. That is, for all natural numbers n,where
is the numeral in the language of arithmetic corresponding to . A set is definable in first order arithmetic if it is defined by some formula in the language of Peano arithmetic.Each set X of natural numbers that is definable in first order arithmetic is assigned classifications of the form
, , and , where is a natural number, as follows. If X is definable by a formula then X is assigned the classification . If X is definable by a formula then X is assigned the classification . If X is both and then is assigned the additional classification .Note that it rarely makes sense to speak of
formulas; the first quantifier of a formula is either existential or universal. So a set is not defined by a formula; rather, there are both and formulas that define the set.A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of the natural numbers. Instead of formulas with one free variable, formulas with k free number variables are used to define the arithmetical hierarchy on sets of k-tuple
Tuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
s of natural numbers.
Relativized arithmetical hierarchies
Just as we can define what it means for a set X to be recursiveRecursive set
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....
relative to another set Y by allowing the computation defining X to consult Y as an oracle we can extend this notion to the whole arithmetic hierarchy and define what it means for X to be
, or in Y, denoted respectively and . To do so, fix a set of integers Y and add a predicate for membership in Y to the language of Peano arithmetic. We then say that X is in if it is defined by a formula in this expanded language. In other words X is if it is defined by a formula allowed to ask questions about membership in Y. Alternatively one can view the sets as those sets that can be built starting with sets recursive in Y and alternatively projecting and taking the complements of these sets up to n times.For example let Y be a set of integers. Let X be the set of numbers divisible by an element of Y. Then X is defined by the formula
so X is in (actually it is in as well since we could bound both quantifiers by n).Arithmetic reducibility and degrees
Arithmetical reducibility is an intermediate notion between Turing reducibility and hyperarithmetic reducibility.A set is arithmetical (also arithmetic and arithmetically definable) if it is defined by some formula in the language of Peano arithmetic. Equivalently X is arithmetical if X is
or for some integer n. A set X is arithmetical in a set Y, denoted , if X is definable a some formula in the language of Peano arithmetic extended by a predicate for membership in Y. Equivalently, X is arithmetical in Y if X is in or for some integer n. A synonym for is: X is arithmetically reducible to YThe relation
is reflexive and transitive, and thus the relation defined by the ruleis an equivalence relation. The equivalence classes of this relation are called the arithmetic degrees; they are partially ordered under
.The arithmetical hierarchy of subsets of Cantor and Baire space
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...
, denoted
, is the set of all infinite sequences of 0s and 1s; 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 ωω...
, denoted
or , is the set of all infinite sequences of natural numbers. Note that elements of the Cantor space can be identified with sets of integers and elements of the Baire space with functions from integers to integers.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 . For example let be the set of all infinite binary strings which aren't all 0 (or equivalently the set of all non-empty sets of integers). As we see that is defined by a formula and hence is a set.Note that while both the elements of the Cantor space (regarded as sets of integers) and subsets of the Cantor space are classified in arithmetic hierarchies but these are not the same hierarchy. In fact the relationship between the two hierarchies is interesting and non-trivial. For instance the
elements of the Cantor space are not (in general) the same as the elements of the Cantor space so that is a subset of the Cantor space. However, many interesting results relate the two hierarchies.There are two ways that a subset of Baire space can be classified in the arithmetical hierarchy.
- A subset of Baire space has a corresponding subset of Cantor space under the map that takes each function from
to 
to the characteristic functionCharacteristic functionIn mathematics, characteristic function can refer to any of several distinct concepts:* The most common and universal usage is as a synonym for indicator function, that is the function* In probability theory, the characteristic function of any probability distribution on the real line is given by...
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.
A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of Baire space or Cantor space, using formulas with several free variables. The arithmetical hierarchy can be defined on any effective Polish space
Effective 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 space and Baire space because they fit with the language of ordinary second-order arithmetic.
Note that we can also define the arithmetic hierarchy of subsets of the Cantor and Baire spaces relative to some set of integers. In fact boldface
is just the union of for all sets of integers Y. Note that the boldface hierarchy is just the standard hierarchy of Borel setsBorel 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...
.
Extensions and variations
It is possible to define the arithmetical hierarchy of formulas using a language extended with a function symbol for each primitive recursive functionPrimitive recursive function
The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions...
. This variation slightly changes the classification of some sets.
A more semantic variation of the hierarchy can be defined on all finitary relations on the natural numbers; the following definition is used. Every computable relation is defined to be
and . The classifications and are defined inductively with the following rules.
- If the relation
is 
then the relation 
is defined to be 
- If the relation
is 
then the relation 
is defined to be 
This variation slightly changes the classification of some sets. It can be extended to cover finitary relations on the natural numbers, Baire space, and Cantor space.
Meaning of the notation
The following meanings can be attached to the notation for the arithmetical hierarchy on formulas.The subscript
in the symbols and indicates the number of alternations of blocks of universal and existential number quantifiers that are used in a formula. Moreover, the outermost block is existential in formulas and universal in formulas.The superscript
in the symbols , , and indicates the type of the objects being quantified over. Type 0 objects are natural numbers, and objects of type are functions that map the set of objects of type to the natural numbers. Quantification over higher type objects, such as functions from natural numbers to natural numbers, is described by a superscript greater than 0, as in the analytical hierarchyAnalytical 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:...
. The superscript 0 indicates quantifiers over numbers, the superscript 1 would indicate quantification over functions from numbers to numbers (type 1 objects), the superscript 2 would correspond to quantification over functions that take a type 1 object and return a number, and so on.
Examples
- The
sets of numbers are those definable by a formula of the form 
where 
has only bounded quantifiers. These are exactly the recursively enumerable setRecursively enumerable setIn computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:...
s.
- The set of natural numbers that are indices for Turing machines that compute total functions is
. Intuitively, an index 
falls into this set if and only if for every 
"there is an 
such that the Turing machine with index 
halts on input 
after 
steps”. A complete proof would show that the property displayed in quotes in the previous sentence is definable in the language of Peano arithmetic by a 
formula.
- Every
subset of Baire space or Cantor space is an open set in the usual topology on the space. Moreover, for any such set there is a computable enumeration of Gödel numbers of basic open sets whose union is the original set. For this reason, 
sets are sometimes called effectively open. Similarly, every 
set is closed and the 
sets are sometimes called effectively closed.
- Every arithmetical subset of Cantor space of Baire space is a Borel setBorel setIn 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...
. The lightface Borel hierarchy extends the arithmetical hierarchy to include additional Borel sets. For example, every
subset of Cantor or Baire space is a 
set (that is, a set which equals the intersection of countably many open sets). Moreover, each of these open sets is 
and the list of Gödel numbers of these open sets has a computable enumeration. If 
is a 
formula with a free set variable X and free number variables 
then the 
set 
is the intersection of the 
sets of the form 
as n ranges over the set of natural numbers.
Properties
The following properties hold for the arithmetical hierarchy of sets of natural numbers and the arithmetical hierarchy of subsets of Cantor or Baire space.- The collections
and 
are closed under finite unionUnion (set theory)In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
s and finite intersectionIntersection (set theory)In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
s of their respective elements. - A set is
if and only if its complement is 
. A set is 
if and only if the set is both 
and 
, in which case its complement will also be 
. - The inclusions
and 
hold for 
. - The inclusions
and 
hold for all 
and the inclusion 
holds for 
. Thus the hierarchy does not collapse.
Relation to Turing machines
The Turing computable sets of natural numbers are exactly the sets at level of the arithmetical hierarchy. The recursively enumerable sets are exactly the sets at level .No oracle machine
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
is capable of solving its own halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
(a variation of Turing's proof applies). The halting problem for a
oracle in fact sits in .Post's theorem
Post's theorem
In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.- Background :The statement of Post's theorem uses several concepts relating to definability and recursion theory...
establishes a close connection between the arithmetical hierarchy of sets of natural numbers and the Turing degree
Turing degree
In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set...
s. In particular, it establishes the following facts for all n ≥ 1:
- The set
(the nth Turing jumpTuring jumpIn computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine with an oracle for .The operator is called a jump...
of the empty set) is many-one completeMany-one reductionIn computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
in
. - The set
is many-one complete in 
. - The set
is Turing complete in 
.
The polynomial hierarchy
Polynomial hierarchy
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...
is a "feasible resource-bounded" version of the arithmetical hierarchy in which polynomial length bounds are placed on the numbers involved (or, equivalently, polynomial time bounds are placed on the Turing machines involved). It gives a finer classification of some sets of natural numbers that are at level
of the arithmetical hierarchy.