Leibniz et les canards

Commençons par une remarque banale. Si le signe « égal » signifie que ce qui est à gauche et ce qui est à droite sont la même chose, l'énoncé 2+4=6 pose clairement un problème. En effet, chacun peut constater qu'à gauche du signe égal, il y a une suite de 3 caractères (2+4) et à droite une suite de 1 caractère (6), distinctes. Il est donc curieux qu'on considère que ces deux objets soient égaux.

Qu'est-ce donc que l'égalité ? C'est alors qu'intervient Gottfried Wilhelm Leibniz (comme je ne suis ni Janine ni Rama, je ne tenterai pas de le dessiner).

On attribue à Leibniz une définition de l'égalité entre deux objets comme l'impossibilité de discerner l'un de l'autre : autrement dit, on considère que deux objets sont égaux si toute propriété de l'un est également vraie de l'autre. Cette idée est reliée à la notion familière du « test du canard » :

« Si ça ressemble à un canard, si ça nage comme un canard et si ça cancane comme un canard, c'est qu'il s'agit sans doute d'un canard. »

On a pourtant constaté qu'il est possible de différencier 2+4 de 6 très simplement : la propriété « longueur » (en nombre de caractères) diffère sur l'un et l'autre. Où est l'astuce ?

La réponse habituelle est que ce n'est pas la suite de caractères (ou l'arbre de syntaxe abstraite), mais ce qu'il « signifie » ou « dénote ». Cette distinction entre notation et dénotation est un des piliers de la présentation usuelle de la logique mathématique, où l'on distingue d'une part une théorie de la preuve (on essaye de définir sur des critères plutôt syntaxiques ce qu'est une preuve mathématique), d'autre part la théorie des modèles (on essaye de définir le sens, ou la sémantique, des symboles et formules). Notons que cette distinction et les idées d'Alfred Tarski à ce sujet sont d'ailleurs critiquées par le logicien Jean-Yves Girard, qui a là dessus une plaisanterie mettant en jeu des brocolis…


Axiomes

Dans l'approche classique des mathématiques, on tente de définir le sens des opérations utilisées à l'aide d'axiomes. Pour l'arithmétique élémentaire, on va poser comme axiome qu'il existe un nombre appelé 0, un nombre 1, et une opération + qui à deux nombres associe un troisième. Le signe 2 est considéré comme une notation, une abréviation, pour 1+1, le signe 3 pour 2+1, le signe 4 pour 3+1, le signe 5 pour 4+1, le signe 6 pour 5+1. On pose comme axiome que pour tout x et y, (x+1)+y=(x+y)+1. Comme 2+4 est une abréviation pour (1+1)+4, en appliquant cet axiome on obtient que 2+4=1+5. On pose comme axiome que pour tout x et y, x+y=y+x. Alors 1+5=5+1, c'est-à-dire 6. On a donc prouvé que 2+4=6 par application successive d'axiomes. Notons que si nous avions eu non pas 2, mais 2000 (considéré comme une notation pour 1999+1, 1999 étant considéré comme une notation pour 1998+1, etc.), on aurait dû appliquer 2000 axiomes…

Les petits cailloux

Examinons l'axiome pour tout x et y, (x+1)+y=(x+y)+1. Il nous est familier sous la forme d'un calcul très simple sur un boulier (je suis conscient qu'il existe des formes de calcul plus sophistiquées à l'aide de cet instrument) : si nous avons des boules sur la gauche d'une rangée du boulier et des boules à droite, nous pouvons faire passer les boules de la gauche vers la droite une par une sans changer le nombre total de boules ; ici, si nous avons des unités à gauche du signe +, nous pouvons les faire passer une à une à droite sans changer le résultat. Un axiome d'égalité peut s'utiliser dans les deux sens : 2+4=3+3=2+4=1+5…, nous pourrions errer longtemps sans arriver à 6. En revanche, si nous décidons de ne l'appliquer que de la gauche vers la droite, autrement dit de réécrire l'expression (x+1)+y en (x+y)+1 mais pas l'inverse, nous lui donnons un caractère effectif ou calculatoire : à force de bouger une par une les unités de la gauche vers la droite, nous finirons par toutes les ôter et à avoir le résultat. Autrement dit, en orientant l'axiome d'égalité, nous avons obtenu un algorithme, une méthode de calcul automatisée (qui s'appelle l'addition unaire).

On m'objectera que l'algorithme ci-dessus, s'il colle avec les méthodes élémentaires sur les bouliers, ou les méthodes à base de petits cailloux (et calcul vient de calculus, le caillou… comme dans « calcul rénal »), n'est pas celui appris à l'école primaire pour additionner deux nombres… mais oui, vous savez bien, on aligne les deux nombres, on applique la table d'addition sur les chiffres en partant de la droite et en propageant l'éventuelle retenue.

Dans cet algorithme 456 n'est pas une notation pour (1+1) + 1… +1 456 fois ; c'est la suite des symboles 4, 5, 6. On a donc un algorithme, nommé addition décimale, qui opère sur des suites de symboles parmi 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. L'avantage de celle-ci sur l'addition unaire est qu'elle demande bien moins de pas de calcul : le nombre de pas de calcul est environ le nombre de chiffres des nombres, et non les nombres eux mêmes ! Ainsi additionner deux nombres à 6 chiffres, donc compris entre 100 000 et 999 999 va prendre 7 pas de calcul, ce qui est bien inférieur. Plus généralement, le nombre de pas de calcul de l'addition unaire est exponentiellement plus grand que celui de l'addition décimale (je précise au passage qu'exponentiel a un sens mathématique précis, qui n'est pas celui de son emploi incorrect en langage courant, soit « très gros » ou « qui augmente très vite »).

Voyons où nous sommes arrivés. Nous avions une formulation intuitive de l'addition (on peut faire passer les cailloux d'un tas à l'autre, ça ne change pas le total), nous avons observé que nous pouvions la rendre effective en ne les faisant passer que de la gauche à la droite, puis nous avons proposé une méthode qui n'a rien à voir et apprise à l'école primaire comme un fait acquis. Qui nous dit que les deux méthodes coïncident ? Déjà, dans l'une, 4 est une notation pour IIII (quatre petits cailloux posés les uns à côté des autres), de l'autre c'est un symbole indivisible. Il faudrait, en toute rigueur, établir une correspondance précise entre les symboles utilisé par l'une et par l'autre et montrer que les résultats calculés sont identiques.

L'addition de l'école primaire

L'addition sur des chiffres décimaux opère sur les chiffres 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, c'est-à-dire inférieurs à 10. On aurait pu aussi bien travailler sur les chiffres ٠‎ ١‎ ٢‎ ٣‎ ٤‎ ٥‎ ٦‎ ٧‎ ٨‎ ٩‎, cela n'aurait rien changé. On aurait pu aussi bien, par convention, travailler sur α β γ δ ε ζ η θ ι κ : cela n'a pas d'importance, tant que la table d'addition utilisée par l'algorithme est adaptée pour travailler sur ces symboles. Les symboles n'ont, en effet, pas de sens en eux-mêmes : leur sens est apporté par le comportement des opérations qu'on leur applique. Autrement dit, βγ, ٢‎٣, et 23 auraient des comportements similaires dans les diverses versions de l'algorithme de sorte que, suivant le « test du canard », il conviendrait de ne pas les distinguer. Il est cependant évident que l'on peut distinguer 2 et ٢ typographiquement : autrement dit, la définition de l'égalité de Leibniz doit en général s'entendre « par rapport à certaines caractéristiques observables » voire « par rapport à certaines caractéristiques observables en changeant ce qui doit être changé » (2 se comporte par rapport à 3 comme ٢ par rapport à ‎٣). 000045 est égal à 45 au sens de Leibniz à partir du moment où l'on a décidé que le nombre de zéros initiaux n'est pas une caractéristique observable. 2+1 est égal à 3 au sens de Leibniz à part du moment où l'on a décidé que les symboles 2, +, 1 ne sont pas observables et que seul compte le résultat final du calcul.

Une extension plus amusante de l'addition décimale est de ne pas se limiter à des chiffres 0 à 9, mais de prendre des chiffres 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, les six derniers se comportant comme les nombres dix, onze, douze, treize, quatorze, quinze, seize. On parle de notation hexadécimale, et tout se passe comme pour l'addition décimale, sauf que la table d'addition est un carré de seize sur seize cases et non dix sur dix. On peut aussi bien fonctionner en base trois (chiffres 0, 1, 2) ; dans mon enfance, il restait encore des traces de l'enseignement des « maths modernes » à l'école primaire, dont l'apprentissage de la base trois, je crois afin de faire prendre conscience du caractère arbitraire de la base dix. Il est vrai qu'on a supprimé ces « maths modernes », peut-être parce qu'elles paraissaient incompréhensibles pour les parents (de la même façon que certains ne semblent pas percevoir le caractère arbitraire de la couleur rose associée aux filles).

Un cas intéressant en pratique est l'usage de la base deux : les chiffres ne sont plus que 0 et 1, la table d'addition est d'une grande simplicité, et l'algorithme peut facilement se mettre en œuvre électroniquement (il suffit de quelques transistors pour chaque chiffre). Remarquons ici que l'usage du binaire en informatique n'a rien de fondamental et de profond au niveau de la théorie du calcul (c'est important, j'insiste, même si je suis conscient que cela va à l'encontre du lieu commun du rôle fondamental des 0 et des 1 en informatique) : on peut faire la même chose en décimal, en base trois, en hexadécimal…, mais le binaire à l'avantage de permettre de réaliser simplement des circuits électroniques. En revanche, l'unaire (compter sur les doigts, les petits cailloux, les petits bâtons à tracer…), s'il permet les mêmes calculs, est considérablement moins efficaces.

Le passage de l'unaire au décimal est un saut conceptuel non trivial. Il me semble intéressant de constater que les chiffres romains sont en quelque sorte « au milieu du gué » : on part de I, II, III, IIII, là on se dit que cela devient délicat et on introduit un nouveau chiffre V que l'on note à gauche… Certains se demandent comment avec un système aussi baroque et inefficace, les romains ont pu faire tant de réalisations !

Canonique, nique, nique

Continuons sur la thématique leibnizienne. On apprend à l'école les « fractions » : ½, ¾, etc. On apprend également que 1/2 = 2/4. Ces deux fractions sont pourtant distinguables : la première commence par le chiffre 1 et la seconde par le chiffre 2 ! De même que nous avions pris la convention d'ignorer les chiffres initiaux (0001 = 1), nous prenons ici la convention de ne comparer les fractions par numérateur et dénominateur qu'une fois la fraction « réduite ». De même qu'il est inhabituel d'écrire 000001 quand on veut écrire 1, il est inhabituel d'écrire 2/4 au lieu de 1/2 : la seconde forme est « canonique », et l'égalité au sens usuel coïncide avec l'égalité syntaxique à condition de comparer les formes canoniques. Voilà une idée importante… Car, finalement, si nous prenons une définition « algorithmique » et non plus axiomatique de l'addition, ce que nous faisons pour établir que 2+4=6, c'est d'exécuter le calcul 2+4 jusqu'à ce que celui-ci termine sur un résultat (qui joue le rôle de « forme canonique »), soit ici 6, et constater que ce qui est à gauche et à droite du signe égal sont syntaxiquement identiques.

Deux remarques importantes découlent de cet exemple :

  1. C'est beaucoup plus simple de raisonner sur des classes d'objets que l'on voudrait ne pas distinguer (p.ex. les entiers 0001, 001, 1, les fractions ½, 2/4, 3/6…) quand on a des formes canoniques, encore plus si celles-ci s'obtiennent par application d'un algorithme.

  2. Le rôle joué par les axiomes peut parfois être rempli par un calcul, qui apporte l'effectivité.

Le point 2 est l'axe du petit livre de Gilles Dowek, Les métamorphoses du calcul, déjà discuté sur ce blog et qui reçut le Grand prix de philosophie de l'Académie française en 2007. Dans ce livre, Gilles Dowek explique que les versions « effectives » de divers concepts mathématiques ont été éclipsés dans le discours (mais pas dans les faits) par des versions « axiomatiques », car ce qui est effectif est ce qui est utilisé en pratique (peu noble car associé à des métiers manuels ou financiers), tandis que ce qui est axiomatique relève de la recherche de la vérité intellectuelle, de la philosophie. Gilles Dowek développera ses idées sur la dévalorisation de tout ce qui est lié au travail (domaine des gens mécaniques) par rapport au domaine des clercs dans Ces préjugés qui nous encombrent.

Quelques réflexions sur l'intelligibilité

(À destination des esprits chagrins : ceci n'est pas un article de didactique des mathématiques destiné à une revue scientifique, et je ne prétends ni enseigner celle-ci, ni découvrir des choses nouvelles en la matière, ni me faire inviter dans les médias à en parler comme si je disais des choses spécialement profondes.)

Des faits qui nous paraissent parfaitement objectifs, indiscutables et « plats » ne le sont que parce que nous les avons appris comme automatismes dans l'enfance. Dans l'évidence que 12+36=48, il y a l'intériorisation du système de notation positionnel décimal (qui, je pense, aurait surpris un romain même lettré) et d'une notion de calcul.

De nombreux élèves qui comprenaient à l'école primaire les algorithmes d'addition, soustraction, multiplication, perdent pied en mathématiques au collège quand on se met à manipuler des x et des y. Dire que x(x+y)=x²+xy leur semble bien mystérieux ; pourtant les mêmes ne penseraient souvent pas à distinguer 2+4 de 4+2. Simplement, le fait de parler non pas en termes de chiffres concrets mais en termes d'inconnues représentant n'importe quel nombre les dépasse. Là encore, il y a un saut conceptuel… mais de la même façon qu'il y a un saut entre compter sur ses doigts en unaire et compter avec un système à notation positionnelle.

Quelques réflexions sur la preuve mathématique

Nous l'avons vu, il y a énormément de non-dits dans les mathématiques du quotidien et même les mathématiques des professionnels. Dans la simple utilisation des fractions, étudiées à l'école primaire, il y a des moments où nous choisissons d'identifier 1/2 et 2/4, d'autres où nous parlons « du numérateur » comme s'il était unique, nous expliquons parfois que nous ne prenons en compte que des fractions réduites, mais nous ne nous gênons pas pour écrire 2/4=1/2 alors que la fraction de gauche n'est pas réduite…


Dans les mathématiques des professionnels (j'entends ici : les gens qui rédigent des preuves mathématiques, qu'ils travaillent en mathématiques pures, appliquées, en informatique théorique, en physique théorique, en économie ou en toute autre discipline), il y a aussi énormément de non-dits, de raisonnements à une équivalence près que l'on n'explicitera pas, de méta-raisonnements (« tout mon raisonnement précédent ne dépend pas de..., donc il s'appliquera aussi bien à... »). Ces étapes sont souvent celles qui sont pénibles lorsque l'on tente de rédiger des preuves absolument rigoureuses, tellement détaillées que leur correction peut être vérifiée par une machine (par exemple à l'aide de l'outil Coq).

Une question au lecteur

Pensez-vous qu'il y aurait un marché (intellectuel, pas commercial) pour un « la logique mathématique et le théorème d'incomplétude de Gödel expliqués aux non-mathématiciens » ?


Hurt me plenty

Les jeux vidéo offrent souvent plusieurs niveaux de difficulté. J'aimerais donc conclure par quelques questions pour mes lecteurs qui trouvent que je suis vraiment trop trivial :

  • Quel est l'intérêt de la théorie homotopique des types et de l'axiome d'univalence ? Qu'est-ce que cela va changer à la vie de la personne qui essaye concrètement de prouver des choses en Coq et qui se retrouve à faire des setoïdes voire à ne pas arriver à raisonner parce que Coq ne voit pas que deux trucs moralement égaux le sont vraiment ?
  • Commenter sur l'intérêt et les inconvénients pratiques de proof irrelevance et de l'axiome K de Streicher, au delà des quelques remarques du blog Cocorico.

I'm too young to die

Je serai curieux de lire les remarques ou questions de non spécialistes ! Ne vous laissez pas intimider par la bande de normaliens coqueurs.