Hiérarchie arithmétique

Un article de Freepedia.

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 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 rajoute autant de fausses variables que nécéssaire. Fin

On dit qu'une formule est <math>\Delta_n</math> si elle est à la fois <math>\Pi_n</math> et <math>\Sigma_n</math>; il n'y a pas de formule <math>\Delta_n</math> à strictement parler, sauf <math>\Delta_0</math>, qui 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.