Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Hiérarchie arithmétique
Résumé
thumb|Illustration de la hiérarchie arithmétique.
En logique mathématique, plus particulièrement en théorie de la calculabilité, la hiérarchie arithmétique, définie par Stephen Cole Kleene, est une hiérarchie des sous-ensembles de l'ensemble N des entiers naturels définissables dans le langage du premier ordre de l'arithmétique de Peano. Un ensemble d'entiers est classé suivant les alternances de quantificateurs d'une formule sous forme prénexe qui permet de le définir.
Les premiers niveaux de la hiérarchie correspondent à la classe des ensembles récursivement énumérables (Σ10) et à celle des ensembles dont le complémentaire est récursivement énumérable (Π10), leur intersection étant la classe des ensembles récursifs (Δ10).
Pour définir la hiérarchie des sous-ensembles définissables de N, on peut utiliser une hiérarchie des formules (au sens du calcul des prédicats) de l'arithmétique. Il s'agit ici de formules du premier ordre, ce qu'indique l'exposant 0, quand on parle de formule Σn0 ou Πn0. De même, la hiérarchie analytique utilise des formules du second ordre, ce qui est dénoté par l'exposant 1. Dans la suite, on omettra l'exposant 0 car il n'y a pas de risque de confusion.
Au niveau 0, les classes des formules Σ0 et Π0 sont identiques. Ce sont les formules à quantificateurs bornés du langage de l'arithmétique de Peano, c'est-à-dire celles qui sont construites à partir des égalités polynomiales (addition et multiplication sont les seuls symboles de fonctions utilisés), avec les connecteurs usuels, et les quantificateurs universels et existentiels bornés ∃x≤t ... et ∀x≤t .... Par exemple, cette formule à deux variables libres x et z est Σ0 (ou Π0) :
(∃y≤z) 2z=(x+y)(x+y+1)+2y
est Σ0 (ou Π0).
On définit ensuite inductivement les classes des formules Σn et Πn, pour un entier naturel n non nul.
Si A est une formule Σ0 (ou Π0), ∃x A est une formule Σ1 et ∀x A une formule Π1 ;
Si S est une formule Σn, si P est une formule Πn, et si x est une variable quelconque (qui peut ou non apparaître libre dans S et P) alors :
∃x S reste Σn ;
∃x P est une formule Σn+1 ;
∀x S est une formule Πn+1 ;
∀x P reste Πn.
Source officielle
À propos de ce résultat
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.