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 form
with 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.
A bounded quantifier has the form or , where the term does not contain . It ranges over a finite initial segment in the standard natural numbers.
An arithmetic bounded formula uses only quantifiers bounded by arithmetic terms, such as and , with the bound not containing the quantified variable. Existential bounded representation of a primitive recursive function places all unrestricted existential variables in a single outer block.
A bounded arithmetic sentence is an arithmetic bounded formula with no free variables. Every quantifier is restricted by an arithmetic first-order term. In the standard natural numbers such a first-order sentence has a definite truth value determined by finite bounded searches.
A formula is an arithmetical formula in which every quantifier is bounded.
A formula is equivalent to with bounded. A formula is equivalent to with bounded.
If a total single-valued numerical function has a Sigma-1 graph, the complement of that graph is also Sigma-1. An input-output pair is outside the graph exactly when some different output is in the graph. Totality and uniqueness are essential to that equivalence. Stage-comparison separation of enumerations of the graph and its complement then gives weak definability of a numerical function in a bounded-complete arithmetic first-order theory.
An arithmetic theory is Sigma-1 complete when it proves every true Sigma-1 formula that is a sentence. A genuine finite proof gives a true existential assertion that a code is a proof; Sigma-1 completeness therefore supplies the external necessitation clause for the usual arithmetical provability predicate. Its formalized version says that, for each Sigma-1 sentence , . Applying this to a provability assertion, which is itself Sigma-1, gives the third of the Hilbert-Bernays-Löb derivability conditions.
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.
A set is in exactly when it is the domain of a partial computable function. Equivalently, there is a computable predicate such that
A set is in when membership can be written with one universal block followed by one existential block over a computable predicate. Equivalently, in the word-function formulation, there is a partial computable such that
For an effective enumeration of computably enumerable languages , the totality problem is
It is -complete: a condition maps effectively to a program whose domain is .
If all indices of total computable functions could be enumerated as , then
would be total and computable. Some would index , giving . Thus the totality problem is not computably enumerable.

Articles by others on the same topic (1)

The Arithmetical Hierarchy is a classification of decision problems (or sets of natural numbers) based on the complexity of their definitions in terms of logical formulas. It arises from the study of computability and formal logic, particularly in relation to first-order arithmetic. The hierarchy is built on the idea of quantifier alternation in logical statements.