Aujourd’hui, c’est le 1er avril, jour des menteurs, et du coup parlons du paradoxe du menteur ! Pourquoi dire que l’on est en train de ne pas dire la vérité pose problème…

Ce sera l’occasion de parler d’un des plus grands logiciens du 20e siècle, Alfred Tarski, et de ses travaux sur la vérité ; et aussi d’un des résultats les plus importants en logique mathématique : le théorème d’incomplétude de Gödel. Et quand on croise Tarski et le théorème d’incomplétude, on obtient le théorème d’indéfinissabilité de Tarski. Et c’est chouette, si, si.

Concernant le « Diagonalization lemma » (ou « diagonal lemma »)

Le « Diagonalization lemma » (je ne l’écrit pas en français car il ne semble pas qu’il soit d’usage de s’y référer ainsi, et cela pourrait créer une confusion avec l’argument de la diagonale de Cantor) est une étape cruciale dans la preuve de Gödel pour montrer en quoi son codage permet de construire des formules auto-référentielles. Vous trouverez la preuve de ce lemme sur Wikipedia ou sur la Stanford Encyclopedia of philosophy, mais la plus claire explication que j’en ai lue se trouve dans un bref papier de Richard Heck dénué de tout symbole logique ; je ne saurais trop vous en recommander la lecture si vous voulez vraiment comprendre ce lemme.

L’exposition du lemme dans ce papier est informelle (au sens où elle s’applique à un langage naturel plutôt qu’à un langage formel) mais elle n’en est pas moins parfaitement rigoureuse sur le plan logique, et cela permet de comprendre bien plus aisément ce qu’exprime ce lemme. Cela permet aussi de comprendre qu’en fin de compte ce lemme n’a rien de proprement arithmétique ; il s’applique à toute théorie satisfaisant ces deux conditions : (1) qu’il y ait dans le langage de la théorie un système permettant à des expressions du langage de référer à des formules du langage ; (2) que l’on puisse exprimer des opérations syntaxiques de substitution dans les formules de ce langage. (Dans le cas de l’arithmétique, (1) est rendu possible par le codage de Gödel et (2) par la quantification.) Le théorème de Tarski dérivant seulement de ce lemme, il est valable pour tout langage satisfaisant (1) et (2) ; donc c’est un résultat plus général que s’il valait seulement pour les systèmes formalisant l’arithmétique.