The arithmetical hierarchy classifies sets by alternating blocks of number quantifiers over computable predicates.
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 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 isIt is -complete: a condition maps effectively to a program whose domain is .
If all indices of total computable functions could be enumerated as , thenwould be total and computable. Some would index , giving . Thus the totality problem is not computably enumerable.
Articles by others on the same topic
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.