This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(June 2021) (Learn how and when to remove this message)

Inmathematical logic, thearithmetical hierarchy,arithmetic hierarchy orKleene–Mostowski hierarchy (after mathematiciansStephen Cole Kleene andAndrzej Mostowski) classifies certainsets based on the complexity offormulas thatdefine them. Any set that receives a classification is calledarithmetical. The arithmetical hierarchy was invented independently by Kleene (1943) and Mostowski (1946).^[1]

The arithmetical hierarchy is important incomputability theory,effective descriptive set theory, and the study offormal theories such asPeano arithmetic.

TheTarski–Kuratowski algorithm provides an easy way to get an upper bound on the classifications assigned to a formula and the set it defines.

Thehyperarithmetical hierarchy and theanalytical hierarchy extend the arithmetical hierarchy to classify additional formulas and sets.

The arithmetical hierarchy assigns classifications to the formulas in the language offirst-order arithmetic. The classifications are denoted${\displaystyle {\mathrm{\Sigma }}_n^0}$ and${\displaystyle {\mathrm{\Pi }}_n^0}$ fornatural numbersn (including 0). The Greek letters here arelightface symbols, which indicates that the formulas do not containset parameters.^{[clarification needed]}

If a formula${\displaystyle \varphi }$ islogically equivalent to a formula having no unbounded quantifiers, i.e. in which all quantifiers arebounded quantifiers then${\displaystyle \varphi }$ is assigned the classifications${\displaystyle {\mathrm{\Sigma }}_0^0}$ and${\displaystyle {\mathrm{\Pi }}_0^0}$.

The classifications${\displaystyle {\mathrm{\Sigma }}_n^0}$ and${\displaystyle {\mathrm{\Pi }}_n^0}$ are defined inductively for every natural numbern using the following rules:

• If${\displaystyle \varphi }$ is logically equivalent to a formula of the form${\displaystyle \mathrm{\exists }{m}_1\mathrm{\exists }{m}_2\cdots \mathrm{\exists }{m}_k\psi }$, where${\displaystyle \psi }$ is${\displaystyle {\mathrm{\Pi }}_n^0}$, then${\displaystyle \varphi }$ is assigned the classification${\displaystyle {\mathrm{\Sigma }}_{n+1}^0}$.
• If${\displaystyle \varphi }$ is logically equivalent to a formula of the form${\displaystyle \mathrm{\forall }{m}_1\mathrm{\forall }{m}_2\cdots \mathrm{\forall }{m}_k\psi }$, where${\displaystyle \psi }$ is${\displaystyle {\mathrm{\Sigma }}_n^0}$, then${\displaystyle \varphi }$ is assigned the classification${\displaystyle {\mathrm{\Pi }}_{n+1}^0}$.

A${\displaystyle {\mathrm{\Sigma }}_n^0}$ formula is equivalent to a formula that begins with someexistential quantifiers and alternates${\displaystyle n-1}$ times between series of existential anduniversal quantifiers; while a${\displaystyle {\mathrm{\Pi }}_n^0}$ formula is equivalent to a formula that begins with some universal quantifiers and alternates analogously.

Because every first-order formula has aprenex 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${\displaystyle {\mathrm{\Sigma }}_n^0}$ or${\displaystyle {\mathrm{\Pi }}_n^0}$ it will be assigned the classifications${\displaystyle {\mathrm{\Sigma }}_m^0}$ and${\displaystyle {\mathrm{\Pi }}_m^0}$ for everym >n. The only relevant classification assigned to a formula is thus the one with the leastn; all the other classifications can be determined from it.

A setX of natural numbers is defined by a formulaφ in the language ofPeano 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 ofX are exactly the numbers that satisfyφ. That is, for all natural numbersn,

${\displaystyle n\in X\iff \mathbb{N}\models \phi (\underset{\_}{n}),}$

where${\displaystyle \underset{\_}{n}}$ is the numeral in the language of arithmetic corresponding to${\displaystyle n}$. A set is definable in first-order arithmetic if it is defined by some formula in the language of Peano arithmetic.

Each setX of natural numbers that is definable in first-order arithmetic is assigned classifications of the form${\displaystyle {\mathrm{\Sigma }}_n^0}$,${\displaystyle {\mathrm{\Pi }}_n^0}$, and${\displaystyle {\mathrm{\Delta }}_n^0}$, where${\displaystyle n}$ is a natural number, as follows. IfX is definable by a${\displaystyle {\mathrm{\Sigma }}_n^0}$ formula thenX is assigned the classification${\displaystyle {\mathrm{\Sigma }}_n^0}$. IfX is definable by a${\displaystyle {\mathrm{\Pi }}_n^0}$ formula thenX is assigned the classification${\displaystyle {\mathrm{\Pi }}_n^0}$. IfX is both${\displaystyle {\mathrm{\Sigma }}_n^0}$ and${\displaystyle {\mathrm{\Pi }}_n^0}$ then${\displaystyle X}$ is assigned the additional classification${\displaystyle {\mathrm{\Delta }}_n^0}$.

Note that it rarely makes sense to speak of${\displaystyle {\mathrm{\Delta }}_n^0}$ formulas; the first quantifier of a formula is either existential or universal. So a${\displaystyle {\mathrm{\Delta }}_n^0}$ set is not necessarily defined by a${\displaystyle {\mathrm{\Delta }}_n^0}$ formula in the sense of a formula that is both${\displaystyle {\mathrm{\Sigma }}_n^0}$ and${\displaystyle {\mathrm{\Pi }}_n^0}$; rather, there are both${\displaystyle {\mathrm{\Sigma }}_n^0}$ and${\displaystyle {\mathrm{\Pi }}_n^0}$ formulas that define the set. For example, the set of odd natural numbers${\displaystyle n}$ is definable by either${\displaystyle \mathrm{\forall }k(n\ne 2\times k)}$ or${\displaystyle \mathrm{\exists }k(n=2\times k+1)}$.

A parallel definition is used to define the arithmetical hierarchy on finiteCartesian powers of the set of natural numbers. Instead of formulas with one free variable, formulas withk free first-order variables are used to define the arithmetical hierarchy on sets ofk-tuples of natural numbers. These are in fact related by the use of apairing function.

The following meanings can be attached to the notation for the arithmetical hierarchy on formulas.

The subscript${\displaystyle n}$ in the symbols${\displaystyle {\mathrm{\Sigma }}_n^0}$ and${\displaystyle {\mathrm{\Pi }}_n^0}$ indicates the number of alternations of blocks of universal and existential first-order quantifiers that are used in a formula. Moreover, the outermost block is existential in${\displaystyle {\mathrm{\Sigma }}_n^0}$ formulas and universal in${\displaystyle {\mathrm{\Pi }}_n^0}$ formulas.

The superscript${\displaystyle 0}$ in the symbols${\displaystyle {\mathrm{\Sigma }}_n^0}$,${\displaystyle {\mathrm{\Pi }}_n^0}$, and${\displaystyle {\mathrm{\Delta }}_n^0}$ indicates the type of the objects being quantified over. Type 0 objects are natural numbers, and objects of type${\displaystyle i+1}$ are functions that map the set of objects of type${\displaystyle i}$ 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 theanalytical 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.

• The${\displaystyle {\mathrm{\Sigma }}_1^0}$ sets of numbers are those definable by a formula of the form${\displaystyle \mathrm{\exists }{n}_1\cdots \mathrm{\exists }{n}_k\psi (n_1,\dots ,n_k,m)}$ where${\displaystyle \psi }$ has only bounded quantifiers. These are exactly therecursively enumerable sets.
• The set of natural numbers that are indices forTuring machines that compute total functions is${\displaystyle {\mathrm{\Pi }}_2^0}$. Intuitively, an index${\displaystyle e}$ falls into this set if and only if for every${\displaystyle m}$ "there is an${\displaystyle s}$ such that the Turing machine with index${\displaystyle e}$ halts on input${\displaystyle m}$ after${\displaystyle s}$ steps". A complete proof would show that the property displayed in quotes in the previous sentence is definable in the language ofPeano arithmetic by a${\displaystyle {\mathrm{\Sigma }}_1^0}$ formula.
• Every${\displaystyle {\mathrm{\Sigma }}_1^0}$ subset ofBaire space orCantor space is anopen set in the usualtopology on the space. Moreover, for any such set there is a computable enumeration ofGödel numbers of basic open sets whose union is the original set. For this reason,${\displaystyle {\mathrm{\Sigma }}_1^0}$ sets are sometimes calledeffectively open. Similarly, every${\displaystyle {\mathrm{\Pi }}_1^0}$ set is closed and the${\displaystyle {\mathrm{\Pi }}_1^0}$ sets are sometimes calledeffectively closed.
• Every arithmetical subset of Cantor space or Baire space is aBorel set. The lightfaceBorel hierarchy extends the arithmetical hierarchy to include additional Borel sets. For example, every${\displaystyle {\mathrm{\Pi }}_2^0}$ subset of Cantor or Baire space isa${\displaystyle G_{\delta }}$ set, that is, a set that equals the intersection of countably many open sets. Moreover, each of these open sets is${\displaystyle {\mathrm{\Sigma }}_1^0}$ and the list of Gödel numbers of these open sets has a computable enumeration. If${\displaystyle \varphi (X,n,m)}$ is a${\displaystyle {\mathrm{\Sigma }}_0^0}$ formula with a free set variable${\displaystyle X}$ and free number variables${\displaystyle n,m}$ then the${\displaystyle {\mathrm{\Pi }}_2^0}$ set${\displaystyle \{X\mid \mathrm{\forall }n\mathrm{\exists }m\varphi (X,n,m)\}}$ is the intersection of the${\displaystyle {\mathrm{\Sigma }}_1^0}$ sets of the form${\displaystyle \{X\mid \mathrm{\exists }m\varphi (X,n,m)\}}$ as${\displaystyle n}$ ranges over the set of natural numbers.
• The${\displaystyle {\mathrm{\Sigma }}_0^0={\mathrm{\Pi }}_0^0={\mathrm{\Delta }}_0^0}$ formulas can be checked by going over all cases one by one, which is possible because all their quantifiers are bounded. The time for this is polynomial in their arguments (e.g. polynomial in${\displaystyle n}$ for${\displaystyle \phi (n)}$); thus their corresponding decision problems are included inE (as${\displaystyle n}$ is exponential in its number of bits). This no longer holds under alternative definitions of${\displaystyle {\mathrm{\Sigma }}_0^0={\mathrm{\Pi }}_0^0={\mathrm{\Delta }}_0^0}$ that allow the use ofprimitive recursive functions, as now the quantifiers may be bounded by any primitive recursive function of the arguments.
• The${\displaystyle {\mathrm{\Sigma }}_0^0={\mathrm{\Pi }}_0^0={\mathrm{\Delta }}_0^0}$ formulas under an alternative definition, that allows the use ofprimitive recursive functions withbounded quantifiers, correspond to sets of natural numbers of the form${\displaystyle \{n:f(n)=0\}}$ for a primitive recursive function${\displaystyle f}$. This is because allowing bounded quantifier adds nothing to the definition: for a primitive recursive${\displaystyle f}$, is the same as${\displaystyle f(0)+f(1)+...f(n-1)=0}$, and is the same as${\displaystyle f(0)\cdot f(1)\cdot \dots \cdot f(n-1)=0}$; withcourse-of-values recursion each of these can be defined by a single primitive recursive function.

Just as we can define what it means for a setX to berecursive relative to another setY by allowing the computation definingX to consultY as anoracle we can extend this notion to the whole arithmetic hierarchy and define what it means forX to be${\displaystyle {\mathrm{\Sigma }}_n^0}$,${\displaystyle {\mathrm{\Delta }}_n^0}$ or${\displaystyle {\mathrm{\Pi }}_n^0}$ inY, denoted respectively${\displaystyle {\mathrm{\Sigma }}_n^{0,Y}}$,${\displaystyle {\mathrm{\Delta }}_n^{0,Y}}$ and${\displaystyle {\mathrm{\Pi }}_n^{0,Y}}$. To do so, fix a set of natural numbersY and add apredicate for membership ofY to the language of Peano arithmetic. We then say thatX is in${\displaystyle {\mathrm{\Sigma }}_n^{0,Y}}$ if it is defined by a${\displaystyle {\mathrm{\Sigma }}_n^0}$ formula in this expanded language. In other words,X is${\displaystyle {\mathrm{\Sigma }}_n^{0,Y}}$ if it is defined by a${\displaystyle {\mathrm{\Sigma }}_n^0}$ formula allowed to ask questions about membership ofY. Alternatively one can view the${\displaystyle {\mathrm{\Sigma }}_n^{0,Y}}$ sets as those sets that can be built starting with sets recursive inY and alternately takingunions andintersections of these sets up ton times.

For example, letY be a set of natural numbers. LetX be the set of numbersdivisible by an element ofY. ThenX is defined by the formula${\displaystyle \varphi (n)=\mathrm{\exists }m\mathrm{\exists }t(Y(m)\wedge m\times t=n)}$ soX is in${\displaystyle {\mathrm{\Sigma }}_1^{0,Y}}$ (actually it is in${\displaystyle {\mathrm{\Delta }}_0^{0,Y}}$ as well, since we could bound both quantifiers byn).

Arithmetical reducibility is an intermediate notion betweenTuring reducibility andhyperarithmetic reducibility.

A set isarithmetical (alsoarithmetic andarithmetically definable) if it is defined by some formula in the language of Peano arithmetic. EquivalentlyX is arithmetical ifX is${\displaystyle {\mathrm{\Sigma }}_n^0}$ or${\displaystyle {\mathrm{\Pi }}_n^0}$ for some natural numbern. A setXis arithmetical in a setY, denoted${\displaystyle X{\le }_{A}Y}$, ifX is definable as some formula in the language of Peano arithmetic extended by a predicate for membership ofY. Equivalently,X is arithmetical inY ifX is in${\displaystyle {\mathrm{\Sigma }}_n^{0,Y}}$ or${\displaystyle {\mathrm{\Pi }}_n^{0,Y}}$ for some natural numbern. A synonym for${\displaystyle X{\le }_{A}Y}$ is:X isarithmetically reducible toY.

The relation${\displaystyle X{\le }_{A}Y}$ isreflexive andtransitive, and thus the relation${\displaystyle {\equiv }_A}$ defined by the rule

${\displaystyle X{\equiv }_{A}Y⟺X{\le }_{A}Y\wedge Y{\le }_{A}X}$

is anequivalence relation. Theequivalence classes of this relation are called thearithmetic degrees; they arepartially ordered under${\displaystyle {\le }_A}$.

TheCantor space, denoted${\displaystyle 2^{\omega }}$, is the set of all infinite sequences of 0s and 1s; theBaire space, denoted${\displaystyle {\omega }^{\omega }}$ or${\displaystyle \mathcal{N}}$, is the set of all infinite sequences of natural numbers. Note that elements of the Cantor space can be identified with sets of natural numbers and elements of the Baire space with functions from natural numbers to natural numbers.

The ordinary axiomatization ofsecond-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${\displaystyle {\mathrm{\Sigma }}_n^0}$ if it is definable by a${\displaystyle {\mathrm{\Sigma }}_n^0}$ formula. The set is assigned the classification${\displaystyle {\mathrm{\Pi }}_n^0}$ if it is definable by a${\displaystyle {\mathrm{\Pi }}_n^0}$ formula. If the set is both${\displaystyle {\mathrm{\Sigma }}_n^0}$ and${\displaystyle {\mathrm{\Pi }}_n^0}$ then it is given the additional classification${\displaystyle {\mathrm{\Delta }}_n^0}$. For example, let${\displaystyle O\subseteq 2^{\omega }}$ be the set of all infinite binary strings that aren't all 0 (or equivalently the set of all non-empty sets of natural numbers). As${\displaystyle O=\{X\in 2^{\omega }|\mathrm{\exists }n(X(n)=1)\}}$ we see that${\displaystyle O}$ is defined by a${\displaystyle {\mathrm{\Sigma }}_1^0}$ formula and hence is a${\displaystyle {\mathrm{\Sigma }}_1^0}$ set.

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. In fact the relationship between the two hierarchies is interesting and non-trivial. For instance the${\displaystyle {\mathrm{\Pi }}_n^0}$ elements of the Cantor space are not (in general) the same as the elements${\displaystyle X}$ of the Cantor space so that${\displaystyle \{X\}}$ is a${\displaystyle {\mathrm{\Pi }}_n^0}$ 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${\displaystyle \omega }$ to${\displaystyle \omega }$ to thecharacteristic function of its graph. A subset of Baire space is given the classification${\displaystyle {\mathrm{\Sigma }}_n^0}$,${\displaystyle {\mathrm{\Pi }}_n^0}$, or${\displaystyle {\mathrm{\Delta }}_n^0}$ if and only if the corresponding subset of Cantor space has the same classification.
• An equivalent definition of the arithmetical hierarchy on Baire space is given by defining the arithmetical hierarchy of formulas using a functional version of second-order arithmetic; then the arithmetical 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 anyeffective 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 natural numbers. In fact boldface${\displaystyle {\mathbf{\Sigma }}_n^0}$ is just the union of${\displaystyle {\mathrm{\Sigma }}_n^{0,Y}}$ for all sets of natural numbersY. Note that the boldface hierarchy is just the standard hierarchy ofBorel sets.

It is possible to define the arithmetical hierarchy of formulas using a language extended with a function symbol for eachprimitive recursive function. This variation slightly changes the classification of${\displaystyle {\mathrm{\Sigma }}_0^0={\mathrm{\Pi }}_0^0={\mathrm{\Delta }}_0^0}$, sinceusing primitive recursive functions in first-order Peano arithmetic requires, in general, an unbounded existential quantifier, and thus some sets that are in${\displaystyle {\mathrm{\Sigma }}_0^0}$ by this definition are strictly in${\displaystyle {\mathrm{\Sigma }}_1^0}$ by the definition given in the beginning of this article. The class${\displaystyle {\mathrm{\Sigma }}_1^0}$ 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${\displaystyle {\mathrm{\Sigma }}_0^0={\mathrm{\Pi }}_0^0={\mathrm{\Delta }}_0^0}$. The classifications${\displaystyle {\mathrm{\Sigma }}_n^0}$ and${\displaystyle {\mathrm{\Pi }}_n^0}$ are defined inductively with the following rules.

• If the relation${\displaystyle R(n_1,\dots ,n_l,m_1,\dots ,m_k)}$ is${\displaystyle {\mathrm{\Sigma }}_n^0}$ then the relation${\displaystyle S(n_1,\dots ,n_l)=\mathrm{\forall }{m}_1\cdots \mathrm{\forall }{m}_{k}R(n_1,\dots ,n_l,m_1,\dots ,m_k)}$ is defined to be${\displaystyle {\mathrm{\Pi }}_{n+1}^0}$
• If the relation${\displaystyle R(n_1,\dots ,n_l,m_1,\dots ,m_k)}$ is${\displaystyle {\mathrm{\Pi }}_n^0}$ then the relation${\displaystyle S(n_1,\dots ,n_l)=\mathrm{\exists }{m}_1\cdots \mathrm{\exists }{m}_{k}R(n_1,\dots ,n_l,m_1,\dots ,m_k)}$ is defined to be${\displaystyle {\mathrm{\Sigma }}_{n+1}^0}$

This variation slightly changes the classification of some sets. In particular,${\displaystyle {\mathrm{\Sigma }}_0^0={\mathrm{\Pi }}_0^0={\mathrm{\Delta }}_0^0}$, as a class of sets (definable by the relations in the class), is identical to${\displaystyle {\mathrm{\Delta }}_1^0}$ as the latter was formerly defined. It can be extended to cover finitary relations on the natural numbers, Baire space, and Cantor space.

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${\displaystyle {\mathrm{\Pi }}_n^0}$ and${\displaystyle {\mathrm{\Sigma }}_n^0}$ are closed under finiteunions and finiteintersections of their respective elements.
• A set is${\displaystyle {\mathrm{\Sigma }}_n^0}$ if and only if its complement is${\displaystyle {\mathrm{\Pi }}_n^0}$. A set is${\displaystyle {\mathrm{\Delta }}_n^0}$ if and only if the set is both${\displaystyle {\mathrm{\Sigma }}_n^0}$ and${\displaystyle {\mathrm{\Pi }}_n^0}$, in which case its complement will also be${\displaystyle {\mathrm{\Delta }}_n^0}$.
• The inclusions${\displaystyle {\mathrm{\Pi }}_n^0⊊{\mathrm{\Pi }}_{n+1}^0}$ and${\displaystyle {\mathrm{\Sigma }}_n^0⊊{\mathrm{\Sigma }}_{n+1}^0}$ hold for all${\displaystyle n}$. Thus the hierarchy does not collapse. This is a direct consequence ofPost's theorem.
• The inclusions${\displaystyle {\mathrm{\Delta }}_n^0⊊{\mathrm{\Pi }}_n^0}$,${\displaystyle {\mathrm{\Delta }}_n^0⊊{\mathrm{\Sigma }}_n^0}$ and${\displaystyle {\mathrm{\Sigma }}_n^0\cup {\mathrm{\Pi }}_n^0⊊{\mathrm{\Delta }}_{n+1}^0}$ hold for${\displaystyle n\ge 1}$.

• For example, for auniversal Turing machineT, the set of pairs (n,m) such thatT halts onn but not onm, is in${\displaystyle {\mathrm{\Delta }}_2^0}$ (being computable with an oracle to the halting problem) but not in${\displaystyle {\mathrm{\Sigma }}_1^0\cup {\mathrm{\Pi }}_1^0}$.
• ${\displaystyle {\mathrm{\Sigma }}_0^0={\mathrm{\Pi }}_0^0={\mathrm{\Delta }}_0^0={\mathrm{\Sigma }}_0^0\cup {\mathrm{\Pi }}_0^0\subseteq {\mathrm{\Delta }}_1^0}$. The inclusion is strict by the definition given in this article, but an identity with${\displaystyle {\mathrm{\Delta }}_1^0}$ holds under one of the variations of the definitiongiven above.

IfS is aTuring computable set, then bothS and itscomplement are recursively enumerable (ifT is a Turing machine giving 1 for inputs inS and 0 otherwise, we may build a Turing machine halting only on the former, and another halting only on the latter).

ByPost's theorem, bothS and its complement are in${\displaystyle {\mathrm{\Sigma }}_1^0}$. This means thatS is both in${\displaystyle {\mathrm{\Sigma }}_1^0}$ and in${\displaystyle {\mathrm{\Pi }}_1^0}$, and hence it is in${\displaystyle {\mathrm{\Delta }}_1^0}$.

Similarly, for every setS in${\displaystyle {\mathrm{\Delta }}_1^0}$, bothS and its complement are in${\displaystyle {\mathrm{\Sigma }}_1^0}$ and are therefore (byPost's theorem) recursively enumerable by some Turing machinesT₁ andT₂, respectively. For every numbern, exactly one of these halts. We may therefore construct a Turing machineT that alternates betweenT₁ andT₂, halting and returning 1 when the former halts or halting and returning 0 when the latter halts. ThusT halts on everyn and returns whether it is inS; soS is computable.

The Turing computable sets of natural numbers are exactly the sets at level${\displaystyle {\mathrm{\Delta }}_1^0}$ of the arithmetical hierarchy. The recursively enumerable sets are exactly the sets at level${\displaystyle {\mathrm{\Sigma }}_1^0}$.

Nooracle machine is capable of solving its ownhalting problem (a variation of Turing's proof applies). The halting problem for a${\displaystyle {\mathrm{\Delta }}_n^{0,Y}}$ oracle in fact sits in${\displaystyle {\mathrm{\Sigma }}_{n+1}^{0,Y}}$.

Post's theorem establishes a close connection between the arithmetical hierarchy of sets of natural numbers and theTuring degrees. In particular, it establishes the following facts for alln ≥ 1:

• The set${\displaystyle {\mathrm{\varnothing }}^{(n)}}$ (thenthTuring jump of the empty set) ismany-one complete in${\displaystyle {\mathrm{\Sigma }}_n^0}$.
• The set${\displaystyle \mathbb{N}\setminus {\mathrm{\varnothing }}^{(n)}}$ is many-one complete in${\displaystyle {\mathrm{\Pi }}_n^0}$.
• The set${\displaystyle {\mathrm{\varnothing }}^{(n-1)}}$ isTuring complete in${\displaystyle {\mathrm{\Delta }}_n^0}$.

Thepolynomial 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${\displaystyle {\mathrm{\Delta }}_1^0}$ of the arithmetical hierarchy.

• Analytical hierarchy
• Lévy hierarchy
• Hierarchy (mathematics)
• Interpretability logic
• Polynomial hierarchy

• Mathematical logic hierarchies
• Computability theory
• Effective descriptive set theory
• Hierarchy
• Complexity classes

• Articles lacking in-text citations from June 2021
• All articles lacking in-text citations
• Articles with short description
• Short description is different from Wikidata
• Wikipedia articles needing clarification from August 2024