Arithmetical hierarchy
The arithmetical hierarchy was invented independently by Kleene (1943) and Mostowski (1946).
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 Greek letters here are lightface symbols, which indicates that the formulas do not contain set parameters.
are defined inductively for every natural number n using the following rules:
times between series of existential and universal quantifiers; while a
A set X of natural numbers is defined by a formula φ in the language of Peano arithmetic (the first-order language with symbols "0" for zero, "S" for the successor function, "+" for addition, "×" for multiplication, and "=" for equality), if the elements of X are exactly the numbers that satisfy φ.
Each set X of natural numbers that is definable in first-order arithmetic is assigned classifications of the form
A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of the set of natural numbers.
Instead of formulas with one free variable, formulas with k free first-order variables are used to define the arithmetical hierarchy on sets of k-tuples of natural numbers.
The following meanings can be attached to the notation for the arithmetical hierarchy on formulas.
indicates the number of alternations of blocks of universal and existential first-order quantifiers that are used in a formula.
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.
To do so, fix a set of natural numbers Y and add a predicate for membership of Y to the language of Peano arithmetic.
formula allowed to ask questions about membership of Y. Alternatively one can view the
The equivalence classes of this relation are called the arithmetic degrees; they are partially ordered under
, is the set of all infinite sequences of 0s and 1s; the Baire space, denoted
, is the set of all infinite sequences of natural numbers.
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.
Note that while both the elements of the Cantor space (regarded as sets of natural numbers) and subsets of the Cantor space are classified in arithmetic hierarchies, these are not the same hierarchy.
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.
Note that we can also define the arithmetic hierarchy of subsets of the Cantor and Baire spaces relative to some set of natural numbers.
, since using primitive recursive functions in first-order Peano arithmetic requires, in general, an unbounded existential quantifier, and thus some sets that are in
A more semantic variation of the hierarchy can be defined on all finitary relations on the natural numbers; the following definition is used.
The following properties hold for the arithmetical hierarchy of sets of natural numbers and the arithmetical hierarchy of subsets of Cantor or Baire space.
and are therefore (by Post's theorem) recursively enumerable by some Turing machines T1 and T2, respectively.
No oracle machine is capable of solving its own halting problem (a variation of Turing's proof applies).
Post's theorem establishes a close connection between the arithmetical hierarchy of sets of natural numbers and the Turing degrees.
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
