L'incomplétude mathématique/Les prédicats de vérité et le théorème d’incomplétude de Tarski
Les énoncés paradoxaux sont produits par une technique logique très générale qui consiste à représenter les formules d’une théorie T par des objets de T. C’est possible dès que T contient les nombres entiers positifs parmi ses objets. Gödel et ses successeurs ont inventé des techniques de codage, de numérotation, qui permettent de représenter n’importe quelle formule par un entier, de telle façon que chaque entier représente au plus une formule.
Dans la suite, les théorèmes de Gödel et Tarski sont énoncés avec l’ensemble des nombres entiers positifs, qu’on appellera tout simplement nombres. Mais on pourrait remplacer cet ensemble par n’importe quel autre système formel infini. Quand on les énonce avec les nombres, ces théorèmes sont plus faciles à comprendre mais il est aussi plus difficile de prouver que les théories mathématiques générales satisfont aux conditions des théorèmes. Dans le chapitre suivant, nous prouverons qu’une théorie élémentaire des ensembles satisfait à ces conditions. Mais les formules ne seront pas représentées par des nombres. L’ensemble des noms que nous choisirons se prêtera plus aisément que les nombres à la représentation des formules.
Si une théorie a un modèle, l’ensemble de toutes ses formules vraies est défini sans équivoque. Lorsqu’une théorie est représentée à l’intérieur d’elle-même, l’ensemble de tous les objets qui représentent des formules vraies est lui aussi défini sans équivoque.
Toute théorie vraie permet de définir des ensembles même si elle n’est pas une théorie des ensembles, parce qu’elle permet toujours de définir des prédicats. Par exemple, le prédicat (il existe un y tel que x = y+y) contient x comme unique variable libre, il est donc unaire, et pour l’arithmétique il définit l’ensemble des nombres pairs. Un prédicat définit de même un ensemble de couples s’il est binaire, de triplets s’il est ternaire, et ainsi de suite.
On peut alors se demander si parmi tous les prédicats d’une théorie vraie, il y en a un qui définit l’ensemble de tous les représentants des formules vraies. Tarski a prouvé que sous des conditions générales, l’existence d’un tel prédicat est impossible. C’est une autre manifestation de l’incomplétude ontologique. Une théorie ne permet jamais de définir tous les ensembles qui ont cependant le droit d’exister. L’ensemble de tous les représentants des formules vraies existe d’une façon aussi certaine que tous les ensembles définis avec des moyens élémentaires.
Le théorème de Tarski dit qu’une théorie mathématique vraie et suffisamment riche ne permet jamais de définir un prédicat de vérité pour elle-même. Plus précisément les conditions du théorème sont les suivantes.
a) Une théorie T a suffisamment de moyens d’expression pour qu’elle compte parmi ses objets tous les nombres.
b) Elle est vraie au sens où elle a un modèle et où toutes ses formules arithmétiques vraies, au sens de la théorie des nombres, sont également vraies pour ce modèle.
c) Les opérateurs de la logique du premier ordre (négation, conjonction, existentiation) sont utilisés dans T.
d) Il existe un procédé de codage qui permet de représenter toutes les formules de T par un nombre unique et pour lequel il existe une formule de T, SUBxyz, qui contient trois variables libres, et qui est vraie si et seulement si (x représente une formule p de T avec une variable libre et z représente une formule obtenue par la substitution du nombre y à toutes les occurrences de la variable libre de p).
SUB est un prédicat ternaire de T. x représente n’importe quel prédicat unaire p de T.
On peut déduire de d) que SUB est une relation fonctionnelle de deux variables, au sens où pour tous w, x, y, z, si (SUBxyz et SUBxyw) alors z=w et où pour tous nombres x et y, si x représente un prédicat unaire de T alors il existe un z tel que SUBxyz.
Les conditions a, b, c et d sont très généralement vérifiées pour les théories destinées à fonder les mathématiques. Même l’arithmétique formelle est suffisamment riche pour se représenter ainsi elle-même. Mais la définition du prédicat ternaire SUB est techniquement assez élaborée et ne sera pas exposée ici.
Faisons alors l’hypothèse que T permet de définir un prédicat unaire, c’est-à-dire une formule avec une variable libre, Vx et que Vx est vrai si et seulement si x représente une formule vraie de T. Autrement dit, on suppose que T permet de définir un prédicat de vérité pour T.
Tarski a prouvé que cette hypothèse conduit à une contradiction.
Considérons la formule (il existe un z tel que SUBxxz et non Vz). C’est une formule avec une variable libre que T permet de définir. Elle est donc représentée par un nombre n de T. Il y a aussi un autre nombre AT de T tel que SUBnn(AT). Est-ce qu'AT représente une formule vraie ?
La formule représentée par AT dit que le prédicat représenté par n est vrai pour n. Le prédicat représenté par n est vrai pour x si et seulement s'il existe un z tel que SUBxxz et non Vz. V(AT) est donc équivalent à (il existe un z tel que SUBnnz et non Vz) par définition de AT. De la condition c, on déduit que SUBnnz équivaut à z=(AT). Donc par définition de AT, V(AT) équivaut à non V(AT). C’est une contradiction. Il s’agit bien du paradoxe du menteur, parce que du fait de sa définition la formule représentée par AT dit d’elle-même qu’elle est fausse. Puisque l’hypothèse de l’existence du prédicat de vérité V conduit à une contradiction, elle doit être rejetée. Tel est précisément le théorème d’incomplétude de Tarski.
Une théorie mathématique vraie et suffisamment riche ne permet jamais de définir un prédicat de vérité pour elle-même.
Ou plus précisément.
Une théorie mathématique vraie T, pour laquelle les conditions a, b et c et d sont vérifiées, ne permet jamais de définir une formule à une variable libre qui serait vraie pour toutes les représentations des formules vraies de T et seulement pour elles.
Le théorème de Tarski n’est pas toujours applicable. Le chapitre suivant donnera deux exemples de prédicats de vérité. Le premier est un prédicat de vérité pour la théorie Enum de tous les ensembles énumérables. Son existence est une conséquence du théorème fondamental de l’énumérabilité. Dans ce cas, la condition b du théorème de Tarski n’est pas remplie. L’existence d’un prédicat de vérité pour la théorie Finitaire1 des ensembles finitaires de base pourra être établie avec un modèle non-standard, pour lequel il n’existe pas de prédicat ternaire SUB.
