# arithmetical hierarchy

The arithmetical hierarchy is a hierarchy of either (depending on the context) formulas or relations. The relations of a particular level of the hierarchy are exactly the relations defined by the formulas of that level, so the two uses are essentially the same.

The first level consists of formulas with only bounded quantifiers, the corresponding relations are also called the Primitive Recursive relations (this definition is equivalent to the definition from computer science). This level is called any of $\Delta^{0}_{0}$, $\Sigma^{0}_{0}$ and $\Pi^{0}_{0}$, depending on context.

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