Arithmetical hierarchy

The arithmetical hierarchy classifies sets by alternating blocks of number quantifiers over computable predicates.

A bounded quantifier has the form $\exists x<t\phi$ or $\forall x<t\phi$, where the term $t$ does not contain $x$. It ranges over a finite initial segment in the standard natural numbers.

An arithmetic bounded formula uses only quantifiers bounded by arithmetic terms, such as $\exists u<t$ and $\forall u<t$, with the bound not containing the quantified variable. Existential bounded representation of a primitive recursive function places all unrestricted existential variables in a single outer block.

A bounded arithmetic sentence is an arithmetic bounded formula with no free variables. Every quantifier is restricted by an arithmetic first-order term. In the standard natural numbers such a first-order sentence has a definite truth value determined by finite bounded searches.

A ${\Delta }_0$ formula is an arithmetical formula in which every quantifier is bounded.

A ${\Sigma }_1$ formula is equivalent to $\exists \mathbf{y}\delta$ with $\delta$ bounded. A ${\Pi }_1$ formula is equivalent to $\forall \mathbf{y}\delta$ with $\delta$ bounded.

If a total single-valued numerical function has a Sigma-1 graph, the complement of that graph is also Sigma-1. An input-output pair is outside the graph exactly when some different output is in the graph. Totality and uniqueness are essential to that equivalence. Stage-comparison separation of enumerations of the graph and its complement then gives weak definability of a numerical function in a bounded-complete arithmetic first-order theory.

An arithmetic theory is Sigma-1 complete when it proves every true Sigma-1 formula that is a sentence. A genuine finite proof gives a true existential assertion that a code is a proof; Sigma-1 completeness therefore supplies the external necessitation clause for the usual arithmetical provability predicate. Its formalized version says that, for each Sigma-1 sentence $\sigma$, $T⊢\sigma \to {\mathrm{Pr}}_T(┌\sigma ┐)$. Applying this to a provability assertion, which is itself Sigma-1, gives the third of the Hilbert-Bernays-Löb derivability conditions.

A set $A$ is in ${\Sigma }_1$ exactly when it is the domain of a partial computable function. Equivalently, there is a computable predicate $R$ such that

A set is in ${\Pi }_2$ when membership can be written with one universal block followed by one existential block over a computable predicate. Equivalently, in the word-function formulation, there is a partial computable $f$ such that

For an effective enumeration of computably enumerable languages $W_v$, the totality problem isIt is ${\Pi }_2$-complete: a ${\Pi }_2$ condition $w\in P⟺\forall xf(w,x)\downarrow$ maps effectively to a program whose domain is $\{x:f(w,x)\downarrow \}$.

If all indices of total computable functions could be enumerated as $e_0,e_1,\dots$, thenwould be total and computable. Some $e_k$ would index $g$, giving $g(k)=g(k)+1$. Thus the totality problem is not computably enumerable.