In mathematical logic, the arithmetical hierarchy (also known as the arithmetic hierarchy) classifies the set of all formulas (or functions) according to their degree of solvability.

Each formula or function is equivalent to a Turing machine.

Layers in the hierarchy are defined as those formulas which satisfy a proposition (description) of a certain complexity.

For example, the category Σ₁, also written as , are those which satisfy propositions with one existential quantifier:

proposition holds

These are precisely the recursively enumerable sets (think: there exists a program with the following property).

A formula is in the level if it satisfies a proposition quantified first by , and a total of n alternating existential () and universal () quantifiers.

Formulas are classified as in an equivalent fashion, except that the quantifiers commence with .

Formulas are in the level if they are in both and .

Suppose that there is an oracle machine capable of calculating all the functions in a level . This machine is incapable of solving its own halting problem (Turing's proof still applies). The halting problem for in fact sits in .

Post's theorem describes the close connection between the arithmetical hierarchy and the Turing degrees.

The polynomial hierarchy is a "feasible resource-bounded" version of the arithmetical hierarchy, in which polynomial length bounds are placed on the strings involved, or equivalently, polynomial time bounds are placed on the Turing machines involved.

See also: recursion theory, analytical hierarchy, interpretability logic.

References

• G.Japaridze, The logic of the arithmetical hierarchy. In: Annals of Pure and Applied Logic 66 (1994), pp.89-112.