Introduction à Gentzen et PrawitzGénéré par machine
De la théorie de la démonstration à une théorie de la signification
La question fondamentale est la suivante : qu’est-ce qui donne leur signification aux symboles de la logique ?
Prenons le mot « et ». Lorsque nous affirmons :
« Il pleut et il fait froid »,
nous comprenons immédiatement ce que signifie la conjonction des deux propositions. Mais comment expliquer cette compréhension ?
Une première réponse consiste à dire que nous connaissons les conditions dans lesquelles cette proposition est vraie : elle est vraie lorsque les deux propositions qui la composent sont vraies.
Une seconde réponse consiste à dire que nous savons ce qui nous autorise à affirmer cette proposition, et quelles conséquences nous pouvons en tirer. Pour affirmer légitimement « Il pleut et il fait froid », nous devons pouvoir établir deux choses : qu’il pleut et qu’il fait froid. Inversement, si nous savons qu’il pleut et qu’il fait froid, nous pouvons en conclure qu’il pleut.
Ces deux explications semblent presque équivalentes. Pourtant, elles conduisent à deux manières profondément différentes de concevoir la logique.
La première s’intéresse principalement aux conditions de vérité des propositions. Elle conduit notamment à la sémantique formelle d’Alfred Tarski.
La seconde s’intéresse aux conditions de justification des propositions et aux inférences qu’elles autorisent. Elle conduit à la théorie de la démonstration de Gerhard Gentzen, puis à la sémantique développée par Dag Prawitz.
C’est cette seconde tradition que nous allons étudier.
Son intuition fondamentale pourrait s’énoncer ainsi :
Comprendre une expression logique, c’est notamment savoir comment elle peut être légitimement employée dans un raisonnement.
Nous verrons que cette intuition, relativement simple, possède une formulation mathématique rigoureuse. Elle engage une conception de la preuve, mais aussi des questions philosophiques concernant la signification, la vérité et la connaissance.
I. Quelques repères historiques : comment la démonstration est devenue un objet mathématique
1. D’Aristote à Frege : formaliser le raisonnement
La logique naît, chez Aristote, comme une étude des formes du raisonnement valide.
Considérons le syllogisme suivant :
« Tous les hommes sont mortels. Socrate est un homme. Donc Socrate est mortel. »
Ce qui intéresse le logicien n’est pas d’abord la mortalité de Socrate. C’est la forme de l’argument.
Nous pouvons remplacer les hommes par des mammifères, Socrate par un chien, et conserver une structure de raisonnement valide.
La validité ne dépend donc pas seulement de ce dont nous parlons. Elle dépend de la manière dont les propositions sont articulées.
Pendant des siècles, la logique s’est développée à partir de cette intuition.
Un tournant décisif intervient avec Gottlob Frege et sa Begriffsschrift de 1879.
Frege construit un langage symbolique capable de représenter des raisonnements dont la complexité dépasse largement celle des syllogismes aristotéliciens.
La nouveauté est considérable : les démonstrations peuvent désormais être étudiées à travers des structures symboliques rigoureusement définies.
Deux questions se dégagent progressivement.
La première : qu’est-ce qui rend une proposition vraie ?
La seconde : qu’est-ce qui rend une démonstration correcte ?
Ces questions sont liées, mais elles ne sont pas identiques.
2. Hilbert : la démonstration comme manipulation réglée de symboles
Au début du XXe siècle, David Hilbert entreprend de donner aux mathématiques des fondements rigoureux.
Son programme consiste notamment à formaliser les théories mathématiques pour étudier leurs propriétés par des méthodes mathématiques.
Un système formel comporte, schématiquement, trois éléments :
- Un ensemble de symboles et des règles indiquant comment former des expressions.
- Des axiomes, c’est-à-dire des propositions admises comme points de départ dans le système.
- Des règles d’inférence permettant de déduire de nouvelles propositions à partir de celles dont nous disposons.
Prenons une règle très simple :
Si nous avons établi « Si P, alors Q », et si nous avons également établi P, nous pouvons conclure Q.
C’est le modus ponens.
Hilbert montre ainsi comment les démonstrations peuvent être étudiées comme des objets formels : nous pouvons examiner la succession des symboles et vérifier que chaque opération respecte une règle.
Cette perspective est fondamentale pour la naissance de la métamathématique.
La métamathématique est l’étude mathématique des théories mathématiques elles-mêmes : leurs démonstrations, leur cohérence, leurs limites.
La cohérence signifie ici, approximativement, qu’un système ne permet pas de démontrer simultanément une proposition et sa négation.
Il faut cependant éviter une confusion : formaliser un raisonnement ne signifie pas nécessairement renoncer à toute interprétation de ses symboles. Une même structure formelle peut faire l’objet d’une étude syntaxique et d’une interprétation sémantique.
La syntaxe étudie la formation des expressions et leurs transformations autorisées.
La sémantique étudie leur signification ou leur interprétation.
Cette distinction va devenir essentielle.
3. Gentzen : changer notre manière de représenter les démonstrations
Gerhard Gentzen (1909-1945) intervient dans les années 1930.
Dans ses Untersuchungen über das logische Schließen (« Recherches sur la déduction logique »), publiées en 1934-1935, il propose deux instruments qui vont transformer la logique contemporaine :
- La déduction naturelle (natürliches Schließen).
- Le calcul des séquents (Sequenzenkalkül).
Son point de départ est assez différent de celui de Hilbert.
Au lieu de construire les démonstrations principalement à partir d’une liste d’axiomes logiques, Gentzen cherche à représenter les opérations élémentaires effectivement mobilisées dans les raisonnements mathématiques.
Comment démontrons-nous une conjonction ?
Comment démontrons-nous une implication ?
Que pouvons-nous légitimement conclure lorsque nous possédons une démonstration d’une proposition composée ?
Gentzen organise les règles autour de ces questions.
Il propose notamment de distinguer, pour chaque opérateur logique, deux types de règles :
Les règles d’introduction, qui indiquent comment établir une proposition contenant cet opérateur.
Les règles d’élimination, qui indiquent ce que nous pouvons déduire d’une proposition contenant cet opérateur.
La grande découverte conceptuelle est que ces deux types de règles ne sont pas indépendants.
Les règles d’élimination doivent respecter ce que les règles d’introduction permettent d’établir.
Gentzen suggère que les introductions jouent, en quelque sorte, le rôle de définitions des constantes logiques.
Cette idée sera décisive pour Prawitz.
4. Prawitz : des propriétés des démonstrations à leur signification
Dag Prawitz, logicien suédois né en 1936, publie en 1965 Natural Deduction: A Proof-Theoretical Study.
Il reprend le programme de Gentzen et lui donne une profondeur nouvelle.
Son apport technique majeur est notamment la démonstration de théorèmes de normalisation pour les systèmes de déduction naturelle.
Nous expliquerons ce terme précisément. Pour l’instant, retenons qu’une démonstration peut contenir des détours inutiles et qu’il est possible, dans les systèmes considérés, de transformer systématiquement une démonstration pour éliminer ces détours.
Ce résultat permet d’étudier les propriétés structurelles des démonstrations.
Mais Prawitz va plus loin, particulièrement à partir des années 1970.
Il cherche à comprendre ce qui fait qu’une preuve constitue une justification valide.
Une nouvelle question apparaît alors :
Peut-on expliquer la signification des constantes logiques à partir des conditions dans lesquelles leurs démonstrations sont valides ?
C’est l’une des origines de ce qu’on appelle aujourd’hui la sémantique preuve-théorétique (proof-theoretic semantics).
Il faut distinguer ces étapes historiques. Gentzen a formulé l’idée des définitions inférentielles et établi des résultats fondamentaux sur les démonstrations. Prawitz a développé leur analyse mathématique, puis une conception sémantique de la validité des preuves. La sémantique preuve-théorétique n’est donc pas un théorème unique, découvert une fois pour toutes en 1935. C’est un programme de recherche qui s’est développé sur plusieurs décennies. Stanford Encyclopedia of Philosophy
II. Apprendre à lire la logique de Gentzen
Avant d’aborder sa pensée, nous devons apprendre à lire quelques symboles. Ils sont peu nombreux, et chacun correspond à une opération intellectuelle familière.
1. Les propositions et les connecteurs
Une proposition est, dans notre cadre, quelque chose qui peut être affirmé ou nié et qui est susceptible d’être vrai ou faux.
Par exemple :
« Il pleut. »
« Le sol est mouillé. »
Nous allons remplacer ces propositions par des lettres.
Nous écrirons :
: « Il pleut. »
: « Le sol est mouillé. »
Ces lettres sont des variables propositionnelles. Elles peuvent représenter différentes propositions.
Nous pouvons maintenant construire des expressions plus complexes.
se lit « P et Q ».
Le symbole représente la conjonction.
se lit « P ou Q ».
Le symbole représente la disjonction, au sens inclusif : au moins l’une des propositions est vraie, éventuellement les deux.
se lit « Si P, alors Q ».
Le symbole représente l’implication.
Enfin :
se lit « Non-P ».
Le symbole représente la négation.
On appelle ces symboles des constantes logiques ou, pour les premiers, des connecteurs logiques.
Pourquoi « constantes » ?
Parce que leur rôle logique demeure le même lorsque nous remplaçons les propositions qu’ils relient.
Dans « Il pleut et il fait froid » comme dans « Socrate est grec et Platon est grec », le mot « et » conserve la même fonction logique.
La question de Gentzen est précisément de comprendre comment définir rigoureusement cette fonction.
2. Qu’est-ce qu’une règle d’inférence ?
Considérons le raisonnement suivant :
« Il pleut. »
« Il fait froid. »
« Donc il pleut et il fait froid. »
Nous pouvons le représenter ainsi :
La barre horizontale signifie que ce qui figure au-dessus autorise à conclure ce qui figure au-dessous.
Nous lisons donc :
« Si nous disposons d’une démonstration de P et d’une démonstration de Q, nous pouvons construire une démonstration de P et Q. »
Il faut prendre garde à une distinction capitale.
La règle ne dit pas que P et Q sont effectivement vrais.
Elle dit que si nous sommes autorisés à affirmer séparément P et Q, alors nous sommes autorisés à affirmer leur conjonction.
C’est une règle de passage entre des propositions.
Le mot technique est inférence.
Une inférence est une opération par laquelle nous passons de certaines propositions, appelées prémisses, à une conclusion.
Une démonstration est une organisation de telles inférences, permettant d’établir une conclusion à partir de prémisses ou d’hypothèses.
Gentzen entreprend de décrire systématiquement ces opérations.
III. La première découverte : les règles d’introduction et d’élimination
Nous pouvons maintenant comprendre la première idée fondamentale de Gentzen.
1. Comment introduire une conjonction ?
Reprenons :
Le symbole , placé à droite, est simplement le nom de la règle.
La lettre signifie introduction.
Nous avons donc une règle d’introduction de la conjonction.
Elle indique ce que nous devons posséder pour construire légitimement une proposition de la forme .
Autrement dit, elle spécifie les conditions permettant d’établir une conjonction.
2. Comment éliminer une conjonction ?
Imaginons maintenant que nous disposions d’une démonstration de :
« Il pleut et il fait froid. »
Nous pouvons naturellement en conclure :
« Il pleut. »
Nous pouvons également conclure :
« Il fait froid. »
Gentzen écrit :
et :
Le symbole signifie élimination.
Les indices 1 et 2 distinguent les deux règles : la première permet de retrouver P, la seconde permet de retrouver Q.
Remarquons quelque chose.
Lorsque nous introduisons une conjonction, nous réunissons deux propositions.
Lorsque nous l’éliminons, nous retrouvons l’une des propositions réunies.
La correspondance paraît évidente.
Mais elle possède une conséquence philosophique considérable.
3. Une nouvelle manière de définir le sens de « et »
Demandons-nous ce que signifie le symbole .
Une réponse traditionnelle serait :
« Il signifie la même chose que le mot français « et ». »
Mais nous n’avons rien expliqué. Nous avons simplement traduit un symbole dans une langue que nous comprenons déjà.
Une autre réponse serait de définir les circonstances dans lesquelles est vrai.
Gentzen propose une autre possibilité : définir un opérateur logique par les conditions de son introduction dans une démonstration.
Ainsi, nous n’avons pas besoin de partir d’une traduction du symbole .
Nous pouvons expliquer son rôle directement :
Pour établir , il faut établir P et établir Q.
Une fois établi, nous pouvons en extraire P ou Q.
Le symbole possède donc une fonction déterminée à l’intérieur d’un système d’inférences.
Il n’est pas un simple dessin sur une feuille.
Il commande des opérations précises.
Nous touchons ici au premier principe de la tradition Gentzen-Prawitz :
La signification d’une constante logique peut être caractérisée par les règles qui gouvernent son emploi dans une démonstration.
Chez Gentzen, cette idée apparaît sous la forme d’une proposition méthodologique : les règles d’introduction représentent, pour ainsi dire, les définitions des symboles logiques, tandis que les éliminations doivent être justifiées à partir de ces définitions.
C’est une thèse plus subtile que l’affirmation selon laquelle toute règle attribuerait automatiquement un sens à un symbole. Nous verrons pourquoi. Stanford Encyclopedia of Philosophy
IV. La deuxième découverte : ce que signifie démontrer une implication
La conjonction était particulièrement simple.
Avec l’implication, nous entrons dans la partie la plus intéressante de la logique de Gentzen.
1. Qu’est-ce qu’une implication ?
Considérons :
« Si P, alors Q. »
Par exemple :
« S’il pleut, alors le sol est mouillé. »
Dans la logique classique, une implication matérielle est fausse exactement lorsque son antécédent est vrai et son conséquent faux.
L’antécédent est ici P : ce qui figure avant la flèche.
Le conséquent est Q : ce qui figure après la flèche.
Mais Gentzen nous invite à poser une autre question :
Qu’est-ce qui nous permet de démontrer une implication ?
2. Le raisonnement hypothétique
Imaginons que nous voulions établir :
« Si un nombre est divisible par quatre, alors il est pair. »
Nous pouvons commencer par supposer qu’un nombre est divisible par quatre.
Nous raisonnons ensuite à partir de cette hypothèse.
Si nous parvenons à démontrer que le nombre est pair, nous avons établi l’implication recherchée.
Le point essentiel est que nous n’avons pas démontré que le nombre considéré était effectivement divisible par quatre.
Nous l’avons supposé.
Nous avons montré ce qui s’ensuivrait si cette hypothèse était satisfaite.
La règle de Gentzen s’écrit :
Déchiffrons-la.
Tout en haut figure .
Les crochets indiquent que P est une hypothèse temporaire.
Les points verticaux signifient qu’un raisonnement, éventuellement composé de plusieurs étapes, intervient.
Nous arrivons finalement à Q.
Nous pouvons alors conclure .
La règle nous autorise à décharger l’hypothèse P.
Cette expression technique mérite une explication.
Une hypothèse est dite ouverte tant que notre démonstration dépend d’elle.
Décharger une hypothèse signifie que nous cessons de l’utiliser comme prémisse encore requise pour la conclusion finale.
Nous n’avons plus besoin d’affirmer P.
Nous affirmons seulement que, sous l’hypothèse P, Q peut être établi.
C’est précisément le passage du raisonnement hypothétique à l’implication.
3. Un exemple de démonstration complète
Nous allons démontrer la proposition suivante :
Elle signifie :
« Si P et Q, alors P. »
Cela paraît trivial. Mais nous allons voir comment cette trivialité se construit rigoureusement.
Nous commençons par supposer :
Nous appliquons la règle d’élimination de la conjonction :
Nous avons donc établi P sous l’hypothèse .
Nous pouvons désormais appliquer la règle d’introduction de l’implication.
La démonstration complète s’écrit :
La notation sert uniquement à indiquer quelle hypothèse est déchargée par la dernière règle.
Suivons les opérations dans l’ordre.
D’abord, nous supposons .
Ensuite, nous en déduisons P.
Enfin, puisque P a été démontré sous l’hypothèse , nous concluons :
L’hypothèse initiale est déchargée.
Nous avons donc démontré une proposition sans conserver d’hypothèse ouverte.
On parle d’une démonstration fermée.
Le point important est que nous n’avons jamais eu à déterminer si P et Q étaient effectivement vrais.
Nous avons établi une relation logique qui vaut indépendamment de leur contenu particulier.
4. Le symbole de dérivabilité
Nous pouvons maintenant introduire une notation supplémentaire :
Le symbole se lit « est démontrable » ou « est dérivable », relativement au système de règles considéré.
Il appartient au langage dans lequel nous parlons des démonstrations.
Il ne faut pas le confondre avec , qui est un connecteur situé à l’intérieur des propositions.
Lorsque nous écrivons :
nous affirmons que Q peut être dérivé à partir de P.
Lorsque nous écrivons :
nous formons une proposition conditionnelle.
Cette distinction entre une relation de dérivabilité et un connecteur logique est fondamentale.
On utilise également la notation :
La lettre grecque , appelée gamma, représente un ensemble ou une collection d’hypothèses.
L’expression signifie :
« P est démontrable à partir des hypothèses contenues dans . »
Nous disposons maintenant de l’essentiel du vocabulaire nécessaire pour comprendre le projet de Gentzen.
V. Prawitz : pourquoi toutes les démonstrations ne se valent-elles pas structurellement ?
Nous arrivons à la contribution fondamentale de Prawitz.
Il ne suffit plus de savoir quelles propositions peuvent être démontrées.
Nous nous intéressons désormais à la structure interne des démonstrations elles-mêmes.
1. Une démonstration peut comporter des détours
Considérons le raisonnement suivant :
« Il pleut. »
« Il fait froid. »
« Donc il pleut et il fait froid. »
« Donc il pleut. »
Le raisonnement est parfaitement correct.
Pourtant, une étape paraît inutile.
Pourquoi avoir commencé par réunir deux propositions, si nous voulions simplement retrouver la première ?
Formellement, nous avons :
Regardons attentivement cette démonstration.
Nous possédons P et Q.
Nous introduisons une conjonction.
Puis nous éliminons immédiatement cette conjonction pour retrouver P.
Nous sommes donc revenus à une proposition dont nous disposions déjà.
Il suffit de conserver la démonstration initiale de P.
Nous pouvons supprimer les deux opérations intermédiaires.
Cette suppression constitue ce qu’on appelle une réduction.
2. Le principe de normalisation
La situation devient beaucoup plus intéressante lorsque les démonstrations comprennent des dizaines, des centaines ou des milliers d’étapes.
Peut-on identifier systématiquement les détours ?
Peut-on les supprimer ?
Et surtout, peut-on garantir que ce processus aboutira à une démonstration débarrassée de ces détours ?
C’est le problème de la normalisation.
Une démonstration est dite normale lorsqu’elle ne contient plus les détours pertinents définis par le calcul.
Dans les systèmes étudiés, les théorèmes de normalisation garantissent que les démonstrations peuvent être transformées en démonstrations normales.
Il ne s’agit donc pas simplement d’un conseil stylistique invitant à écrire des preuves plus élégantes.
C’est un résultat mathématique sur la structure des démonstrations.
Prawitz publie en 1965 une démonstration générale de normalisation pour d’importants systèmes de déduction naturelle, puis contribue aux résultats de normalisation forte au début des années 1970.
La normalisation forte signifie que tout enchaînement de réductions autorisées finit par s’arrêter, même si nous choisissons des détours à supprimer dans des ordres différents.
La distinction est importante : dans la normalisation ordinaire, on cherche une procédure qui aboutit ; dans la normalisation forte, toute suite de réductions conforme aux règles doit aboutir. Stanford Encyclopedia of Philosophy
3. Pourquoi cette propriété concerne-t-elle la signification ?
Revenons à notre conjonction.
Pour démontrer , nous devons disposer de démonstrations de P et de Q.
Si nous introduisons la conjonction puis l’éliminons, nous retrouvons simplement ce qui avait permis de l’introduire.
L’élimination ne nous donne rien qui dépasse les ressources justificatives engagées dans l’introduction.
Prawitz reprend et précise ici une idée de Gentzen, sous le nom de principe d’inversion.
Dans sa forme intuitive, ce principe signifie que les règles d’élimination doivent pouvoir être justifiées à partir des possibilités ouvertes par les règles d’introduction.
Autrement dit :
Ce qu’une expression nous permet de déduire doit être proportionné à ce qui nous permet de l’établir.
Cette idée paraît presque banale dans le cas de la conjonction.
Mais elle devient profonde avec l’implication.
4. La normalisation de l’implication
Supposons que nous possédions une démonstration de :
Nous l’avons obtenue en supposant P, puis en démontrant Q sous cette hypothèse.
Supposons maintenant que nous possédions également une démonstration indépendante de P.
Nous pouvons utiliser le modus ponens :
Nous obtenons Q.
Mais observons ce qui vient de se passer.
La démonstration de contenait déjà une méthode permettant de passer d’une démonstration de P à une démonstration de Q.
Et nous disposons précisément d’une démonstration de P.
Nous pouvons donc remplacer l’hypothèse P, dans notre première démonstration, par la démonstration effective de P.
Nous obtenons directement une démonstration de Q.
L’implication intermédiaire devient inutile.
Ce procédé s’appelle une substitution de preuve.
Il constitue le mécanisme central de réduction des détours liés à l’implication.
Philosophiquement, il suggère une interprétation remarquable :
Une preuve de peut être comprise comme une méthode permettant de transformer une preuve de P en une preuve de Q.
Nous ne considérons plus seulement l’implication comme une relation entre deux valeurs de vérité.
Nous la considérons comme une transformation entre justifications.
Cette idée est l’un des points de rencontre entre la théorie de la démonstration, la logique intuitionniste et la conception constructive des mathématiques.
VI. L’harmonie : peut-on inventer n’importe quel connecteur logique ?
Une difficulté apparaît maintenant.
Si la signification d’une constante logique est donnée par ses règles, ne pouvons-nous pas inventer arbitrairement de nouveaux connecteurs ?
Pourquoi ne pas décider qu’un symbole quelconque obéira à toutes les règles que nous souhaitons ?
Cette question a été formulée de manière particulièrement frappante par Arthur Prior en 1960.
1. Le connecteur « tonk »
Prior imagine un connecteur artificiel, nommé tonk.
Il propose deux règles.
La première nous autorise à passer de P à :
La seconde nous autorise à passer de cette dernière expression à Q.
Nous avons donc :
et :
Appliquons maintenant ces deux règles successivement.
À partir de P, nous obtenons .
À partir de cette nouvelle proposition, nous obtenons Q.
Nous pouvons donc dériver :
Or P et Q sont arbitraires.
Cela signifie que nous pouvons déduire n’importe quelle proposition de n’importe quelle autre.
Par exemple, à partir de « 2 est pair », nous pourrions dériver « 2 est impair ».
Le système perdrait toute capacité à distinguer les inférences légitimes des inférences arbitraires.
On dit qu’il se trivialise.
2. Pourquoi « tonk » ne fonctionne-t-il pas ?
Comparons « tonk » et la conjonction.
Pour introduire , il fallait établir P et Q.
Pour éliminer , nous pouvions obtenir P ou Q.
Les deux opérations étaient ajustées l’une à l’autre.
Avec « tonk », il suffit d’avoir établi P pour introduire une proposition dont l’élimination permet d’obtenir Q.
Nous retirons donc davantage d’informations que nous n’en avions apportées.
Les deux règles sont déséquilibrées.
C’est ce qui conduit les successeurs de Gentzen à parler d’harmonie entre introduction et élimination.
Le terme est particulièrement associé aux développements de Michael Dummett, même si le principe d’inversion de Prawitz en constitue une formulation technique antérieure.
L’exemple de Prior permet de comprendre un problème philosophique important : toutes les règles d’inférence ne constituent pas des définitions logiques acceptables.
Il faut établir des critères permettant de distinguer des règles cohérentes et équilibrées de celles qui détruisent la structure de la conséquence logique. Cambridge University Press
Nous pouvons désormais formuler plus précisément l’ambition de cette tradition :
La signification d’une expression logique ne résulte pas du simple fait qu’on lui associe des règles. Elle dépend de la structure et de la justification de ces règles.
C’est exactement ce que la normalisation permet, en partie, d’étudier mathématiquement.
VII. Pourquoi parle-t-on ici de sémantique ?
C’est probablement le point philosophiquement le plus important de notre cours.
Nous avons étudié des règles, des démonstrations et des transformations de démonstrations.
Mais pourquoi parler de signification ?
Pour comprendre cela, nous devons distinguer deux conceptions de la sémantique formelle.
1. La sémantique de Tarski : interpréter les expressions
Alfred Tarski (1901-1983) a joué un rôle décisif dans le développement de la sémantique logique.
Dans le cadre de la sémantique modèle-théorétique, nous considérons un langage formel et nous lui donnons une interprétation.
Qu’est-ce qu’une interprétation ?
Prenons un exemple.
Nous disposons d’un langage contenant un prédicat :
La lettre R pourrait signifier « est rouge ».
La lettre représente une variable individuelle : elle occupe la place d’un objet.
Supposons que notre domaine comporte trois objets : une pomme, une banane et une cerise.
Le domaine est simplement l’ensemble des objets sur lesquels portent nos propositions.
Nous pouvons interpréter R comme le prédicat qui s’applique exactement à la pomme et à la cerise.
Nous avons alors déterminé son extension, c’est-à-dire l’ensemble des objets auxquels il s’applique.
Pour déterminer si est satisfait, il nous faut encore attribuer une valeur à la variable .
Si nous attribuons la pomme à , la formule est satisfaite.
Si nous attribuons la banane à , elle ne l’est pas.
Une assignation est précisément une fonction qui attribue des objets du domaine aux variables individuelles.
Et un modèle est, dans ce contexte, une structure mathématique qui fournit notamment un domaine et une interprétation des symboles non logiques.
Ainsi, nous pouvons déterminer les conditions de satisfaction d’une formule.
Dans la notation usuelle :
Cela se lit :
« Le modèle , sous l’assignation , satisfait la formule . »
Le symbole exprime ici la satisfaction sémantique.
Il se distingue du symbole , qui exprimait la dérivabilité dans un système de preuve.
L’opposition entre les deux est fondamentale :
signifie que P est démontrable à partir de .
Tandis que :
signifie que, dans tous les modèles considérés où les propositions de sont vraies, P est également vraie.
La première relation est définie en termes de démonstrations.
La seconde en termes d’interprétations et de vérité dans des modèles.
Dans certains systèmes, notamment en logique classique du premier ordre, les théorèmes de correction et de complétude permettent d’établir une correspondance exacte entre ces deux relations.
Mais cette correspondance ne rend pas les deux approches conceptuellement identiques.
La sémantique modèle-théorétique nous indique comment une expression est évaluée relativement à une interprétation.
La théorie de la démonstration nous indique comment une proposition peut être établie à partir d’autres propositions. Stanford Encyclopedia of Philosophy
2. Une autre conception : la sémantique preuve-théorétique
Revenons maintenant à notre symbole :
Dans la sémantique classique des valeurs de vérité, nous expliquons la conjonction en disant :
est vraie exactement lorsque P et Q sont toutes deux vraies.
Nous caractérisons ainsi la conjonction par ses conditions de vérité.
Dans la tradition Gentzen-Prawitz, nous pouvons procéder autrement.
Nous expliquons ce qui compte comme une démonstration de .
Pour disposer d’une démonstration canonique de cette proposition, nous devons disposer d’une démonstration de P et d’une démonstration de Q.
Une démonstration est dite canonique lorsqu’elle établit directement une proposition en terminant par la règle d’introduction appropriée.
Une démonstration non canonique peut cependant constituer une justification valable si elle peut être ramenée, au moyen des réductions appropriées, à une démonstration canonique.
Nous avons ainsi commencé à caractériser la signification d’une expression logique à partir des conditions de validité de ses démonstrations.
C’est le principe de la sémantique preuve-théorétique.
L’expression preuve-théorétique est la traduction de l’anglais proof-theoretic.
Elle signifie simplement que nous étudions la signification en nous appuyant sur la théorie des démonstrations.
La différence conceptuelle est profonde.
Dans le premier cadre, nous nous demandons essentiellement :
« Dans quelles conditions cette proposition est-elle vraie ? »
Dans le second :
« Qu’est-ce qui constitue une justification de cette proposition ? »
Il ne s’agit pas seulement de remplacer un vocabulaire par un autre.
Nous choisissons des notions fondamentales différentes pour expliquer la signification.
3. Quel rôle joue alors Prawitz ?
À partir des années 1970, Prawitz développe une conception de la validité preuve-théorétique.
L’idée est d’identifier ce qui fait qu’une structure de raisonnement constitue effectivement une preuve valide.
Très schématiquement, il donne un rôle fondamental aux démonstrations canoniques.
Une démonstration non canonique est justifiée si elle peut être réduite de manière appropriée à une démonstration canonique valide.
Et une démonstration dépendant d’hypothèses doit rester valide lorsque celles-ci sont remplacées par des démonstrations valides des propositions correspondantes.
Cette dernière exigence est particulièrement intéressante.
Elle signifie que la validité d’une inférence ne tient pas seulement à la disposition des symboles.
Elle dépend également de la possibilité de substituer aux hypothèses des justifications effectives sans compromettre la validité de l’argument.
La sémantique se construit donc à partir d’une théorie des justifications et de leurs transformations.
Nous pouvons comprendre pourquoi les résultats techniques de normalisation ont acquis une portée philosophique.
Ils permettent de préciser ce que signifie expliquer une proposition par ses conditions de preuve. Stanford Encyclopedia of Philosophy
VIII. Le tournant philosophique : vérité, justification et usage
Nous pouvons maintenant situer Gentzen et Prawitz dans l’histoire de la philosophie contemporaine.
Trois rapprochements sont particulièrement importants.
1. L’héritage du constructivisme mathématique
Le premier concerne le constructivisme et l’intuitionnisme.
L’intuitionnisme mathématique, associé notamment à L. E. J. Brouwer, remet en question l’idée selon laquelle la vérité mathématique pourrait être comprise indépendamment de nos possibilités de construction ou de démonstration.
Considérons le principe du tiers exclu :
Il signifie :
« P ou non-P. »
En logique classique, ce principe est universellement valide.
Mais que se passe-t-il si nous demandons une démonstration constructive de cette proposition ?
Pour démontrer une disjonction , nous devons, selon l’interprétation constructive ordinaire, disposer d’une démonstration de P ou d’une démonstration de Q.
Appliquons cela au tiers exclu.
Pour démontrer constructivement , il faudrait disposer soit d’une démonstration de P, soit d’une démonstration de sa négation.
Or, pour une proposition arbitraire, nous ne disposons pas nécessairement de l’une ou de l’autre.
Voilà pourquoi le tiers exclu n’est pas universellement démontrable en logique intuitionniste.
Il faut être précis : cela ne signifie pas que l’intuitionniste soutient que le tiers exclu est faux dans tous les cas. Cela signifie que son acceptation comme principe logique général ne se justifie pas par les règles constructives ordinaires.
Nous rencontrons ici un désaccord philosophique majeur.
La vérité mathématique doit-elle être pensée indépendamment des preuves ?
Ou faut-il donner un rôle constitutif aux conditions dans lesquelles nous pouvons effectivement justifier une proposition ?
La sémantique preuve-théorétique appartient historiquement à cette seconde famille de préoccupations, même si elle ne se confond pas purement et simplement avec toutes les thèses de Brouwer.
Il serait également erroné de présenter Gentzen et Prawitz comme des auteurs qui auraient exclusivement travaillé sur la logique intuitionniste : leurs contributions techniques concernent aussi la logique classique.
2. Dummett : une théorie de la signification à partir de l’usage
Le deuxième rapprochement concerne Michael Dummett (1925-2011).
Dummett reprend et développe une question héritée de Frege :
Que faut-il expliquer lorsque nous prétendons rendre compte de la signification d’une expression ?
Il insiste sur le fait que comprendre une expression est une capacité qui doit pouvoir se manifester dans son emploi.
Autrement dit, une théorie de la signification doit rendre intelligible ce que nous savons faire lorsque nous comprenons un langage.
L’idée rencontre directement la théorie de la démonstration.
Si comprendre une conjonction consiste notamment à savoir ce qui permet de l’affirmer et ce que nous pouvons en inférer, alors les règles de Gentzen constituent une ressource particulièrement précieuse.
Dummett voit dans la théorie de la démonstration un instrument permettant de développer une conception de la signification en termes de justification.
Cette conception intervient dans son opposition entre réalisme et antiréalisme sémantiques.
La question n’est pas seulement de savoir si les objets existent indépendamment de nous.
Elle concerne aussi la manière dont nous comprenons les conditions de vérité des propositions, particulièrement lorsqu’elles dépassent nos capacités possibles de vérification.
Dummett s’intéresse ainsi à la relation entre vérité et possibilité de reconnaissance ou de justification.
La théorie de la démonstration fournit un cadre technique pour formuler certaines de ces questions.
Mais attention : on ne peut pas déduire directement une métaphysique antiréaliste d’un théorème de normalisation.
Il existe des étapes philosophiques supplémentaires.
3. De Gentzen à Brandom : l’inférentialisme
Le troisième rapprochement nous conduit à une tradition philosophique plus récente : l’inférentialisme.
Cette position est particulièrement associée à Robert Brandom.
Son intuition générale est que le contenu conceptuel d’une expression doit être expliqué, au moins fondamentalement, par sa place dans les relations d’inférence.
Prenons le concept de mammifère.
Comprendre ce concept, c’est notamment savoir que :
« Cet animal est un mammifère »
autorise certaines conclusions, par exemple :
« Cet animal est un vertébré. »
Inversement, certaines informations peuvent justifier l’application du concept de mammifère.
Le concept est ainsi inséré dans un réseau de conséquences et de conditions d’application.
Nous retrouvons une structure familière.
D’un côté, les circonstances dans lesquelles nous sommes autorisés à employer une expression.
De l’autre, les conséquences auxquelles cet emploi nous engage.
Il existe donc une parenté importante entre les définitions inférentielles de Gentzen-Prawitz et l’inférentialisme philosophique contemporain.
Mais il faut distinguer les niveaux.
Gentzen étudie principalement les règles de formation des démonstrations et les propriétés des systèmes logiques.
Prawitz développe une théorie de la validité des preuves et une sémantique des constantes logiques.
Brandom cherche à proposer une théorie beaucoup plus générale du contenu conceptuel, des pratiques discursives et des engagements normatifs.
Chez Brandom, la question concerne aussi les rapports entre interlocuteurs, leurs engagements et leurs autorisations à affirmer.
Chez Prawitz, elle concerne prioritairement la structure justificative des preuves.
La sémantique preuve-théorétique est donc une forme particulièrement rigoureuse et circonscrite d’approche inférentielle de la signification.
Elle n’épuise pas à elle seule le programme de l’inférentialisme général.
IX. Une conséquence remarquable : les démonstrations ressemblent à des programmes
Je voudrais introduire brièvement une dernière idée, parce qu’elle permet de mesurer l’importance historique de ces travaux.
Revenons à l’implication :
Nous avons vu qu’une démonstration constructive de cette implication peut être comprise comme une méthode transformant une preuve de P en une preuve de Q.
Or cette description ressemble singulièrement à celle d’un programme informatique.
Un programme peut recevoir une donnée en entrée, accomplir une transformation et produire une donnée en sortie.
De même, une démonstration de peut être représentée comme une transformation prenant une preuve de P et produisant une preuve de Q.
Ce rapprochement est formalisé par la correspondance de Curry-Howard.
Dans certaines théories des types, les propositions correspondent à des types, et leurs preuves à des programmes ou à des objets de preuve.
Sans entrer dans la théorie des types, nous pouvons retenir l’analogie fondamentale :
Démontrer une implication revient à construire une transformation.
Appliquer cette implication à une preuve revient à exécuter cette transformation.
Normaliser une démonstration correspond alors à simplifier ou évaluer le programme qui lui est associé.
Il s’agit d’une correspondance mathématique précise, et pas seulement d’une métaphore.
Cette tradition a profondément influencé la logique informatique, les langages de programmation fonctionnels et les assistants de preuve contemporains.
Un résultat initialement formulé dans l’étude des fondements des mathématiques est ainsi devenu l’une des ressources fondamentales de l’informatique théorique. Stanford Encyclopedia of Philosophy
X. Jusqu’où peut-on aller ? Trois distinctions philosophiques indispensables
Nous avons acquis les principales idées de Gentzen et de Prawitz.
Il reste à préciser leur portée. Sans ces distinctions, nous risquerions de transformer un programme technique rigoureux en une doctrine philosophique trop générale.
1. Définir les constantes logiques n’est pas définir tous les symboles
Lorsque Gentzen suggère que les règles d’introduction constituent des définitions, il parle principalement des constantes logiques.
C’est une restriction essentielle.
Les lettres P et Q qui figurent dans nos démonstrations sont des variables propositionnelles.
Elles occupent la place de propositions quelconques.
Les règles d’introduction de la conjonction ne nous disent pas ce que signifie P.
Elles nous disent comment fonctionne , quelles que soient les propositions placées de part et d’autre.
Pour obtenir une interprétation complète d’un langage, il faut donc encore s’occuper des expressions atomiques, c’est-à-dire de celles qui ne sont pas construites à partir de connecteurs logiques.
Dans plusieurs variantes de la sémantique preuve-théorétique, on part justement d’un système de règles gouvernant les propositions atomiques.
La signification des propositions complexes est ensuite expliquée à partir de cette base.
On ne peut donc pas conclure que les règles logiques suffisent à attribuer automatiquement une signification complète à tous les signes imaginables.
2. Une définition inférentielle n’est pas une définition par référence
Revenons à la conjonction.
Nous pouvons expliquer son rôle à partir de ses règles d’introduction et d’élimination.
Cette explication ne consiste pas à désigner un objet particulier auquel le symbole renverrait.
Mais cela ne signifie pas que les signes logiques seraient absolument dépourvus de toute interprétation dénotationnelle possible.
Dans une sémantique classique, la conjonction possède par exemple une interprétation parfaitement déterminée comme opération sur les valeurs de vérité.
Le point de la sémantique preuve-théorétique n’est pas nécessairement de nier toute possibilité de cette interprétation.
Il consiste à proposer une explication de la signification qui ne prend pas la référence ou les conditions de vérité comme notions primitives.
La différence est décisive.
Une théorie de la signification peut donner la priorité à la preuve sans soutenir que les interprétations référentielles sont impossibles ou incohérentes.
3. Un théorème mathématique n’est pas encore une philosophie de la signification
Dernière distinction, peut-être la plus importante.
Un théorème de normalisation établit une propriété mathématique d’un système de démonstration.
Il montre que certaines transformations des preuves sont possibles.
Nous pouvons ensuite interpréter philosophiquement ce résultat.
Nous pouvons soutenir, par exemple, que la possibilité de réduire les démonstrations non canoniques à des démonstrations canoniques fournit une explication de la validité des preuves.
Nous pouvons encore soutenir que cette structure constitue une explication satisfaisante du sens des constantes logiques.
Mais ces deux propositions ne sont pas exactement le théorème mathématique lui-même.
Elles mobilisent des engagements supplémentaires concernant ce que doit accomplir une théorie de la signification.
C’est pourquoi il existe, à l’intérieur même de la sémantique preuve-théorétique, des désaccords sur la notion de preuve valide, sur la justification des règles et sur l’étendue du programme.
Ces désaccords n’annulent nullement les résultats de Gentzen et de Prawitz.
Ils montrent simplement que l’élucidation philosophique de la signification ne se réduit pas à l’établissement d’un résultat formel.
XI. Ce qu’il faut finalement comprendre de Gentzen et de Prawitz
Je voudrais terminer en réunissant les éléments de ce parcours autour d’une seule question.
Qu’est-ce que comprendre une proposition logique ?
Imaginons que nous rencontrions un nouveau symbole :
Nous ignorons ce qu’il signifie.
Comment pourrions-nous l’apprendre ?
Une première méthode consisterait à nous donner sa traduction dans une langue familière.
Une deuxième méthode consisterait à nous expliquer ses conditions de vérité.
Une troisième méthode consisterait à nous montrer comment il intervient dans les démonstrations : dans quelles conditions pouvons-nous introduire une formule contenant ce symbole, et quelles inférences son emploi autorise-t-il ?
C’est cette troisième possibilité que Gentzen ouvre avec une puissance particulière.
Mais il comprend également que les opérations autorisées doivent être cohérentes entre elles.
Prawitz reprend cette exigence et la développe mathématiquement.
Les preuves ne sont plus seulement des successions de propositions correctes.
Elles possèdent une structure susceptible d’être analysée, simplifiée et comparée.
Certaines démonstrations sont canoniques ; d’autres peuvent être ramenées à une forme canonique.
Leur validité dépend de propriétés précises.
Ces propriétés deviennent les ressources d’une théorie de la signification.
Nous pouvons alors distinguer trois interrogations qui traversent toute cette tradition.
La première est logique : quelles règles permettent de construire des démonstrations correctes ?
La deuxième est métalogique : quelles propriétés possèdent les démonstrations construites selon ces règles ?
La troisième est sémantique : les structures ainsi mises au jour permettent-elles d’expliquer ce que signifient les expressions logiques ?
Gentzen apporte des instruments décisifs pour répondre aux deux premières questions et formule une intuition déterminante concernant la troisième.
Prawitz développe considérablement l’analyse mathématique des démonstrations et propose une réponse systématique à la question sémantique.
C’est pourquoi leurs travaux occupent une place charnière entre la théorie de la démonstration, la philosophie des mathématiques et les théories contemporaines de la signification.
Pour approfondir
Je recommande trois textes, dans cet ordre.
1. Gerhard Gentzen, « Untersuchungen über das logische Schließen » (1934-1935). Il existe une traduction anglaise sous le titre Investigations into Logical Deduction. C’est le texte fondateur. Sa lecture permet de comprendre l’invention de la déduction naturelle et la fonction des règles d’introduction et d’élimination.
2. Dag Prawitz, Natural Deduction: A Proof-Theoretical Study (1965). C’est le grand texte technique de référence. Il introduit notamment une formulation précise du principe d’inversion et développe la théorie de la normalisation.
3. Dag Prawitz, « The Philosophical Position of Proof Theory » (1972). C’est une excellente porte d’entrée dans les ambitions proprement philosophiques de son programme, en particulier dans la distinction entre une théorie qui étudie les preuves pour elles-mêmes et une théorie qui les traite seulement comme instruments métamathématiques.
Pour accompagner ces lectures, les articles de la Stanford Encyclopedia of Philosophy consacrés à la sémantique preuve-théorétique, à la déduction naturelle et au développement historique de la théorie de la démonstration offrent des présentations rigoureuses et permettent de situer les résultats dans leur contexte.
Je retiendrais surtout cette proposition, qui condense la nouveauté philosophique du programme :
Une expression logique n’a pas besoin d’être d’abord expliquée par ce qu’elle désigne. Sa signification peut être comprise à partir de ce qui justifie son affirmation et des inférences que celle-ci autorise.
C’est le passage d’une conception de la signification centrée sur la vérité à une conception centrée sur les conditions de justification. Ce passage ne résout pas toutes les questions de la sémantique. Il déplace profondément la manière de les poser.