Une Preuve Formelle et Intuitionniste du Théorème de Complétude de la Logique Classique

Extract

Introduction. Il est bien connu que la correspondance de Curry-Howard permet d'associer un programme, sous la forme d'un λ-terme, à toute preuve intuitionniste, formalisée dans le calcul des prédicats du second ordre (voir, par exemple [3]). Cette correspondance a été étendue, assez récemment, à la logique classique moyennant une extension convenable du λ-calcul (voir [1, 4, 5, 6]). Chaque théorème formalisé en logique du second ordre correspond donc à une spécification de programme.

Il se pose alors le problème, en général tout à fait non trivial, de trouver la spécification associée à un théorème donné; autrement dit, de déterminer le comportement opérationnel commun aux λ-termes associés aux diverses démonstrations formelles du théorème considéré.

Cette question est résolue ici pour le théorème de complétude de la logique classique.

La première étape consiste à formaliser convenablement ce théorème en logique du second ordre. Ce travail est fait complètement dans la section 1. Il a comme sous-produit, peut-être inattendu, de montrer que ce théorème est prouvable en logique intuitionniste du second ordre (section 2). Ceci, toutefois, à condition d'introduire une légère variante de la notion de modèle, en admettant un modèle supplémentaire trivial, où toute formule est satisfaite.

On notera, à ce sujet, que des preuves intuitionnistes du théorème de complétude de la logique intuitionniste, utilisant des variantes de la notion de modele de Kripke, ont été données par H. Friedman [7] et W. Veldman [8]. On remarquera également qu'un argument de G. Kreisel [2] montre que le théorème de complétude habituel de la logique intuitionniste n'a pas de preuve intuitionniste.