Arithmetical hierarchy (nonfiction)

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.

Nonfiction cross-reference

• Mathematics (nonfiction)
• Set theory (nonfiction)

External links:

• Arithmetical hierarchy @ Wikipedia