Enfin, j’arrive au bout de cette série sur la démonstration et la connaissance !

Axiomes et règles d’inférence

Un petit mot sur la différence entre axiome (dont on a parlé dans l’épisode sur l’axiomatique) et règle d’inférence. Je n’ai pas assez insisté sur ce point alors qu’il est assez crucial pour bien comprendre le paradoxe de Lewis Carroll.

On peut construire un système déductif sans aucun axiome. Par exemple, la déduction naturelle pour la logique du premier ordre est un système déductif sans axiome (le calcul des séquents aussi, mais c’est un peu plus compliqué à expliquer donc je vais rester sur la déduction naturelle). Le système déductif consiste alors seulement en un ensemble de règles d’inférences. Les règles de la déduction naturelle permettent la construction d’arbres déductifs dont les racines et les noeuds sont des formules du langage, chaque étape de construction étant régi par l’une des règles du système, et certaines applications de ces règles permettant de décharger les formules racines. (Typiquement, si vous avez un arbre dont l’une des racines est « p » et qui aboutit à « q », vous pouvez poursuivre l’arbre en écrivant au noeud suivant « p → q », ce qui décharge la racine « p ».) Lorsqu’un arbre de déduction est construit d’après ces règles, on peut regarder l’ensemble S des formules racines non-déchargées et la formule φ qui est à l’autre extrémité de l’arbre et dire que φ est déductible de S. Si l’ensemble S est vide, c’est-à-dire que toutes les formules de point de départ ont été déchargées, alors φ est un théorème du système. En somme, dans ce genre de système, les théorèmes sont les formules déductibles de l’ensemble vide.

Qu’est-ce donc qu’une axiomatique ? C’est un système déductif dans lequel on trouve non seulement des règles d’inférences (il en faut de toute façon), mais aussi un ensemble de formules du langage que l’on spécifie comme étant des axiomes et pour lesquels on décrète que : les théorèmes sont les formules déductibles des axiomes. Les formules déductibles de l’ensemble vide sont toujours des théorèmes, à plus forte raison, mais cela ajoute un grand nombre d’autres théorèmes, et cela permet de produire des systèmes déductifs très différents et souvent beaucoup plus intéressants.

Par exemple, avec les règles standard de la déduction naturelle appliquées à un langage du premier ordre avec identité, on obtient la logique standard du premier ordre avec identité : c’est une logique cohérente et complète, mais relativement peu expressive (c’est grâce à cela qu’elle est complète). Ajoutez-y les axiomes de ZFC (qui sont tous formulables dans ce langage du premier ordre) et vous avez… la théorie des ensembles ZFC, soit à peu près toutes les mathématiques. Même langage, mêmes règles d’inférences, juste quelques axiomes supplémentaires, mais cela fait une sacrée différence !

Il faut bien comprendre ceci dit que les axiomes de ZFC en eux-mêmes ne prouvent strictement rien ; ce ne sont que des formules d’un langage du premier ordre. Tout ce que l’on déduit de ces axiomes, on le déduit en utilisant les règles d’inférence de la logique du premier ordre. C’est pourquoi il faut des règles d’inférence en plus des axiomes ; il faut des règles d’inférence pour spécifier comment, à partir de tels et tels axiomes, tirer tel ou tel théorème.

En somme, on peut dire que ce que veut la Tortue dans le paradoxe de Lewis Carroll (dans sa version originale), c’est un système qui ne consisterait qu’en axiomes : « Spécifie tous les axiomes que je dois accepter pour être contrainte d’accepter la conclusion. » Or il n’y a pas d’axiomes à ajouter, seulement des règles d’inférence ; et lorsque Achille formule ce qui devrait être compris comme une règle d’inférence, la Tortue l’ajoute au carnet d’Achille comme si c’était un axiome ; et cet ensemble d’axiome ne suffit jamais pour arriver à la conclusion puisque ce qu’il faut, c’est une règle d’inférence : une règle qui nous dise comment tirer une conclusion à partir de ces axiomes.

Dans la version remaniée du paradoxe de Lewis Carroll que je présente dans cette vidéo, je permets à Achille de faire entendre à la Tortue cette distinction entre axiomes et règles d’inférence ; mais à ce moment, on tombe sur le paradoxe d’une hiérarchie infinie de méta-langages. Car si les règles d’inférences des axiomes du carnet de base s’expriment dans un méta-langage, pour comprendre les raisonnements que l’on fait dans le méta-langage il faut accepter qu’il y a des règles d’inférence pour ce méta-langage, lesquelles devraient être exprimées dans un méta-méta-langage… et ainsi putain de suite !

Voilà !