# arithmetical hierarchy

A formula $\phi$ is $\Sigma^{0}_{n}$ if there is some $\Delta^{0}_{0}$ formula $\psi$ such that $\phi$ can be written:

 $\phi(\vec{k})=\exists x_{1}\forall x_{2}\cdots{Q}x_{n}\psi(\vec{k},\vec{x})$
 $\text{ where }Q\text{ is either }\forall\text{ or }\exists\text{, whichever % maintains the pattern of alternating quantifiers}$

The $\Sigma^{0}_{1}$ relations are the same as the Recursively Enumerable relations.

Similarly, $\phi$ is a $\Pi^{0}_{n}$ relation if there is some $\Delta^{0}_{0}$ formula $\psi$ such that:

 $\phi(\vec{k})=\forall x_{1}\exists x_{2}\cdots Qx_{n}\psi(\vec{k},\vec{x})$
 $\text{ where }Q\text{ is either }\forall\text{ or }\exists\text{, whichever % maintains the pattern of alternating quantifiers}$

A formula is $\Delta^{0}_{n}$ if it is both $\Sigma^{0}_{n}$ and $\Pi^{0}_{n}$. Since each $\Sigma^{0}_{n}$ formula is just the negation  of a $\Pi^{0}_{n}$ formula and vice-versa, the $\Sigma^{0}_{n}$ relations are the complements  of the $\Pi^{0}_{n}$ relations.

The relations in $\Delta^{0}_{1}=\Sigma^{0}_{1}\cap\Pi^{0}_{1}$ are the Recursive relations.

Higher levels on the hierarchy correspond to broader and broader classes of relations. A formula or relation which is $\Sigma^{0}_{n}$ (or, equivalently, $\Pi^{0}_{n}$) for some integer $n$ is called arithmetical.

The superscript $0$ is often omitted when it is not necessary to distinguish from the analytic hierarchy.

Functions can be described as being in one of the levels of the hierarchy if the graph of the function is in that level.

 Title arithmetical hierarchy Canonical name ArithmeticalHierarchy Date of creation 2013-03-22 12:55:11 Last modified on 2013-03-22 12:55:11 Owner CWoo (3771) Last modified by CWoo (3771) Numerical id 19 Author CWoo (3771) Entry type Definition Classification msc 03B10 Synonym arithmetic hierarchy Synonym arithmetic Synonym arithmetical Synonym arithmetic formula Synonym arithmetical formulas Related topic AnalyticHierarchy Defines sigma n Defines sigma-n Defines pi n Defines pi-n Defines delta n Defines delta-n Defines recursive Defines recursively enumerable Defines delta-0 Defines delta 0 Defines delta-1 Defines delta 1 Defines arithmetical