Hiérarchie arithmétique - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs est disponible ici.

En calculabilité, on considère les formules logiques (du premier ordre) de la forme

formule \Pi_n : \forall a_1 \exists a_2 \cdots \phi(a_1\cdots a_n)
formule \Sigma_n : \exists a_1 \forall a_2 \cdots \phi(a_1\cdots a_n)

φ 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: \forall x \forall y \forall z devient \forall (x,y,z). 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.

Page générée en 0.025 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise