Hiérarchie arithmétique
Un article de Wikivisual, l'encyclopédie libre.
| Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
En calculabilité, on considère les formules logiques (du premier ordre) de la forme
- formule <math>\Pi_n : \forall a_1 \exists a_2 \cdots \phi(a_1\cdots a_n)</math>
- formule <math>\Sigma_n : \exists a_1 \forall a_2 \cdots \phi(a_1\cdots a_n)</math>
où <math>\phi</math> 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 <math>\Pi_n</math> ou <math>\Sigma_n</math>, à 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 <math>\neg \forall x \equiv \exists x \neg</math>. Ensuite, pour obtenir l'alternance pour-tout/il-existe, on remplace une suite de <math>k</math> quantificateurs identiques par un quantificateur sur un <math>k</math>-uple: <math>\forall x \forall y \forall z</math> devient <math>\forall (x,y,z)</math>. Fin
Par extension, on dira d'une formule qu'elle est <math>\Pi_n</math> (respectivement <math>\Sigma_n</math>) si elle est équivalente à une formule <math>\Pi_n</math> (respectivement <math>\Sigma_n</math>), même si elle n'est pas elle-même sous forme prénexe.
On dit qu'une formule est <math>\Delta_n</math> si elle est à la fois <math>\Pi_n</math> et <math>\Sigma_n</math>; Ainsi <math>\Delta_0</math> désigne l'ensemble des formules sans quantificateurs.
On classifie ainsi toutes les formules comme <math>\Pi_n</math> ou <math>\Sigma_n</math>, ce qui donne une manière de mesurer leur complexité, c'est-à-dire les moyens à employer pour les calculer. En particulier, les formules <math>\Sigma_1</math> 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.
| Image:BandeauPortailLogiqueSmall.png | Portail de la logique – Accédez aux articles de Wikipédia concernant la logique. |
