Editing Arithmetical hierarchy (section)

== The arithmetical hierarchy of formulas ==

The arithmetical hierarchy assigns classifications to the formulas in the language of [[Peano axioms#Peano arithmetic as first-order theory|first-order arithmetic]].  The classifications are denoted <math>\Sigma^0_n</math> and <math>\Pi^0_n</math> for [[natural number]]s ''n'' (including 0). The Greek letters here are [[lightface]] symbols, which indicates that the formulas do not contain {{Clarify|text=set parameters.|date=August 2024}}

If a formula <math>\phi</math> is [[logically equivalent]] to a formula having no unbounded quantifiers, i.e. in which all quantifiers are [[Bounded_quantifier#Bounded_quantifiers_in_arithmetic|bounded quantifiers]] then <math>\phi</math> is assigned the classifications <math>\Sigma^0_0</math> and <math>\Pi^0_0</math>.

The classifications <math>\Sigma^0_n</math> and <math>\Pi^0_n</math> are defined inductively for every natural number ''n'' using the following rules:
*If <math>\phi</math> is logically equivalent to a formula of the form <math>\exists m_1 \exists m_2\cdots \exists m_k \psi</math>, where <math>\psi</math> is <math>\Pi^0_n</math>, then <math>\phi</math> is assigned the classification <math>\Sigma^0_{n+1}</math>.
*If <math>\phi</math> is logically equivalent to a formula of the form <math>\forall m_1 \forall m_2\cdots \forall m_k  \psi</math>, where <math>\psi</math> is <math>\Sigma^0_n</math>, then <math>\phi</math> is assigned the classification <math>\Pi^0_{n+1}</math>.

A <math>\Sigma^0_n</math> formula is equivalent to a formula that begins with some [[existential quantifier]]s and alternates <math>n-1</math> times between series of existential and [[universal quantifier]]s; while a <math>\Pi^0_n</math> formula is equivalent to a formula that begins with some universal quantifiers and alternates analogously.

Because every first-order formula has a [[prenex normal form]], every formula is assigned at least one classification.  Because redundant quantifiers can be added to any formula, once a formula is assigned the classification <math>\Sigma^0_n</math> or <math>\Pi^0_n</math> it will be assigned the classifications <math>\Sigma^0_m</math> and <math>\Pi^0_m</math> for every ''m'' > ''n''.  The only relevant classification assigned to a formula is thus the one with the least ''n''; all the other classifications can be determined from it.