Théorème d'incomplétude de Tarski
Le théorème d'incomplétude de Tarski dit qu’une théorie mathématique suffisamment riche ne permet jamais de définir un prédicat de vérité pour elle-même.
Les conditions du théorème, qui seront exposées plus loin, disent avec précision ce qu'il faut entendre par théorie mathématique suffisamment riche dans le cas présent.
| Sommaire |
Les prédicats de vérité
La représentation des formules et la numérotation gödelienne
La notion de prédicat de vérité repose sur 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. Kurt 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. Cette technique permet de produire des énoncés paradoxaux semblables à celui du menteur. L'existence de ces énoncés est au cœur de toutes les preuves des théorèmes d'incomplétude.
L'ensemble des vérités
Si une théorie a un modèle, l’ensemble de toutes ses formules vraies dans ce modèle 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.
Les prédicats de vérité
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, appelé prédicat de vérité, est impossible.
L'incomplétude ontologique
L'inexistence d'un prédicat de vérité est une 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 mais il ne peut pas exister à l’intérieur de ces théories.
Les conditions du théorème
Dans la suite, le théorème est énoncé 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 l’énonce avec les nombres, ce théorème est plus facile à comprendre mais il est aussi plus difficile de prouver que les théories mathématiques générales satisfont à ses conditions. Celles-ci 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 les 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 la 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.
La preuve du théorème
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 que 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 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. Si les conditions c ou d notamment ne sont pas remplies alors un prédicat de vérité peut exister.