Arithmetical hierarchy

The arithmetical hierarchy classifies sets of natural numbers by the quantifier patterns needed to define them using computable predicates. Its levels measure increasing logical complexity, with alternating existential and universal quantifiers.

Computable function: A function whose values can be produced by an algorithm that halts on every input. Computable predicates provide the basic tests inside definitions at every level.
Σ⁰₁: The class of sets definable by an existential quantifier over a computable predicate. This is the first existential level above computable predicates.
Halting problem: The problem of deciding whether an arbitrary program eventually halts on a given input. Its set of halting instances is Σ⁰₁-complete.
Analytical hierarchy: A hierarchy classifying sets by formulas that may quantify over sets or functions as well as numbers. It extends arithmetical classification by allowing second-order quantification.
Predicate (mathematical logic): A statement with one or more free variables whose truth depends on their values. The hierarchy uses computable predicates as its quantifier-free starting point.
Prenex normal form: A logical formula with all quantifiers moved to the front, followed by a quantifier-free matrix. Prenex form makes the quantifier pattern used to assign a level explicit.
Rice's theorem: A theorem stating that every nontrivial semantic property of partial computable functions is undecidable. Many such properties are expressible at low levels of the hierarchy despite undecidability.
Polynomial hierarchy: A hierarchy of computational complexity classes defined through alternating polynomial-time quantifiers. It resembles quantifier alternation but measures resource-bounded decision complexity.
First-order logic: A formal system for reasoning about objects using predicates, variables, quantifiers, and logical connectives. Its existential and universal quantifiers form the patterns that distinguish hierarchy levels.
Turing jump: An operation that produces a set encoding which computations halt relative to a given oracle. Iterated jumps provide a degree-theoretic account of successive arithmetical levels.

Linked from 5 pages