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
Σ⁰ₙ	—	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
Σ¹₁	—	Sigma-1-1	Function quantifier

Metatheory. Hierarchy is strict: Σ⁰ₙ ≠ Π⁰ₙ at every level. Mirrors the Turing-jump hierarchy (Post). Tarski's undefinability follows: arithmetical truth escapes every fixed level.

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

Limitations. Measures definitional, not computational, complexity. Counting alternations only; ignores feasibility. Analytical levels require impredicative resources.