Langage : introduction

Évaluation d’entrée

Avant de parcourir l’unité, il convient de mesurer le point de départ. Cette évaluation est une autoévaluation : elle n’est pas notée, et son seul but est d’orienter l’étude. Ses onze questions portent, dans l’ordre, sur les quatre leçons de l’unité : trois sur la première, trois sur la deuxième, deux sur la troisième et trois sur la quatrième. Qui n’a jamais étudié la logique ne doit pas s’attendre à toutes les réussir, et cela n’a pas d’importance : chaque réponse, juste ou non, explique le point et nomme la leçon qui le traite. Les mêmes compétences sont mesurées de nouveau à la fin, dans la leçon de synthèse ; comme il s’agit de la première unité d’un cours sans prérequis, il n’y a pas de questions sur des unités antérieures.

Les contenus de l’unité

Cette unité sert, avant tout, le premier des objectifs du cours, distinguer le langage objet du métalangage et décider à l’aide des règles de formation si une chaîne est une formule ; elle sert aussi le deuxième, formaliser des énoncés et des raisonnements du langage naturel, et elle prépare le quatrième, démontrer des métathéorèmes par induction, qui accompagnera le cours jusqu’à sa dernière unité. Son but est qu’au terme de l’unité on sache ce qu’étudie la logique, que l’on dispose d’un langage formel construit en toute rigueur, que l’on sache démontrer des propriétés de toutes ses formules et que l’on puisse y traduire des énoncés et des raisonnements du français, en sachant ce que la traduction conserve et ce qu’elle perd. Ses quatre leçons forment une chaîne dans laquelle chacune s’appuie sur les précédentes.

1. Qu’est-ce que la logique mathématique. Elle délimite l’objet de la discipline : non la vérité des énoncés particuliers, mais la validité, la relation entre prémisses et conclusion qui garantit que la vérité des premières passe à la seconde. Elle distingue la validité de la vérité, montre pourquoi le langage naturel, ambigu et capable de parler de lui-même, ne suffit pas pour l’étudier, et établit la distinction entre langage objet et métalangage. Elle analyse, en explicitant leurs hypothèses, les paradoxes du menteur, de Berry, du barbier et de Russell, et se termine par la carte du cours.
2. Le langage de la logique propositionnelle. Elle enseigne l’indispensable sur les ensembles et sur les chaînes de symboles, dénombre les chaînes que l’on peut écrire avec deux symboles et construit la langue de base : une infinité de variables écrites avec des cercles et des disques, une seule règle de formation et une clause de clôture, dont on déduit un principe pour démontrer des propriétés de toutes les formules. Elle donne une procédure pour décider si une chaîne est une formule et construit, sur la langue de base, le métalangage avec lequel on travaillera désormais : les métavariables, la négation conjointe écrite avec des parenthèses et les abréviations officielles des autres connecteurs.
3. La récurrence sur les entiers et l’induction sur les formules. Elle enseigne la récurrence sur les entiers naturels, simple et forte, et la transpose aux formules sous la forme de l’induction structurelle. Avec elle, elle démontre le lemme du poids et, à partir de lui, le théorème de lecture unique, que la leçon précédente avait énoncé : chaque formule composée se décompose d’une seule façon. La lecture unique légitime enfin les définitions par récurrence sur les formules (longueur, sous-formules, profondeur) et la substitution d’une sous-formule par une autre.
4. La formalisation du langage naturel. Elle jette le pont entre le français et le langage formel : le dictionnaire d’une formalisation, la lecture de chaque connecteur déduite de celle du connecteur primitif, les subtilités de « mais », « seulement si » et « à moins que », la portée des connecteurs, l’implication matérielle et ce que la logique propositionnelle ne peut pas exprimer. Elle se termine en formalisant des raisonnements complets comme un ensemble de prémisses et une conclusion, que les unités suivantes soumettront à la déduction et à la sémantique.

L’unité se termine par la leçon de synthèse et défis, qui rassemble l’acquis en une chaîne déductive, reprend dans son évaluation de sortie les compétences de l’évaluation d’entrée et propose des défis qui combinent plusieurs leçons.

La place de l’unité dans le cours

Le cours parcourt, pour le langage le plus simple de la logique, le chemin complet d’une théorie logique, et il le fait en quatre parties, qui sont ses quatre unités de contenu. La première, celle-ci, fixe le langage. La deuxième, la déduction, définit ce que signifie qu’une formule $\varphi$ s’obtienne d’un ensemble de formules $\Gamma$ au moyen d’axiomes et de règles d’inférence, ce qui s’écrira $\Gamma \vdash \varphi$ ; c’est la face syntaxique de la validité, où l’on manipule des symboles sans égard à leur signification. La troisième, la sémantique, attribue à chaque formule une valeur de vérité dans chaque valuation et définit ce que signifie que $\varphi$ soit conséquence de $\Gamma$, ce qui s’écrira $\Gamma \models \varphi$ ; c’est la face sémantique de la validité. La quatrième, la métathéorie, démontre que les deux faces coïncident : la correction dit que tout ce qui est déductible est conséquence, et la complétude, que toute conséquence est déductible.

S’il en est ainsi, la syntaxe n’est pas un préambule que l’on puisse abréger, mais la condition des trois autres parties. Une déduction est une suite de formules, et pour décider si une suite en est une il faut savoir, sans hésitation, quelles chaînes sont des formules et comment elles se décomposent ; une valuation s’étend des variables à toutes les formules par récurrence, et la définition par récurrence ne donne une valeur à chaque formule que si chaque formule se lit d’une seule manière ; les théorèmes de la métathéorie se démontrent par induction sur la complexité des formules ou par récurrence sur la longueur des déductions. Il s’ensuit l’ordre de l’unité : d’abord, ce que l’on veut étudier et pourquoi il faut un langage formel ; ensuite, le langage ; puis l’instrument pour démontrer quelque chose de toutes ses formules, avec lequel on prouve la lecture unique ; et, enfin, le pont vers les raisonnements du français, qui sont la raison d’être de tout ce qui précède.

Pourquoi une langue de cercles et de disques

Le langage du cours a un alphabet de deux symboles seulement, le cercle $\sigO$ et le disque $\sigI$, et une seule règle de formation : si $\varphi$ et $\psi$ sont des formules, $\sigI\varphi\psi$ en est une aussi. La $n$-ième variable est la chaîne de $n$ cercles suivis d’un disque, $v_{n} = \sigO^{n}\sigI$. À première vue, le choix est étrange, car les formules ainsi écrites sont difficiles à lire. Il a pourtant quatre raisons précises.

La première est que deux symboles suffisent pour écrire une infinité de variables sans sortir d’un alphabet fini, de sorte que toute formule est, littéralement, une chaîne finie de symboles d’un ensemble à deux éléments, et que les questions sur le langage sont des questions sur des chaînes, que l’on peut dénombrer et comparer. La deuxième est qu’une seule règle laisse un seul cas dans chaque démonstration par induction : ce qui est prouvé pour les variables et pour $\sigI\varphi\psi$ est prouvé pour toutes les formules, sans un cas par connecteur. La troisième est que la règle place le connecteur devant ses deux arguments, comme dans la notation que Jan Łukasiewicz proposa dans les années 1920, et c’est pourquoi elle n’a pas besoin de parenthèses : la lecture unique se démontre par un argument d’une page, qui attribue à chaque variable le poids $+1$ et à chaque disque connecteur le poids $-1$. La quatrième est que l’unique connecteur, la négation conjointe, « ni $\varphi$ ni $\psi$ », suffit pour exprimer tous les autres, comme l’observa Charles Sanders Peirce vers 1880 et comme le publia Henry Sheffer en 1913, et comme le démontrera l’unité de sémantique ; de sorte que l’économie du langage ne sacrifie rien de ce que la logique propositionnelle peut dire.

Or le prix de cette économie est la lisibilité, et l’unité le paie dans le métalangage : personne n’écrira au quotidien des chaînes de cercles et de disques, mais leurs noms, $(\varphi \downarrow \psi)$, $\neg\varphi$, $(\varphi \rightarrow \psi)$, définis une seule fois et dépliables, à tout moment, jusqu’à la chaîne qu’ils désignent. Par conséquent, le cours travaille à deux niveaux à la fois : une langue de base minimale, sur laquelle on démontre, et une notation commode, avec laquelle on écrit ; et la distinction entre langage objet et métalangage, que la première leçon introduit, est celle qui permet de ne pas les confondre.

Ce qui est tenu pour acquis

L’unité part de presque rien. Elle ne suppose pas d’avoir étudié la logique, ni de connaître la théorie des ensembles, ni d’avoir jamais démontré un théorème : ce qu’elle utilise des ensembles, la deuxième leçon l’enseigne, et ce qu’elle utilise de la récurrence, la troisième. Elle suppose seulement deux choses. La première, lire avec attention : dans un langage formel, un symbole ajouté ou omis change la chaîne, et l’ordre des mots d’une définition importe autant que les mots eux-mêmes. La seconde, l’arithmétique élémentaire des entiers naturels, qui dans ce cours sont $1, 2, 3, \ldots$ : additionner et multiplier, calculer des puissances de $2$, distinguer les nombres pairs des impairs et reconnaître un nombre premier.

Qui souhaite un appui supplémentaire pour la récurrence peut consulter les leçons sur les axiomes de Peano et sur les sommes et la récurrence du cours Algèbre et géométrie I ; ce n’est pas nécessaire, car la troisième leçon de cette unité enseigne la récurrence à partir de son énoncé.

Le problème que l’unité résout

La logique étudie la validité, et la validité dépend de la forme des raisonnements. Mais, pour parler de la forme avec rigueur, il faut que chaque expression ait une seule forme, et le langage naturel ne le garantit pas : « le double de trois plus quatre » peut valoir $10$ ou $14$, selon le regroupement. Cela pose deux problèmes, qui sont ceux de l’unité. Le premier est de construire un langage dans lequel chaque expression se lise d’une seule façon. Le second est de le démontrer : les formules sont en nombre infini, et aucune vérification au cas par cas, si longue soit-elle, n’établit qu’elles se lisent toutes d’une seule façon. L’exemple suivant montre les deux problèmes dans une seule expression.

La réponse de l’unité à ces deux problèmes a donc deux parties. Pour le premier, une langue dont l’unique règle place le connecteur devant, de sorte que les parenthèses sont superflues, et un métalangage dont les abréviations désignent chacune une seule chaîne. Pour le second, un principe de démonstration, l’induction sur la complexité des formules, qui passe d’un nombre fini de vérifications (les variables et la règle) à toutes les formules, de même que la récurrence sur les entiers passe de $1$ et du passage de $k$ à $k + 1$ à tous les nombres. Avec ces deux parties, la forme d’un raisonnement devient un objet précis, et la question de sa validité peut être posée avec rigueur dans les unités suivantes.

Comment étudier l’unité

Il convient de commencer par cette évaluation d’entrée et de noter les questions manquées, qui signalent les leçons où il faut s’attarder. Les quatre leçons doivent être étudiées dans l’ordre, car chacune utilise ce qu’établissent les précédentes. Dans la deuxième et la troisième, l’étude exige papier et crayon : les chaînes de cercles et de disques se lisent mal à l’écran, et il convient de les recopier, de séparer leurs mots (chaque variable et chaque disque isolé) et de noter le poids de chacun, jusqu’à ce que le décompte de la lecture unique devienne une habitude. Les démonstrations sont publiées sous forme de lecteurs pas à pas, et chaque étape doit pouvoir être justifiée avant d’avancer. Dans la première et la quatrième, le travail est de lecture attentive : devant chaque phrase du français, se demander ce qu’elle affirme exactement, quelles lectures elle admet et quelle formule la représente. Enfin, l’indication et la réponse de chaque problème proposé ne s’ouvrent qu’après l’avoir sérieusement tenté.

Où elle mène

Au terme de l’unité, le langage sera fixé, et les unités suivantes bâtiront sur lui sans le remettre en discussion. Celle de déduction définira un système d’axiomes et deux règles d’inférence, le modus ponens et, une fois démontrée la double négation, le remplacement de la double négation, dont les déductions sont des suites de formules ; ses axiomes s’écrivent avec les abréviations officielles, que cette unité définit, et son théorème de déduction se démontre par récurrence sur la longueur des déductions, avec l’instrument qu’on apprend ici. Sa première leçon est celle des systèmes déductifs formels. Celle de sémantique attribuera des valeurs de vérité aux variables et les étendra à toutes les formules par récurrence, ce qui n’est possible que grâce à la lecture unique ; elle justifiera par des tables les lectures informelles des connecteurs qu’utilise la quatrième leçon, et démontrera, dans la leçon sur la complétude fonctionnelle, que la négation conjointe suffit pour exprimer n’importe quel connecteur. Celle de métathéorie, enfin, démontrera par induction la correction et la complétude, et les raisonnements que cette unité apprend à formaliser pourront, au bout du compte, être tranchés indifféremment par la déduction ou par la sémantique.

Hors de ce cours, la syntaxe d’un langage formel est celle de tout langage de programmation : un compilateur, comme ceux de Programmation en C++ I, commence par décider si un programme est bien formé et par le décomposer d’une seule façon. La distinction entre la validité et la vérité est aussi le point de départ de la Logique aristotélicienne, qui étudie la forme des syllogismes ; et la récurrence de la troisième leçon est la même qui démontre les propriétés des nombres en Algèbre et géométrie I. Dans tous ces domaines, comme dans la rédaction de règlements et de contrats, la leçon est la même : dire avec précision ce que l’on affirme exige un langage dans lequel chaque expression ait une seule lecture.