In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical.
The arithmetical hierarchy is important in recursion theory, effective descriptive set theory, and the study of formal theories such as Peano arithmetic.
The Tarski-Kuratowski algorithm provides an easy way to get an upper bound on the classifications assigned to a formula and the set it defines.
The hyperarithmetical hierarchy and the analytical hierarchy extend the arithmetical hierarchy to classify additional formulas and sets.
Read more about Arithmetical Hierarchy: The Arithmetical Hierarchy of Formulas, The Arithmetical Hierarchy of Sets of Natural Numbers, Relativized Arithmetical Hierarchies, Arithmetic Reducibility and Degrees, The Arithmetical Hierarchy of Subsets of Cantor and Baire Space, Extensions and Variations, Meaning of The Notation, Examples, Properties, Relation To Turing Machines
Famous quotes containing the word hierarchy:
“In the world of the celebrity, the hierarchy of publicity has replaced the hierarchy of descent and even of great wealth.”
—C. Wright Mills (1916–1962)