Hiérarchie arithmétique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Illustration de la Hiérarchie Arithmétique[1]

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érables10) et à celle des ensembles dont le complémentaire est récursivement énumérable (Π10), leur intersection étant la classe des ensembles récursifs10).

Classification des formules prénexes[modifier | modifier le code]

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 (en) utilise des formules du second ordre, ce qui est dénoté par l'exposant 1. Il arrive que l'on omette l'exposant, s'il n'y a pas risque de confusion, et c'est ce que l'on fera dans la suite.

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 ∃xt ... et ∀xt .... 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.

On observe donc qu'une formule Σn ou Πn est une formule à quantificateurs bornés précédée d'un préfixe de n alternances de quantificateurs commençant par un existentiel pour les Σn, par un universel pour les Πn.

La notion que l'on a définie est pour le moment purement syntaxique. On n'a pas classé toutes les formules du langage, mais toute formule étant équivalente à une forme prénexe, est équivalente à une formule de la hiérarchie, dont la matrice ne contient d'ailleurs même pas de quantifications bornées. On peut remarquer également que la négation d'une formule Σ0 étant Π0 (la classe est stable par négation), la négation d'une formule Σn est évidemment équivalente à une formule Πn.

Classification des sous-ensembles définissables de N[modifier | modifier le code]

Définition par les formules[modifier | modifier le code]

Un sous-ensemble de N est dit Σn, respectivement Πn, s'il peut être défini par une formule à une variable libre Σn, respectivement Πn, et il est dit Δn s'il est à la fois Σn et Πn. On déduit directement de la définition des formules Σn et Πn qu'un ensemble est Πn si et seulement si son complémentaire est Σn, et donc les ensembles Δn sont aussi les ensembles Σn dont le complémentaire est aussi Σn.

Il peut être commode d'étendre la notion aux uples d'entiers naturels : un sous-ensemble de Np, où p est un entier naturel non nul, est Σn, respectivement Πn, s'il est défini par une formule Σn, respectivement Πn, à p variables libres.

De façon équivalente on parle aussi de prédicat ou de relation sur N Σn ou Πn.

On classe ainsi tous les sous-ensembles définissables au premier ordre de N comme Σn ou Πn, c'est ce que l'on appelle la hiérarchie arithmétique. Classer un ensemble dans la hiérarchie permet d'une certaine façon de mesurer le « degré de calculabilité » de l'ensemble grâce à la complexité logique d'une formule qui le définit. Plus un ensemble est haut dans la hiérarchie, « moins » il est calculable.

En effet, en suivant les méthodes employées par Gödel pour démontrer son premier théorème d'incomplétude[2] on montre que la classe des ensembles Σ1 est exactement la classe des ensembles récursivement énumérables. Ainsi, Δ1 désigne la classe des ensembles récursivement énumérables et de complémentaire récursivement énumérable, donc la classe des ensembles récursifs.

Le treillis de l'inclusion sur la hiérarchie arithmétique[modifier | modifier le code]

Si l'on ajoute un quantificateur « inutile » (c'est-à-dire portant sur une variable qui n'apparait pas dans la formule), en tête ou en queue du préfixe de quantificateurs d'une formule Σn ou Πn, on obtient une formule trivialement équivalente. Il est donc immédiat que :

Σn ∪ Πn   ⊂   Σn+1 ∩ Πn+1 = Δn+1 .

Par ailleurs on a, évidemment par définition des Δn :

Δn ⊂ Σn    et    Δn ⊂ Πn.

Le treillis de l'inclusion sur la hiérarchie arithmétique est entièrement décrit pas ces relations d'inclusion, en particulier ces inclusions sont des inclusions strictes, ce qui résulte essentiellement de l'indécidabilité du problème de l'arrêt, qui dit directement que Δ1 est une partie stricte de Σ1 et donc de Π1.

Propriétés de clôture[modifier | modifier le code]

Chaque classe Σn, Πn ou Δn est stable par intersection et réunion, on le déduit en construisant dans l'ordre adéquat la forme prénexe de la conjonction ou de la disjonction de deux formules Σn ou Πn. elles sont également stables par produit cartésien. La classe des ensembles Δn est stable par passage au complémentaire et donc par toutes les opérations booléennes.

Contraction des quantificateurs de même nature[modifier | modifier le code]

On peut montrer que tout ensemble de la hiérarchie peut toujours de définir au même niveau par une formule ou chaque alternance est réduite à un seul quantificateur et où la matrice est une formule Σ0 :

  • Σn : ∃x1x2x3 ... F
  • Πn : ∀x1x2x3 ... F

F est Σ0.

On peut utiliser pour ceci le codage des couples de Cantor, qui se manipule par des formules Σ0.

Définition par projection et passage au complémentaire[modifier | modifier le code]

Un ensemble Σn s'écrit A = { nN / ∃(a1,...,ak)∈Nk, P(n,a1,...,ak) } avec P une formule Πn-1 à k+1 variables libres. On peut alors former l'ensemble B = { (n,a1,...,ak)∈Nk+1 / P(n,a1,...,ak) }, qui est Πn-1 dans Nk+1, et constater que A est le projeté de B selon la première coordonnée.

Une quantification existentielle correspond ainsi à une projection. On peut en déduire une autre définition de la hiérarchie arithmétique qui ne fait pas appel directement aux formules. En effet, la classe Σn étant définie (pour des sous-ensembles de Np p > 0) :

  • La classe des ensembles Πn est la classe des ensembles dont le complémentaire est Σn ;
  • La classe des ensembles Σn+1 est la classe des projetés des ensembles Πn.

Ceci définit la hiérarchie, la classe des ensembles Σ0 étant définie.

Il est cependant possible de prendre une autre classe de sous-ensembles de la réunion des Np, p > 0, comme point de départ, en conservant la même hiérarchie à partir du rang 1. Par exemple on peut partir :

  • de la classe des ensembles primitifs récursifs (les projetés d'ensembles primitifs récursifs sont bien les ensembles récursivement énumérables, d'après le théorème de forme normale de Kleene) ;
  • Les ensembles définis par des équations polynomiales sans paramètres (les projetés de ces ensembles sont alors les ensembles diophantiens, donc les ensembles récursivement énumérables selon le théorème de Matiiassevitch).

Dans le second cas, cela revient, pour la définition par les formules, à prendre à la place des formules Σ0 les formules sans quantificateurs (même bornés).

Ensembles universels[modifier | modifier le code]

Réductibilité et hiérarchie arithmétique[modifier | modifier le code]

Le théorème de Post fait plus précisément le lien entre hiérarchie arithmétique et degré de Turing.

Notes[modifier | modifier le code]

  1. D. Kozen Theory of Computation Springer 2006
  2. essentiellement en utilisant la fonction β, voir l'article

Voir aussi[modifier | modifier le code]

Sources[modifier | modifier le code]

  • P. Odifreddi, 1989. Classical Recursion Theory, North-Holland. (ISBN 0-44487-295-7)