Arithmetical hierarchy (source code)

= Arithmetical hierarchy
{wiki}

The <arithmetical hierarchy> measures how many alternating blocks of unbounded <quantifiers> over <natural numbers> are needed to define a <set> of <natural numbers>. In its lightface version, $A\in\Sigma^0_n$ when membership has the form
$$
x\in A\ \Longleftrightarrow\ \exists y_1\forall y_2\exists y_3\cdots Q_ny_n\ R(x,y_1,\ldots,y_n),
$$
with a <computable predicate> $R$ and $n$ alternating blocks; a block can code a finite tuple. The class $\Pi^0_n$ starts with a universal block, and $\Delta^0_n=\Sigma^0_n\cap\Pi^0_n$. At level zero the matrix is <computable>; these definitions allow natural-number parameters, rather than arbitrary sets as oracle parameters.

The <halting set> is $\Sigma^0_1$: membership says that some finite computation halts. Its <complement> is $\Pi^0_1$. The index set of <total computable functions> is $\Pi^0_2$, since totality says $\forall x\exists s$ that the computation on input $x$ halts within $s$ steps. Alternation therefore records a concrete difference between witnessing one successful finite search and certifying that every input eventually succeeds.