Théorème de Tarski

Un article de Wikipédia, l'encyclopédie libre.

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.

[modifier] 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.

[modifier] 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 Taski utilise un argument diagonal qui fait apparaître un énoncé similaire au paradoxe du menteur.

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é, alors que Gödel utilise une formule dont il a montré auparavant qu'elle représentait la prouvabilité dans la théorie considérée.

On note ⌈F⌉ le code d'une formule F du langage ; ⌈F⌉ est donc un entier. 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é A vérifiant dans N l'équivalence :

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

c’est-à-dire un énoncé affirmant de lui même qu'il est faux. C'est bien le paradoxe du menteur. Ceci contredit le fait que V définit la vérité pour toutes les formules du langage, et donc en particulier pour A.

[modifier] Sources

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

[modifier] Notes

• Portail des mathématiques