Arithmetical hierarchy Created 2026-09-24 Updated 2026-11-05
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, when membership has the formwith a computable predicate and alternating blocks; a block can code a finite tuple. The class starts with a universal block, and . At level zero the matrix is computable; these definitions allow natural-number parameters, rather than arbitrary sets as oracle parameters.
The halting set is : membership says that some finite computation halts. Its complement is . The index set of total computable functions is , since totality says that the computation on input halts within steps. Alternation therefore records a concrete difference between witnessing one successful finite search and certifying that every input eventually succeeds.
Pi-1 formula Created 2026-09-24 Updated 2026-11-05
A Pi-1 formula in the arithmetical hierarchy has the form , with a decidable predicate; several universal number quantifiers can be combined by coding tuples. In a formal arithmetic presentation, the matrix is taken to have bounded quantifiers, with equivalent computable-predicate normal forms obtained by coding computations.
For example, the assertion that a fixed Turing machine never halts is , where checks that it has not halted in its first steps. A false such assertion has a finite counterexample, while a true one need not have a finite computational certificate. Negating a Pi-1 formula gives a Sigma-1 formula.