Arithmetical Hierarchy - The Arithmetical Hierarchy of Formulas

The Arithmetical Hierarchy of Formulas

The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic. The classifications are denoted and 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 is logically equivalent to a formula with only bounded quantifiers then is assigned the classifications and .

The classifications and are defined inductively for every natural number n using the following rules:

• If is logically equivalent to a formula of the form, where is, then is assigned the classification .
• If is logically equivalent to a formula of the form, where is, then is assigned the classification .

Also, a formula is equivalent to a formula that begins with some existential quantifiers and alternates times between series of existential and universal quantifiers; while a 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 or it will be assigned the classifications and 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.