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.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
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.
En logique mathématique, l'arithmétique du second ordre est une théorie des entiers naturels et des ensembles d'entiers naturels. Elle a été introduite par David Hilbert et Paul Bernays dans leur livre Grundlagen der Mathematik. L'axiomatisation usuelle de l'arithmétique du second ordre est notée Z2. L'arithmétique de second ordre a pour conséquence les théorèmes de l'arithmétique de Peano (du premier ordre), mais elle est à la fois plus forte et plus expressive que celle-ci.
La théorie descriptive des ensembles est une branche des mathématiques s'intéressant aux ensembles « définissables ». Son principal but est de classifier ces ensembles par complexité. Elle a de nombreux liens avec la théorie des ensembles et a des applications dans de nombreux domaines. Historiquement, les premières questions de la théorie descriptive des ensembles sont apparues à la suite de la découverte d'une erreur par Mikhaïl Souslin en dans une démonstration de Lebesgue.