Langage : synthèse et défis

Résumé

Cette leçon clôt l’unité consacrée au langage de la logique propositionnelle. Elle reconstruit la chaîne déductive qui va de la distinction entre validité et vérité, et de l’analyse des paradoxes, à la lecture unique des formules et à la formalisation des énoncés et des raisonnements, en indiquant à chaque maillon quel principe est utilisé et dans quelle leçon il est démontré ; elle situe l’acquis par rapport au plan du cours et explique pourquoi le langage déjà construit pose la question de l’unité suivante, consacrée à la déduction. Elle reprend dans son évaluation de sortie les compétences de l’évaluation d’entrée et se termine par six défis, d’une difficulté supérieure à celle des problèmes des leçons, qui exigent de combiner les instruments de plusieurs d’entre elles.

Objectifs d’apprentissage

Reconstruire l’ordre logique des résultats de l’unité, en identifiant le principe sur lequel s’appuie chacun d’eux et la leçon où il est démontré.
Expliquer comment s’enchaînent le principe de clôture, la décomposition en mots, le lemme du poids et la lecture unique, et pourquoi de cette dernière dépendent les définitions par récurrence et la comparaison des formalisations.
Distinguer ce que l’unité a démontré de ce qu’elle a admis comme hypothèse (la bivalence, le schéma de vérité, le principe de récurrence et la lecture de la négation conjointe) et de ce qu’elle a laissé aux unités suivantes.
Résoudre des problèmes qui combinent le lemme diagonal, le dénombrement des chaînes, l’induction sur les formules, l’argument du poids et le dépliage des abréviations.

L’acquis de l’unité

L’unité s’était proposé de construire, à partir d’un alphabet de deux symboles, un langage où chaque formule se lit d’une seule manière, de démontrer avec rigueur les propriétés de ce langage et de jeter un pont entre lui et la langue dans laquelle nous raisonnons. Le but a été atteint avec quelques réserves, chacune déclarée en son lieu : la bivalence et le schéma de vérité, que la première leçon n’a pas admis comme des vérités mais comme des hypothèses explicites, pour examiner ce qui arrive lorsqu’on les maintient ensemble ; le principe de récurrence sur les entiers naturels, qui est admis comme le cinquième axiome de Peano ; la lecture informelle de la négation conjointe, qui est stipulée et que l’unité de sémantique transformera en définition ; et l’indispensable de la théorie des ensembles (appartenance, inclusion et réunion), enseigné là où il était nécessaire. Avec ces réserves, le chemin parcouru peut se lire comme une seule chaîne déductive en quatre tronçons.

Raisonner et parler du langage

La leçon sur ce qu’est la logique mathématique a fixé l’objet du cours : non la vérité des énoncés, qui relève de chaque science, mais sa transmission. Un raisonnement est valide lorsque sa forme n’admet aucune instance à prémisses vraies et à conclusion fausse, et de cette définition on a déduit la seule chose que garantit la validité : si les prémisses sont vraies, la conclusion l’est aussi ; d’où un raisonnement valide à conclusion fausse a quelque prémisse fausse, et une forme est non valide exactement lorsqu’elle a un contre-exemple. Ce même résultat a fait de l’analyse des paradoxes une procédure : si les pas d’un raisonnement qui aboutit à une contradiction sont valides, quelque hypothèse est fausse, et résoudre le paradoxe, c’est trouver laquelle. C’est ainsi qu’a été traité le menteur, où la bivalence et le schéma de vérité ne peuvent être maintenus ensemble pour une phrase qui se déclare fausse, et ainsi qu’ont été traités le paradoxe de Berry et l’adjectif « hétérologique ». Du barbier on a tiré un lemme général, le lemme diagonal, qui démontre que le barbier n’existe pas et que le principe de compréhension sans restriction est contradictoire. La leçon a établi enfin la distinction entre langage objet et métalangage, et entre l’usage d’une expression et sa mention, qui gouverne tout ce qui suit : les résultats de l’unité sur les formules ne sont pas des formules, mais des métathéorèmes.

La langue des cercles et des disques

La leçon sur le langage de la logique propositionnelle a introduit les ensembles et les chaînes, a compté les chaînes de chaque longueur (il y en a $2^{n}$ de longueur $n$ , et $2^{N + 1} - 2$ de longueurs $1$ à $N$ ) et a construit la langue de base : les variables $v_n = \sigO^{n}\sigI$ et une seule règle, qui de deux formules $\varphi$ et $\psi$ forme $\sigI\varphi\psi$ . La clause « rien d’autre n’est une formule » a été rendue précise en définissant les formules comme les chaînes qui appartiennent à tous les ensembles clos, et de cette définition on a déduit le principe de clôture, grâce auquel on a démontré que toute formule est une variable ou est $\sigI\varphi\psi$ , et pas les deux, que toute formule se termine par un disque et qu’elle contient un nombre impair de disques. L’observation que les variables et le disque isolé forment un code préfixe a donné la décomposition unique en mots, et avec elle la notion de poids. La leçon a construit aussi le métalangage avec lequel on travaille désormais : les métavariables, la négation conjointe écrite $(\varphi \downarrow \psi)$ et les six abréviations officielles, chacune définie une seule fois à partir des précédentes, de sorte que toute expression abrégée désigne une seule chaîne.

Induction et lecture unique

La leçon sur la récurrence sur les entiers et l’induction sur les formules a justifié les dénombrements que la leçon précédente avait conclus par « et ainsi de suite », a déduit la récurrence forte de la récurrence simple et, en appliquant la première à la longueur, a obtenu l’induction structurelle, qui se révèle être la même récurrence sur les entiers naturels transportée aux formules. Avec cet instrument, elle a démontré le lemme du poids : toute formule pèse $+1$ , et tout préfixe par mots propre et non vide pèse au plus $0$ . Il s’ensuit, dans cet ordre, qu’aucune formule n’est préfixe propre d’une autre et que toute formule composée se lit d’une manière unique. La lecture unique est le maillon auquel est suspendu le reste de l’unité : elle justifie la procédure de décision que la leçon sur le langage avait décrite comme une dette qui se solde, et elle légitime les définitions par récurrence (la longueur, le nombre de variables et de disques connecteurs, les sous-formules, la profondeur et la substitution), qui sans elle pourraient attribuer à une formule deux valeurs différentes.

Du français aux formules

La leçon sur la formalisation du langage naturel a jeté le pont vers la langue. Elle a fixé la convention des lettres $p$ , $q$ , $r$ , $s$ et $t$ comme noms de cinq variables déterminées, a exigé que toute formalisation déclare son dictionnaire et a déduit, de la seule lecture stipulée de la négation conjointe, la lecture de chaque abréviation. Avec la lecture unique, elle a démontré que deux parenthésages différents des mêmes connecteurs sont des formules différentes, et avec la définition par récurrence de la longueur elle a calculé combien mesurent les abréviations dépliées, ce qui donne un critère rapide pour séparer des formalisations. Elle a montré que l’implication matérielle n’est fausse que lorsque l’antécédent est vrai et le conséquent faux, et que c’est la seule lecture, dépendant uniquement de la vérité des parties, qui rend vrais les théorèmes conditionnels des mathématiques ; elle a signalé ce que la formalisation perd (quantificateurs, temps, causalité, modalité) et s’est terminée par la formalisation de raisonnements complets comme un ensemble de prémisses $\Gamma$ et une conclusion.

La figure suivante réunit les quatre tronçons en une seule chaîne. Chaque nœud de la colonne est une définition ou un résultat, numéroté selon l’ordre logique et relié par un arc aux maillons antérieurs qu’utilise sa démonstration ; autour flottent les appuis, c’est-à-dire les principes auxquels la chaîne recourt sans cesse, chacun relié par un trait plein aux maillons qui s’appuient sur lui et par un trait pointillé au maillon où il est établi, sauf ceux qui sont admis sans démonstration, qui sont dessinés comme des anneaux. Un clic sur un appui met en évidence tous les maillons qui l’utilisent, et chaque maillon renvoie à la leçon où il est démontré. On remarquera que la procédure de décision, bien qu’exposée dans la leçon sur le langage, occupe sa place logique après la lecture unique, sur laquelle elle s’appuie.

Appuis de la chaîne

ABivalence. Toute proposition est vraie ou fausse, et non les deux ; être fausse équivaut à ne pas être vraie. Elle est admise comme hypothèse explicite dans l’analyse des paradoxes. Admis sans démonstration dans cette unité.
BSchéma de vérité. Une phrase est vraie si et seulement si ce qu’elle dit est le cas. Il est admis comme hypothèse explicite ; la solution de Tarski le conserve, mais seulement pour les phrases d’un langage qui ne contient pas son propre prédicat de vérité. Admis sans démonstration dans cette unité.
CPrincipe de récurrence. Si une propriété est vraie pour $1$ et si, chaque fois qu’elle est vraie pour un entier naturel $k$ , elle l’est pour $k + 1$ , alors elle est vraie pour tous les entiers naturels. C’est le cinquième axiome de Peano, et il est admis. Admis sans démonstration dans cette unité.
DLemme diagonal. Aucun objet $b$ d’une collection ne vérifie $R(b, x) \Leftrightarrow \neg R(x, x)$ pour tout $x$ de la collection. Établi dans: 3. Lemme diagonal.
EPrincipe de clôture. Une propriété qu’ont toutes les variables et qui passe de $\varphi$ et $\psi$ à $\sigI\varphi\psi$ est celle de toutes les formules. Établi dans: 5. Principe de clôture.
FInduction structurelle. L’induction sur la complexité des formules, déduite de la récurrence forte sur la longueur : son initialisation porte sur les variables, et son hérédité, sur l’unique règle de formation. Établi dans: 9. Induction structurelle.
GLecture unique. Si $\sigI\varphi\psi = \sigI\varphi'\psi'$ , les quatre chaînes étant des formules, alors $\varphi = \varphi'$ et $\psi = \psi'$ . Établi dans: 11. Lecture unique.
HLecture de la négation conjointe. La formule $(\varphi \downarrow \psi)$ est vraie exactement lorsque $\varphi$ et $\psi$ sont toutes deux fausses. C’est la seule lecture stipulée ; les autres s’en déduisent, et l’unité de sémantique la précisera. Admis sans démonstration dans cette unité.

Tronçon 1 Raisonner et parler du langage
- Distinguer la validité de la vérité et réfuter une forme non valide par un contre-exemple.
- Reconnaître les ambiguïtés du langage naturel et séparer les lectures d’un énoncé.
- Distinguer le langage objet du métalangage, et l’usage d’une expression de sa mention.
- Analyser un paradoxe en isolant ses hypothèses et en décidant laquelle doit être abandonnée.
1. Ce que garantit la validité. Si un raisonnement est valide et que toutes ses prémisses sont vraies, sa conclusion est vraie ; d’où un raisonnement valide à conclusion fausse a quelque prémisse fausse, et une forme est non valide exactement lorsqu’elle a un contre-exemple.
  Démontré dans: Qu’est-ce que la logique mathématique.
2. Le paradoxe du menteur. Appliqués à la phrase $m$ , « la phrase $m$ est fausse », la bivalence et le schéma de vérité donnent $V(m) \Leftrightarrow \neg V(m)$ ; pour un langage qui contient $m$ , l’une des deux hypothèses doit être abandonnée, et l’issue de Tarski est qu’aucun langage ne contienne son propre prédicat de vérité, de sorte que $m$ ne peut pas être formée.
  Utilise: 1. Ce que garantit la validité. Repose sur: A (Bivalence), B (Schéma de vérité). Démontré dans: Qu’est-ce que la logique mathématique.
3. Lemme diagonal. Si $R$ est une relation entre les objets d’une collection $D$ , telle que chaque $R(x, y)$ est vraie ou fausse, aucun $b$ de $D$ ne vérifie $R(b, x) \Leftrightarrow \neg R(x, x)$ pour tout $x$ de $D$ .
  Repose sur: A (Bivalence). Démontré dans: Qu’est-ce que la logique mathématique.
4. Le barbier et Russell. Il n’existe pas d’homme du village qui rase exactement les hommes du village qui ne se rasent pas eux-mêmes ; et le principe de compréhension sans restriction est contradictoire, parce qu’il affirme l’existence de l’ensemble $Z = \{ x : x \notin x \}$ .
  Repose sur: D (Lemme diagonal). Démontré dans: Qu’est-ce que la logique mathématique.
Tronçon 2 La langue des cercles et des disques
- Décrire des ensembles de chaînes et compter les chaînes de chaque longueur.
- Définir les formules comme le plus petit ensemble clos et en déduire le principe de clôture.
- Démontrer des propriétés de toutes les formules et s’en servir pour écarter des chaînes.
- Décomposer une chaîne en mots et déplier les abréviations jusqu’à la langue de base.
1. Principe de clôture. L’ensemble $\mathcal{F}$ des formules est le plus petit ensemble de chaînes qui contient les variables $v_n = \sigO^{n}\sigI$ et qui, avec $\varphi$ et $\psi$ , contient $\sigI\varphi\psi$ ; par conséquent, une propriété qu’ont les variables et qui passe de $\varphi$ et $\psi$ à $\sigI\varphi\psi$ est celle de toutes les formules.
  Démontré dans: Le langage de la logique propositionnelle.
2. Forme des formules. Toute formule est une variable ou est $\sigI\varphi\psi$ avec $\varphi$ et $\psi$ des formules, et pas les deux : toute variable commence par $\sigO$ , et toute formule composée, par $\sigI$ .
  Repose sur: E (Principe de clôture). Démontré dans: Le langage de la logique propositionnelle.
3. Dernier symbole et nombre de disques. Toute formule se termine par un disque et contient un nombre impair de disques ; d’où ni la concaténation de deux formules ni la chaîne $\sigI\varphi$ ne sont des formules.
  Repose sur: E (Principe de clôture). Démontré dans: Le langage de la logique propositionnelle.
4. Décomposition en mots. Toute chaîne qui se termine par un disque se décompose d’une manière unique en mots, c’est-à-dire en variables $\sigO^{n}\sigI$ et en disques isolés, parce que chaque mot se termine par son unique disque et qu’aucun n’est préfixe propre d’un autre.
  Démontré dans: Le langage de la logique propositionnelle.
Tronçon 3 Induction et lecture unique
- Démontrer par récurrence simple et forte, et en déduire l’induction sur la complexité des formules.
- Démontrer le lemme du poids et en déduire la lecture unique.
- Décider si une chaîne est une formule et reconstruire sa formation.
- Définir des fonctions sur les formules par récurrence et démontrer des relations entre elles.
1. Induction structurelle. La récurrence forte se déduit de la récurrence simple ; appliquée à la longueur, elle donne le principe d’induction sur la complexité : si les variables ont une propriété et que celle-ci passe de $\varphi$ et $\psi$ à $\sigI\varphi\psi$ , toutes les formules l’ont.
  Utilise: 6. Forme des formules. Repose sur: C (Principe de récurrence). Démontré dans: Récurrence sur les entiers et induction sur les formules.
2. Lemme du poids. Si chaque occurrence de variable pèse $+1$ et chaque disque connecteur $-1$ , toute formule pèse $+1$ et tout préfixe par mots propre et non vide d’une formule pèse au plus $0$ ; en particulier, toute formule a une occurrence de variable de plus que de disques connecteurs.
  Utilise: 8. Décomposition en mots. Repose sur: F (Induction structurelle). Démontré dans: Récurrence sur les entiers et induction sur les formules.
3. Lecture unique. Aucune formule n’est préfixe propre d’une autre ; d’où, si $\sigI\varphi\psi = \sigI\varphi'\psi'$ , les quatre chaînes étant des formules, alors $\varphi = \varphi'$ et $\psi = \psi'$ .
  Utilise: 7. Dernier symbole et nombre de disques, 8. Décomposition en mots, 10. Lemme du poids. Démontré dans: Récurrence sur les entiers et induction sur les formules.
4. Procédure de décision. Une chaîne qui se termine par $\sigO$ n’est pas une formule ; si elle se termine par $\sigI$ , on la décompose en mots. Si le premier mot est une variable, la chaîne est une formule exactement lorsque cette variable est son seul mot. Si c’est un disque, on tient la dette après lui : si elle ne s’annule jamais, la chaîne n’est pas une formule ; si elle s’annule, la coupure entre $\varphi$ et $\psi$ se trouve là où elle s’annule pour la première fois, et chaque segment s’examine de la même façon, sachant que la chaîne vide n’est pas une formule.
  Utilise: 6. Forme des formules, 7. Dernier symbole et nombre de disques, 8. Décomposition en mots. Repose sur: G (Lecture unique). Démontré dans: Le langage de la logique propositionnelle.
5. Définition par récurrence. Étant donnés une valeur pour chaque variable et une règle qui calcule la valeur de $\sigI\varphi\psi$ à partir de $\varphi$ , de $\psi$ et de leurs valeurs, il existe exactement une fonction sur les formules qui les respecte ; c’est ainsi que se définissent la longueur, les sous-formules, la profondeur et la substitution, qui produit toujours des formules.
  Utilise: 6. Forme des formules. Repose sur: C (Principe de récurrence), F (Induction structurelle), G (Lecture unique). Démontré dans: Récurrence sur les entiers et induction sur les formules.
Tronçon 4 Du français aux formules
- Formaliser des énoncés avec un dictionnaire explicite, en décidant de la portée de chaque connecteur.
- Déplier des abréviations pour décider si deux formalisations sont la même formule.
- Distinguer l’implication matérielle du « si… alors » de la langue et signaler ce que la formalisation perd.
- Formaliser des raisonnements complets comme un ensemble de prémisses et une conclusion.
1. Longueur des abréviations. Si $L(\varphi) = a$ et $L(\psi) = b$ , les chaînes de $\neg\varphi$ , $(\varphi \vee \psi)$ , $(\varphi \rightarrow \psi)$ et $(\varphi \wedge \psi)$ mesurent $2a + 1$ , $2a + 2b + 3$ , $4a + 2b + 5$ et $8a + 8b + 15$ ; deux formalisations de longueurs différentes sont des formules différentes.
  Utilise: 13. Définition par récurrence. Démontré dans: Formalisation du langage naturel.
2. Portée et formules différentes. Les parenthésages $((p \wedge q) \vee r)$ et $(p \wedge (q \vee r))$ sont des chaînes différentes : s’ils coïncidaient, la lecture unique, appliquée deux fois, obligerait la variable $r$ à coïncider avec la formule composée $(p \wedge q)$ .
  Utilise: 6. Forme des formules. Repose sur: G (Lecture unique). Démontré dans: Formalisation du langage naturel.
3. Implication matérielle. L’implication $(\varphi \rightarrow \psi)$ , qui abrège $(\neg\varphi \vee \psi)$ , n’est fausse que lorsque $\varphi$ est vraie et $\psi$ fausse ; c’est la seule lecture, dépendant uniquement de la vérité des parties, qui rend vrais les théorèmes conditionnels des mathématiques.
  Repose sur: H (Lecture de la négation conjointe). Démontré dans: Formalisation du langage naturel.

Vers la déduction. La chaîne s’arrête là où le langage est construit et où les raisonnements sont formalisés comme un ensemble de prémisses et une conclusion. Il reste à décider quand une formule découle d’autres : d’abord en manipulant des symboles avec des règles, dans l’unité suivante, et ensuite en considérant leur vérité.