Théorème d'incomplétude de Tarski

Le théorème de Tarski, ou théorème de non définissabilité de Tarski, peut s'énoncer informellement ainsi : on ne peut définir dans le langage de l'arithmétique la vérité des énoncés de ce langage.

Définir un ensemble de nombres entiers dans le langage de l'arithmétique, c'est trouver une formule de ce langage à une variable libre qui n'est vérifiée que par les entiers de cet ensemble. Par exemple la formule il existe un y tel que x = y+y, qui a pour seule variable libre x, définit l'ensemble des entiers pairs. Cette définition fait référence à la vérité dans N : les nombres entiers positifs.

On suppose que le langage est récursif : ce qui est le cas quand les symboles primitifs, « 0, s, +, ×, ≤ » pour l'arithmétique de Peano, sont en nombre fini. Sans entrer dans le détail, les langages des théories que l'on utilise habituellement en mathématique sont récursifs.

Le théorème s'appuie sur les travaux de Gödel, qui, pour la preuve de ses théorèmes d'incomplétude, montre que l'on peut coder les formules par des nombres entiers. L'ensemble des entiers qui sont des codes de formules, comme l'ensemble des entiers qui sont des codes d'énoncés (formules closes, sans variables libre) se définissent dans l'arithmétique.

Le théorème de Tarski énonce précisément que, quel que soit le codage choisi,

l'ensemble des codes des énoncés d'un certain langage pour l'arithmétique qui sont vrais dans N n'est pas définissable dans N par une formule de ce même langage.

Alfred Tarski a énoncé et démontré ce théorème dans un article paru en polonais en 1933, puis traduit en allemand en 1936, qui est connu pour être le premier article à proposer des formalisations de la notion de vérité en mathématiques^[1]. Il semble cependant que Gödel, lors de ses recherches sur les théorèmes d'incomplétude, ait démontré ce théorème, dont la preuve est très semblable à celle de son premier théorème d'incomplétude tout en étant techniquement plus simple. Il l'a mentionné dans une lettre adressée à John von Neumann en 1931, selon une lettre ultérieure de Gödel lui-même. Il ajoutait qu'il tenait ce théorème pour « la vraie raison de l'existence d'énoncés indécidables dans les systèmes formels contenant l'arithmétique »^[2]. Gödel se serait refusé à parler de vérité dans son article de 1931, la notion à l'époque étant controversée.

Le théorème se généralise à tout langage récursif qui permet de définir le langage de l'arithmétique de Peano.

L'ensemble des énoncés vrais

L’ensemble des énoncés d'un langage, vrais dans un modèle, est défini par induction sur la structure des formules (voir théorie des modèles). Ici, on s'intéresse aux énoncés du langage vrais dans N. On peut donc définir mathématiquement cet ensemble, mais pour cela il faut une théorie dans un langage plus riche que celui d'origine. Par exemple on peut définir la vérité dans N en théorie des ensembles, ou plus simplement, en arithmétique du second ordre. Alfred Tarski parle d'un méta-langage, qui doit être nécessairement plus riche que le langage objet.

On peut remarquer que dans un langage dénombrable, on ne pourra jamais définir qu'un ensemble dénombrable de sous-ensembles de N, c'est l'argument essentiel pour le théorème de Löwenheim-Skolem. Or d'après un résultat bien connu de Cantor, l'ensemble des sous-ensembles de N n'est pas dénombrable. On sait donc que tous les sous-ensembles de N ne peuvent être définissables.

La preuve du théorème

Comme la preuve du premier théorème d'incomplétude de Gödel, celle du théorème de Tarski utilise un argument diagonal qui fait apparaître un énoncé similaire au paradoxe du menteur.

Le codage des formules peut se faire de la même façon que pour le théorème d'incomplétude de Gödel. On note ⌈F⌉ le code d'une formule F du langage ; ⌈F⌉ est donc un entier.

Tarski suppose, en vue d'obtenir une contradiction, l'existence d’une formule de l'arithmétique à une variable libre V(x) qui définit la vérité, c'est-à-dire que l'équivalence suivante :

A ⇔ V(⌈A⌉)

doit être vérifiée dans N pour tout énoncé A.

Par une diagonalisation identique à celle utilisée pour le premier théorème d'incomplétude de Gödel (en utilisant le prédicat de substitution), on obtient un énoncé D (qui dépend de V), et telle que l'équivalence suivante soit satisfaite dans N :

D ⇔ ¬V(⌈D⌉)          (le signe ¬ signifie la négation).

L'énoncé D affirme de lui-même qu'il est faux, c'est donc bien une formalisation du paradoxe du menteur. On aboutit à une contradiction, puisque, comme V est censée définir la vérité, on doit aussi avoir :

D ⇔ V(⌈D⌉).

On a obtenu l'énoncé D par diagonalisation à partir d'une formule arbitraire V là où, pour son théorème, Gödel utilise une formule qu'il a construite auparavant pour représenter la prouvabilité dans la théorie considérée.

Sources

• Raymond Smullyan, Les théorèmes d'incomplétude de Gödel, Dunod, 2000 (ISBN 210005287X)

Notes et références

• Portail des mathématiques