En calculabilité, on considère les formules logiques (du premier ordre) de la forme
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 (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une...) 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection...) des formules sans quantificateurs.
On classifie ainsi toutes les formules comme Πn ou Σn, ce qui donne une manière de mesurer leur complexité (La complexité est une notion utilisée en philosophie, épistémologie (par...), 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 (Ce théorème fait le lien entre hiérarchie arithmétique et degré de Turing.) fait plus précisément le lien entre hiérarchie arithmétique (En calculabilité, on considère les formules logiques (du premier ordre) de la forme) et degré (Le mot degré a plusieurs significations, il est notamment employé dans les domaines...) de Turing.