La hiérarchie arithmétique
La hiérarchie arithmétique classifie les ensembles de nombres naturels en fonction du nombre de quantificateurs alternés nécessaires pour les définir, établissant un lien entre la complexité logique et les degrés d'incalculabilité.
Definition
La hiérarchie arithmétique stratifie les ensembles définissables en arithmétique du premier ordre en comptant les alternances de quantificateurs non bornés devant une matrice calculable, les ensembles sigma-n étant définis par un bloc commençant par un quantificateur existentiel et les ensembles pi-n par un bloc commençant par un quantificateur universel.
Scope
Ce sujet aborde la classification des ensembles définissables en niveaux sigma, pi et delta par alternance de quantificateurs sur des relations calculables, le théorème de Post reliant la hiérarchie au problème de l'arrêt itéré et aux sauts de Turing, la stricte hiérarchie, et son extension à la hiérarchie analytique.
Core questions
- Comment l'alternance de quantificateurs mesure-t-elle la complexité d'un ensemble ?
- Comment les classes sigma, pi et delta de chaque niveau sont-elles liées les unes aux autres ?
- Comment la hiérarchie correspond-elle à l'itération du problème de l'arrêt ?
- Pourquoi la hiérarchie est-elle stricte, chaque niveau étant proprement plus grand que le précédent ?
Key theories
- Classification par quantificateurs
- Un ensemble est sigma-n s'il est définissable par n blocs de quantificateurs alternés commençant existentiellement sur une relation calculable, et pi-n s'il commence universellement ; les ensembles énumérables calculablement sont exactement les ensembles sigma-un.
- Théorème de Post
- Un ensemble est sigma-(n+1) précisément lorsqu'il est énumérable calculablement relativement au n-ième saut de Turing, liant les niveaux de la hiérarchie aux problèmes de l'arrêt relativisés itérés.
- Stricte hiérarchie
- Chaque saut de Turing est strictement plus complexe que le précédent, de sorte que chaque niveau de la hiérarchie arithmétique contient proprement les niveaux inférieurs et la hiérarchie ne s'effondre pas.
Clinical relevance
La hiérarchie arithmétique constitue l'étalon de mesure standard de la complexité des problèmes définissables en logique et en informatique : elle situe des problèmes tels que la totalité, la finitude et la co-finitude des ensembles calculables à des niveaux précis, et elle délimite la frontière entre ce qui est énumérable calculablement et ce qui nécessite des ressources non calculables plus puissantes.
History
Kleene et Mostowski ont introduit indépendamment la hiérarchie arithmétique vers 1943, classifiant les ensembles par complexité de quantificateurs sur des prédicats calculables. Le théorème de Post a relié la hiérarchie au saut de Turing, unifiant les perspectives basées sur la définissabilité et sur la calculabilité, et le cadre a ensuite été étendu vers le haut dans la hiérarchie analytique.
Key figures
- Stephen Cole Kleene
- Andrzej Mostowski
- Emil Post
Related topics
Seminal works
- rogers1987
- soare1987
- cutland1980
Frequently asked questions
- Que signifie un niveau plus élevé dans la hiérarchie ?
- Un plus grand nombre de quantificateurs alternés implique une définition plus complexe et, selon le théorème de Post, un problème qui nécessite davantage d'itérations du problème de l'arrêt pour être décidé. Les ensembles situés plus haut dans la hiérarchie sont strictement moins accessibles au calcul que ceux qui leur sont inférieurs.
- Où se situent les ensembles énumérables calculablement ?
- Ils occupent le niveau sigma-un, définissables par un unique quantificateur existentiel sur une relation calculable. Leurs compléments occupent le niveau pi-un, et les ensembles qui sont les deux, les ensembles delta-un, sont exactement les ensembles calculables.