Théorème d'élimination des coupures

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En logique mathématique, le théorème d'élimination des coupures (ou Hauptsatz de Gentzen) est le résultat central établissant l'importance du calcul des séquents. Il a été initialement prouvé par Gerhard Gentzen en 1934 dans son article historique « Investigations in Logical Deduction » pour les systèmes LJ et LK formalisant la logique intuitionniste et classique, respectivement. Le théorème d'élimination des coupures stipule que toute déclaration qui possède une preuve dans le calcul des séquents, faisant usage de la règle de coupure, possède aussi une preuve sans coupure, à savoir, une preuve qui ne fait pas usage de la règle de coupure[1],[2].

La règle de coupure[modifier | modifier le code]

Article détaillé : règle de coupure.

Un séquent est une expression logique concernant plusieurs phrases, sous la forme  «  », qui est lu «  prouve  », et (comme déclaré par Gentzen) doit être compris comme équivalente à la fonction de vérité «  Si ( et  et  …) alors ( ou  ou  …). »[3] Notez que le côté gauche (CG) est une conjonction (et) et le côté droit (CD) est une disjonction (ou).

Le CG peut avoir arbitrairement plus ou moins de formules; lorsque le CG est vide, le CD devient une tautologie. Dans LK, le CD peut aussi avoir un certain nombre de formules, s'il n'en a pas, le CG est une contradiction, alors que dans LJ, le CD ne peut avoir soit qu'une formule, soit aucune: nous voyons ici qu'avoir plus d'une formule du CD est équivalent, en présence de la règle de contraction droite, à l'admissibilité du principe du tiers exclu (car est alors prouvable). Depuis la logique LC de Jean-Yves Girard, il est facile d'obtenir une formalisation assez naturelle de la logique classique où le CD contient au plus une formule.

La « coupure » est une règle du calcul des séquents, et est équivalente à une variété de règles d'autres théories de la démonstration, ce qui, étant donné

et

permet de déduire

Autrement dit, il « coupe » les occurrences de la formule hors de la relation d'inférence.

Élimination de la coupure[modifier | modifier le code]

Le théorème d'élimination des coupures stipule que, pour un système donné, tout séquent prouvable en utilisant la règle de coupure peut être prouvé sans l'utilisation de cette règle.

Pour le calcul des séquents, qui ont seulement une formule du CD, la règle de coupure, étant donné

et

permet de déduire

Si nous considérons comme un théorème, alors l'élimination de la coupure dans ce cas, dit simplement qu'un lemme utilisé pour démontrer ce théorème peut être inliné. Chaque fois que la démonstration du théorème mentionne le lemme , nous pouvons remplacer les occurrences de la démonstration de . Par conséquent, la règle de coupe est admissible.

Voir aussi[modifier | modifier le code]

Notes[modifier | modifier le code]

  • Curry 1977, pp. 208–213, donne une démonstration du théorème d'élimination.
  • Kleene 2009, pp. 453, donne une très brève démonstration du théorème d'élimination des coupures.
  • Wilfried Buchholz, Beweistheorie (Allemagne, 2002-2003)
  • Références[modifier | modifier le code]