Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Arithmetical hierarchy
Summary
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical. The arithmetical hierarchy was invented independently by Kleene (1943) and Mostowski (1946).
The arithmetical hierarchy is important in computability 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 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 .
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 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 or it will be assigned the classifications and for every m > n.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.