Arithmetical hierarchy

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 forumlas 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 .

See also: recursion theory, analytical hierarchy.