Arithmetical Hierarchy

Origin. Kleene, Mostowski (1940s). Classify sets of naturals by the number of alternating quantifiers over a recursive matrix. The analytical hierarchy extends this to second-order quantifiers.

Models. A set's complexity is measured by quantifier alternation. Σ⁰ₙ and Π⁰ₙ levels layer the definable sets above the recursive ones and align exactly with iterated Turing jumps.

Formalism.

Base levels: Δ⁰₁ = recursive. Σ⁰₁ = ∃y R(x, y), R recursive (= r.e.). Π⁰₁ = ∀y R(x, y) (co-r.e.).

Alternation: Σ⁰_{n+1} = ∃ȳ. (Π⁰ₙ matrix). Π⁰_{n+1} = ∀ȳ. (Σ⁰ₙ matrix). Δ⁰ₙ = Σ⁰ₙ ∩ Π⁰ₙ.

Post's theorem: Σ⁰_{n+1} = r.e. in 0⁽ⁿ⁾. Δ⁰_{n+1} = computable in 0⁽ⁿ⁾. Level n ↔ n-th Turing jump.

Completeness: Each level has ≤_m-complete sets. K is Σ⁰₁-complete. Fin = {e : W_e finite} is Σ⁰₂-complete. Tot = {e : φ_e total} is Π⁰₂-complete. Cof is Σ⁰₃-complete.

Analytical hierarchy: Σ¹₁ = ∃f (function quantifier), Π¹₁ dual. Δ¹₁ = hyperarithmetic. Second-order over ℕ.

Symbols.

Symbol	Unicode	Name	Meaning
∃	U+2203	Existential quantifier	Leads a Σ block
∀	U+2200	Universal quantifier	Leads a Π block
∩	U+2229	Intersection	Δ level is the meet of Σ and Π
≠	U+2260	Non-equality	Strictness of a level
ℕ	U+2115	Double-struck N / Naturals	Domain over which the hierarchy is taken
Σ⁰ₙ	—	Sigma-0-n	n existential-led alternations
Π⁰ₙ	—	Pi-0-n	n universal-led alternations
Δ⁰ₙ	—	Delta-0-n	Both Σ⁰ₙ and Π⁰ₙ
0⁽ⁿ⁾	—	n-th jump	Iterated halting
≤_m	—	Many-one reducibility	Reduction used for completeness at a level
W_e	—	e-th r.e. set	Domain of the e-th partial computable function
Σ¹₁	—	Sigma-1-1	Function quantifier
Δ¹₁	—	Delta-1-1	Hyperarithmetic sets

Metatheory. Kleene (1943) and Mostowski (1947) proved the hierarchy theorem independently: for every n ≥ 1 the inclusions Δ⁰ₙ ⊊ Σ⁰ₙ and Δ⁰ₙ ⊊ Π⁰ₙ are proper and Σ⁰ₙ ≠ Π⁰ₙ, so no level collapses; the separating sets come from diagonalizing the universal Σ⁰ₙ predicate that Kleene's normal form theorem supplies. Post's theorem identifies the levels with iterated jumps: A is Σ⁰_{n+1} iff A is r.e. in ∅⁽ⁿ⁾, A is Δ⁰_{n+1} iff A ≤_T ∅⁽ⁿ⁾, and ∅⁽ⁿ⁾ is Σ⁰ₙ-complete under many-one reduction for n ≥ 1, so strictness of the hierarchy is exactly strictness of the jump. Every level carries ≤_m-complete sets: K at Σ⁰₁, Fin at Σ⁰₂, Tot at Π⁰₂, Cof at Σ⁰₃. Tarski's undefinability theorem says the union is not itself arithmetical — Th(ℕ) sits at no level, and ∅⁽ω⁾ ≡_T Th(ℕ). One level up, Kleene proved Δ¹₁ is exactly the hyperarithmetic sets, and the index set of computable well-orderings is Π¹₁-complete.

Applies to. Classifying undecidable problems. Definability theory. Reverse mathematics. Effective descriptive set theory.

Limitations. The hierarchy classifies definitions, not computations. Every decidable set is Δ⁰₁ however expensive the decision procedure, so complexity is invisible here and the polynomial hierarchy is a separate construction that merely resembles this one in shape. Within a level the classification is coarse: Σ⁰₁ contains the Turing-incomparable c.e. sets of Friedberg and Muchnik and every degree Sacks density inserts, so a level bounds Turing degree from above and fixes nothing else, and two Δ⁰₂ sets can be incomparable. Post's theorem supplies a complete set at each level but no structure theory inside one. The hierarchy also stops early: it captures exactly the arithmetically definable sets, and Th(ℕ) already escapes, so reaching the hyperarithmetic sets needs transfinite iteration of the jump and the analytical levels need quantification over all of Baire space, which is impredicative.