The Arithmetic Hierarchy

The arithmetic hierarchy classifies sets and relations by the complexity of their definitions in the language of arithmetic. It stratifies undecidable problems by the number of quantifier alternations needed to define them.

Definition

Definition5.7Arithmetic Hierarchy

The classes $\Sigma^0_n$ and $\Pi^0_n$ of the arithmetic hierarchy are defined inductively:

$\Sigma^0_0 = \Pi^0_0 = \Delta^0_0$ : the decidable (computable) sets.
$\Sigma^0_{n+1}$ : sets of the form $\{x : \exists y \, R(x, y)\}$ where $R \in \Pi^0_n$ .
$\Pi^0_{n+1}$ : sets of the form $\{x : \forall y \, R(x, y)\}$ where $R \in \Sigma^0_n$ .
$\Delta^0_{n+1} = \Sigma^0_{n+1} \cap \Pi^0_{n+1}$ .

Definition5.8Complete Sets in the Hierarchy

A set $A$ is $\Sigma^0_n$ -complete if $A \in \Sigma^0_n$ and every $\Sigma^0_n$ set is many-one reducible to $A$ . The $n$ -th jump $\emptyset^{(n)}$ of the empty set is $\Sigma^0_n$ -complete. In particular, $\emptyset' = K$ is $\Sigma^0_1$ -complete.

Key Examples

ExampleClassification of Natural Problems

$\Sigma^0_1$ : $\{e : W_e \neq \emptyset\}$ (nonempty c.e. sets), the halting problem $K$
$\Pi^0_1$ : $\{e : W_e = \emptyset\}$ (empty c.e. sets), $\overline{K}$
$\Sigma^0_2$ : $\{e : W_e \text{ is infinite}\}$ , $\text{Fin} = \{e : W_e \text{ is finite}\}$ is $\Sigma^0_2$ -complete
$\Pi^0_2$ : $\text{Tot} = \{e : \varphi_e \text{ is total}\}$ , $\Pi^0_2$ -complete
$\Sigma^0_3$ : $\{e : W_e \text{ is cofinite}\}$ , $\Sigma^0_3$ -complete

RemarkPost's Theorem

Post's Theorem establishes the precise connection: $A \in \Sigma^0_{n+1}$ iff $A$ is c.e. relative to $\emptyset^{(n)}$ , and $A \in \Delta^0_{n+1}$ iff $A \leq_T \emptyset^{(n)}$ . This shows that each level of the hierarchy corresponds to computability relative to a specific oracle.

Analytical Hierarchy

Definition5.9Analytical Hierarchy

The analytical hierarchy extends beyond arithmetic by allowing quantification over functions (or sets of natural numbers). $\Sigma^1_1$ sets are projections of arithmetic sets; they include many natural objects from analysis. The hierarchy $\Sigma^1_n, \Pi^1_n$ continues upward and connects to descriptive set theory.

Example$\Sigma^1_1$ Sets

The set of codes for well-orderings of $\mathbb{N}$ is $\Pi^1_1$ -complete. The set of codes for computable ordinals (below $\omega_1^{CK}$ ) is $\Sigma^1_1$ but not $\Pi^1_1$ . The boundary between $\Sigma^1_1$ and $\Pi^1_1$ marks a fundamental divide in descriptive set theory.