Arithmetical hierarchy

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. 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. The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic. The classifications are denoted Σ n 0 {displaystyle Sigma _{n}^{0}} and Π n 0 {displaystyle Pi _{n}^{0}} for natural numbers n (including 0). The Greek letters here are lightface symbols, which indicates that the formulas do not contain set parameters. If a formula ϕ {displaystyle phi } is logically equivalent to a formula with only bounded quantifiers then ϕ {displaystyle phi } is assigned the classifications Σ 0 0 {displaystyle Sigma _{0}^{0}} and Π 0 0 {displaystyle Pi _{0}^{0}} . The classifications Σ n 0 {displaystyle Sigma _{n}^{0}} and Π n 0 {displaystyle Pi _{n}^{0}} are defined inductively for every natural number n using the following rules: Also, a Σ n 0 {displaystyle Sigma _{n}^{0}} formula is equivalent to a formula that begins with some existential quantifiers and alternates n − 1 {displaystyle n-1} times between series of existential and universal quantifiers; while a Π n 0 {displaystyle Pi _{n}^{0}} formula is equivalent to a formula that begins with some universal quantifiers and alternates similarly. Because every formula is equivalent to a formula in prenex normal form, every formula with no set quantifiers is assigned at least one classification. Because redundant quantifiers can be added to any formula, once a formula is assigned the classification Σ n 0 {displaystyle Sigma _{n}^{0}} or Π n 0 {displaystyle Pi _{n}^{0}} it will be assigned the classifications Σ m 0 {displaystyle Sigma _{m}^{0}} and Π m 0 {displaystyle Pi _{m}^{0}} for every m greater than n. The most important classification assigned to a formula is thus the one with the least n, because this is enough to determine all the other classifications.