arithmetical hierarchy

The arithmetical hierarchy is a scheme that classifies sets of natural numbers and the formulae that define them based on complexity.

Formulae are classed as and according to the following scheme. Let be a statement in the language of first-order arithmetic. Then is:

• both and iff has no unbounded quantifiers;
• iff , where is ;
• iff , where is .

Furthermore, we declare these classes to be invariant under logical equivalence. Since every first-order formula has a logically-equivalent prenex normal form, it follows that this scheme classifies every formula.

These classes are extended to sets in the obvious way: if (where is a formula with a single free variable), then is iff is and iff is . Additionally, is iff it is both and .

These classes are sometimes written with a superscript ; i.e., , , and . The superscript represents the largest “type” of object being quantified over. Type objects are numbers , type objects are functions —or objects that can be encoded as such, e.g., real numbers—and so on. For example, assuming the classical - definition of the limit, the statement is , while the statement that exists is (with some restrictions on the definition of ). The arithmetical hierarchy refers specifically to statements about/sets of natural numbers, hence statements/sets in , , and .

The arithmetical hierarchy has some relation to decidability. / properties are decidable, while properties are semidecidable. In fact, is exactly the set of formulae describing semidecidable properties. On the other hand, is exactly the set of formulae whose negations are semidecidable.