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 <math>\Sigma_1</math>, also written as <math>\Sigma_1^0</math>, are those which satisfy propositions with one existential quantifier:

<math>\exists x_1 : </math> proposition holds

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

A formula is in the level <math>\Sigma_n^0</math> if it satisfies a proposition quantified first by <math>\exists</math>, and a total of n alternating existential (<math>\exists</math>) and universal (<math>\forall</math>) quantifiers.

Formulas are classified as <math>\Pi_n^0</math> in an equivalent fashion, except that the quantifiers commence with <math>\forall</math>.

Formulas are in the level <math>\Delta_n^0</math> if they are in both <math>\Sigma_n^0</math> and <math>\Pi_n^0</math>.

Suppose that there is an Oracle machine capable of calculating all the functions in a level <math>\Delta_n^0</math>. This machine is incapcable of solving its own halting problem (Turing's proof still applies). The halting problem for <math>\Delta_n^0</math> in fact sits in <math>\Delta_{n+1}^0</math>.