Une stratification des prédicats et formules portant sur les entiers naturels selon le motif et le nombre d'alternances de quantificateurs du premier ordre ; les classes notées Σ_n, Π_n et Δ_n classent la définissabilité et la décidabilité en arithmétique du premier ordre.

Principe

Mesurer la complexité d'une formule par son quantificateur initial et le nombre d'alternances existentielles/universelles ; cette mesure syntaxique corrèle avec des propriétés de calculabilité et de réductions entre ensembles de nombres naturels.

Démonstration

Une formule de la forme ∃x∀y R(x,y) (avec R décidable) appartient à Σ_2 ; la classe Σ_1 correspond aux formules existentielles dont les extensions sont exactement les ensembles récursivement énumérables, tandis que Π_1 donne les descriptions universelles (co-énumérables).

Mauvaise application

Considérer la hiérarchie arithmétique comme une mesure de complexité temporelle ou spatiale pratique, ou la confondre avec des hiérarchies de complexité sur structures finies, est une erreur de catégorie sur ce que la hiérarchie formalise.

Conséquence

Une application correcte permet d'énoncer précisément la décidabilité, l'existence de problèmes complets pour des niveaux donnés (Σ_n ou Π_n), et les types de réductions ou d'accès à des oracles nécessaires pour décider des prédicats.

Inversion

Inverser le motif du quantificateur dominant permet de passer entre classes duales (Σ_n ↔ Π_n) ; cela échange la complexité existentielle et universelle et change souvent le caractère de décidabilité (r.e. ↔ co-r.e.).

Limite

S'applique à l'arithmétique du premier ordre sur N et aux formules arithmétiquement définissables ; elle exclut les logiques du deuxième ordre, les hiérarchies de la théorie des ensembles et les classes de complexité basées sur des ressources sur structures finies.

Tension sémantique

La tension apparaît avec la hiérarchie analytique et avec des hiérarchies de complexité (par ex. la hiérarchie polynomiale) : des stratifications qui se ressemblent superficiellement diffèrent par leur domaine et par les ressources computationnelles qu'elles expriment.

Synthèse

La hiérarchie arithmétique organise la définissabilité arithmétique par alternance de quantificateurs, de sorte que la forme syntaxique prédit des propriétés de calculabilité et de décidabilité, délimitant r.e., co-r.e. et au-delà.