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 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 arithmetical hierarchy of formulas. The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic. The classifications are denoted formula_1 and formula_2 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 formula_3 is logically equivalent to a formula without quantifiers, then formula_3 is assigned the classifications formula_5 and formula_6. Since any formula with bounded quantifiers can be replaced by a formula without quantifiers (for example, formula_7 is equivalent to formula_8), we  can also allow formula_3 to have bounded quantifiers. The classifications formula_1 and formula_2 are defined inductively for every natural number "n" using the following rules: A formula_1 formula is equivalent to a formula that begins with some existential quantifiers and alternates formula_25 times between series of existential and universal quantifiers; while a formula_2 formula is equivalent to a formula that begins with some universal quantifiers and alternates analogously. Because every first-order formula has a prenex normal form, every formula is assigned at least one classification. Because redundant quantifiers can be added to any formula, once a formula is assigned  the classification formula_1 or formula_2 it will be assigned the classifications formula_29 and formula_30 for every "r > n". The only relevant classification assigned to a formula is thus the one with the least "n"; all the other classifications can be determined from it. The arithmetical hierarchy of sets of natural numbers. A set "X" of natural numbers is defined by 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 φ. That is, for all natural numbers "n", where formula_32 is the numeral in the language of arithmetic corresponding to formula_33. 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 formula_1, formula_2, and formula_36, where formula_33 is a natural number, as follows. If "X" is definable by a formula_1 formula then "X" is assigned the classification formula_1. If "X" is definable by a formula_2 formula  then "X" is assigned the classification formula_2. If "X" is both formula_1 and formula_2 then formula_44 is assigned the additional classification formula_36. Note that it rarely makes sense to speak of formula_36 formulas; the first quantifier of a formula is either existential or universal. So a formula_36 set is not defined by a formula_36 formula; rather, there are both formula_1 and formula_2 formulas that define the set. For example, the set of odd natural numbers formula_33 is definable by either formula_52 or formula_53. 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 number variables are used to define the arithmetical hierarchy on sets of "k"-tuples of natural numbers. These are in fact related by the use of a pairing function. Relativized arithmetical hierarchies. Just as we can define what it means for a set "X" to be recursive 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 formula_1, formula_36 or formula_2  in "Y", denoted respectively formula_57 formula_58 and formula_59. 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 formula_57 if it is defined by a formula_1 formula in this expanded language. In other words, "X" is formula_57 if it is defined by a formula_63 formula allowed to ask questions about membership in "Y". Alternatively one can view the formula_57 sets as those sets that can be built starting with sets recursive in "Y" and alternately taking unions and intersections 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 formula_65 so "X" is in formula_66 (actually it is in formula_67 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 formula_1 or formula_2 for some integer n". A set "X" is arithmetical in a set "Y", denoted formula_70, if "X" is definable as 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 formula_57 or formula_59 for some integer "n". A synonym for formula_70 is: "X" is arithmetically reducible to "Y". The relation formula_70 is reflexive and transitive, and thus the relation formula_75 defined by the rule is an equivalence relation. The equivalence classes of this relation are called the arithmetic degrees; they  are partially ordered under formula_77. The arithmetical hierarchy of subsets of Cantor and Baire space. The Cantor space, denoted formula_78, is the set of all infinite sequences of 0s and 1s; the Baire space, denoted formula_79 or formula_80, 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 formula_1 if it is definable by a formula_1 formula. The set is assigned the classification formula_2 if it is definable by a formula_2 formula. If the set is both formula_1 and formula_2 then it is given the additional classification formula_36. For example, let formula_88 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 formula_89 we see that formula_90 is defined by a formula_91 formula and hence is a formula_91 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, these are not the same hierarchy. In fact the relationship between the two hierarchies is interesting and non-trivial. For instance the formula_2 elements of the Cantor space are not (in general) the same as the elements formula_44 of the Cantor space so that formula_95 is a formula_2 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 formula_102 is just the union of formula_57 for all sets of integers "Y". Note that the  boldface hierarchy is just the standard hierarchy of Borel sets. 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 function. This variation slightly changes the classification of formula_104, since using primitive recursive functions in first-order Peano arithmetic requires, in general, an unbounded existential quantifier, and thus some sets that are in formula_5 by this definition are in formula_91 by the definition given in the beginning of this article. formula_91 and thus all higher classes in the hierarchy remain unaffected. 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 formula_104. The classifications formula_1 and formula_2 are defined inductively with the following rules. This variation slightly changes the classification of some sets. In particular, formula_104, as a class of sets (definable by the relations in the class), is identical to formula_120 as the latter was formerly defined. 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 formula_33 in the symbols formula_1 and formula_2 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 formula_1 formulas and universal in formula_2 formulas. The superscript formula_126 in the symbols formula_1, formula_2, and formula_36 indicates the type of the objects being quantified over. Type 0 objects are natural numbers, and objects of type formula_130 are functions that map the set of objects of type formula_131 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. 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. Relation to Turing machines. Computable sets. If S  is a Turing computable set, then both S and its complement are recursively enumerable (if T is a Turing machine giving 1 for inputs in S and 0 otherwise, we may build a Turing machine halting only on the former, and another halting only on the latter). By Post's theorem, both S and its complement are in formula_91. This means that S is both in formula_91 and in formula_145, and hence it is in formula_120. Similarly, for every set S in formula_120, both S and its complement are in formula_91 and are therefore (by Post's theorem) recursively enumerable  by some Turing machines T and T, respectively. For every number n, exactly one of these halts. We may therefore construct a Turing machine T that alternates between T and T, halting and returning 1 when the former halts or halting and returning 0 when the latter halts. Thus T halts on every n and returns whether it is in S, So S is computable. Summary of main results. The Turing computable sets of natural numbers are exactly the sets at level formula_120 of the arithmetical hierarchy. The recursively enumerable sets are exactly the sets at level formula_91. No oracle  machine is capable of solving its own halting problem (a variation of Turing's proof applies). The halting problem for a formula_58 oracle in fact sits in formula_194. 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 formula_120 of the arithmetical hierarchy.