Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Arithmetical hierarchy
open-in-new
<p>In <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a>, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians <a href="/facts/Stephen_Cole_Kleene/sKSax2se">Stephen Cole Kleene</a> and <a href="/facts/Andrzej_Mostowski/jIYwsCEC">Andrzej Mostowski</a>) classifies certain <a href="/facts/Set_(mathematics)/BfucfHMq">sets</a> based on the complexity of <a href="/facts/Formula_(logic)/YpTVlzuj">formulas</a> that <a href="/facts/Definable_set/scSn8jvA">define</a> them. Any set that receives a classification is called arithmetical. The arithmetical hierarchy was invented independently by Kleene (1943) and Mostowski (1946). </p><p>The arithmetical hierarchy is important in <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a>, <a href="/facts/Effective_descriptive_set_theory/YvexeYWC">effective descriptive set theory</a>, and the study of <a href="/facts/Theory_(logic)/mYe5gQpI">formal theories</a> such as <a href="/facts/Peano_arithmetic/DhhDnNug">Peano arithmetic</a>. </p><p>The <a href="/facts/Tarski%25E2%2580%2593Kuratowski_algorithm/6cbhHSjr">Tarski–Kuratowski algorithm</a> provides an easy way to get an upper bound on the classifications assigned to a formula and the set it defines. </p><p>The <a href="/facts/Hyperarithmetical_hierarchy/3tGU6KR1">hyperarithmetical hierarchy</a> and the <a href="/facts/Analytical_hierarchy/C9r61LzA">analytical hierarchy</a> extend the arithmetical hierarchy to classify additional formulas and sets. </p>