Hiérarchie arithmétique
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de  |
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
- formule
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 
. Ensuite, pour obtenir l'alternance pour-tout/il-existe, on remplace une suite de k quantificateurs identiques par un quantificateur sur un k-uple: 
devient 
. 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.
 |
Portail de la logique – Accédez aux articles de Wikipédia concernant la logique. |
