Hiérarchie arithmétique

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

Classification des formules prénexes

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 Σ_n⁰ ou Π_n⁰. 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 Σ₀ et Π₀ 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 Σ₀ (ou Π₀) :

(∃y≤z) 2z=(x+y)(x+y+1)+2y

est Σ₀ (ou Π₀).

On définit ensuite inductivement les classes des formules Σ_n et Π_n, pour un entier naturel n non nul.

• Si A est une formule Σ₀ (ou Π₀), ∃x A est une formule Σ₁ et ∀x A une formule Π₁ ;
• 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.

Ainsi, 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 quantificateur existentiel pour les Σ_n, par un quantificateur 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 Σ₀ étant Π₀ (la classe est stable par négation), la négation d'une formule Σ_n est équivalente à une formule Π_n.

Classification des sous-ensembles définissables de N

Définition par les formules

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 N^p, 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, on montre que la classe des ensembles Σ₁ est exactement la classe des ensembles récursivement énumérables. Ainsi, Δ₁ 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

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 par 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 Δ₁ est une partie stricte de Σ₁ et donc de Π₁.

Propriétés de clôture

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

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

• Σ_n : ∃x₁ ∀x₂ ∃x₃ … Qx_n F
• Π_n : ∀x₁ ∃x₂ ∀x₃ … Qx_n F

où F est Σ₀.

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

Définition par projection et passage au complémentaire

Un ensemble Σ_n s'écrit A = { n∈N / ∃(a₁, …, a_k)∈N^k, P(n, a₁, …, a_k) } avec P une formule Π_n-1 à k+1 variables libres. On peut alors former l'ensemble B = { (n, a₁, …, a_k)∈N^k+1 / P(n, a₁, …, a_k) }, qui est Π_n-1 dans N^k+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 N^p 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 Σ₀ étant définie.

Il est cependant possible de prendre une autre classe de sous-ensembles de la réunion des N^p, 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 Σ₀ les formules sans quantificateurs (même bornés).

Réductibilité et hiérarchie arithmétique

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

Voir aussi

• Hiérarchie de Chomsky concernant les langages récursifs.
• Théorie descriptive des ensembles
• Hiérarchie de Borel
• Hiérarchie polynomiale
• Degré de Turing
• Saut de Turing

Sources

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