Hiérarchie arithmétique
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article 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 assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à...) 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 \neg \forall x \equiv \exists x \neg. 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 d’objets (les éléments de l'ensemble), « une multitude qui peut...) 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 exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en...), 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 suivants :) de Turing.

Page générée en 0.040 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique