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
Analytical hierarchy
Summary
In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers over both the set of natural numbers, , and over functions from to . The analytical hierarchy of sets classifies sets by the formulas that can be used to define them; it is the lightface version of the projective hierarchy.
The notation
indicates the class of formulas in the language of second-order arithmetic with number quantifiers but no set quantifiers. This language does not contain set parameters. The Greek letters here are lightface symbols, which indicate this choice of language. Each corresponding boldface symbol denotes the corresponding class of formulas in the extended language with a parameter for each real; see projective hierarchy for details.
A formula in the language of second-order arithmetic is defined to be if it is logically equivalent to a formula of the form where is . A formula is defined to be if it is logically equivalent to a formula of the form where is . This inductive definition defines the classes and for every natural number .
Kuratowski and Tarski showed in 1931 that every formula in the language of second-order arithmetic has a prenex normal form, and therefore or for some . Because meaningless quantifiers can be added to any formula, once a formula is given the classification or for some it will be given the classifications and for all greater than .
A set of natural numbers is assigned the classification if it is definable by a formula. The set is assigned the classification if it is definable by a formula. If the set is both and then it is given the additional classification .
The sets are called hyperarithmetical. An alternate classification of these sets by way of iterated computable functionals is provided by the hyperarithmetical theory.
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.