Hiérarchie arithmétique

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

En calculabilité, on considère les formules logiques (du premier ordre) de la forme

formule $\Pi_n : \forall a_1 \exists a_2 \cdots \phi(a_1\cdots a_n)$

formule $\Sigma_n : \exists a_1 \forall a_2 \cdots \phi(a_1\cdots a_n)$

où $φ$ ne contient pas de quantificateurs.

Ce genre de formules, dites prénexes, n'est pas un cas isolé, comme le prouve le théorème suivant :

Théorème : toute formule est équivalente à une formule $Π n$ ou $Σ n$ , à moins qu'elle n'ait aucun quantificateur.

Preuve. On commence par placer tous les quantificateurs en tête de formule, grâce aux propriétés du type $\neg \forall x \equiv \exists x \neg$ . Ensuite, pour obtenir l'alternance pour-tout/il-existe, on remplace une suite de $k$ quantificateurs identiques par un quantificateur sur un $k$ -uple: $\forall x \forall y \forall z$ devient $\forall (x,y,z)$ . Fin

Par extension, on dira d'une formule qu'elle est $Π n$ (respectivement $Σ n$ ) si elle est équivalente à une formule $Π n$ (respectivement $Σ n$ ), même si elle n'est pas elle-même sous forme prénexe.

On dit qu'une formule est $Δ n$ si elle est à la fois $Π n$ et $Σ n$ ; Ainsi $Δ 0$ désigne l'ensemble des formules sans quantificateurs.

On classifie ainsi toutes les formules comme $Π n$ ou $Σ n$ , ce qui donne une manière de mesurer leur complexité, c'est-à-dire les moyens à employer pour les calculer. En particulier, les formules $Σ 1$ expriment les ensembles récursivement énumérables.

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