Editing Arithmetical hierarchy (section)

{{No footnotes|date=June 2021}}
{{short description|Hierarchy of complexity classes for formulas defining sets}}
[[File:Arithmetic hierarchy.svg|thumb|513x513px|An illustration of how the levels of the hierarchy interact and where some basic set categories lie within it.]]
In [[mathematical logic]], the '''arithmetical hierarchy''', '''arithmetic hierarchy''' or '''Kleene–Mostowski hierarchy''' (after mathematicians [[Stephen Cole Kleene]] and [[Andrzej Mostowski]]) classifies certain [[Set (mathematics)|sets]] based on the complexity of [[formula (logic)|formula]]s that [[definable set|define]] them.  Any set that receives a classification is called '''arithmetical'''.  The arithmetical hierarchy was invented independently by Kleene (1943) and Mostowski (1946).<ref>P. G. Hinman, ''Recursion-Theoretic Hierarchies'' (p.89), Perspectives in Logic, 1978. Springer-Verlag Berlin Heidelberg, ISBN 3-540-07904-1.</ref>

The arithmetical hierarchy is important in [[computability theory]], [[effective descriptive set theory]], and the study of [[theory (logic)|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.