Arithmetical hierarchy

The arithmetical hierachy (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 hierachy are defined as those forumlas which satisfy a proposition (description) of a certain complexity.

For example, the category $\Sigma _{1}$, also written as $\Sigma _{1}^{0}$, are those which satisfy propositions with one existential quantifier:

$\exists x_{1}:$ proposition holds

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

A formula is in the level $\Sigma _{n}^{0}$ if it satisfies a proposition quantified first by $\exists$, and a total of n alternating existential ($\exists$) and universal ($\forall$) quantifiers.

Formulas are classified as $\Pi _{n}^{0}$ in an equivalent fashion, except that the quantifiers commence with $\forall$.

Formulas are in the level $\Delta _{n}^{0}$ if they are in both $\Sigma _{n}^{0}$ and $\Pi _{n}^{0}$.

See also: recusion theory, analytical hierarchy.