Théorème de Tarski
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être...) de nombres entiers dans le langage de l'arithmétique (L'arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la théorie des groupes. On l'appelle plus généralement la...), c'est trouver une formule de ce langage à une variable (En mathématiques et en logique, une variable est représentée par un symbole. Elle est utilisée pour marquer un rôle dans une formule, un prédicat ou un algorithme. En statistiques, une...) 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 (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) 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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) fini. Sans entrer dans le détail, les langages des théories que l'on utilise habituellement en mathématique (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les transformations. Les mathématiques...) sont récursifs.

Le théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers...) s'appuie sur les travaux de Gödel, qui, pour la preuve de ses théorèmes d'incomplétude (On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématiques qu'il est complet pour exprimer que rien ne peut lui être ajouté, en un sens qu'il faut préciser dans chaque...), 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 (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.) énonce précisément que, quelquesoit le codage (De façon générale un codage permet de passer d'une représentation des données vers une autre.) 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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) en étant techniquement plus simple. Il l'a mentionné dans une lettre adressée à John von Neumann (John von Neumann, mathématicien et physicien américain d'origine hongroise, a apporté d'importantes contributions tant en mécanique quantique, qu'en analyse fonctionnelle, en théorie des...) 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 (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur...) 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 (La théorie des ensembles est une branche des mathématiques créée initialement par le mathématicien allemand Georg Cantor à la fin du XIXe siècle.), ou plus simplement, en arithmétique du second ordre. Alfred Tarski parle d'un meta-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 (Un ensemble E est dit dénombrable s'il est équipotent à l'ensemble des entiers naturels , c'est-à-dire s'il existe une bijection de E sur  ; cela équivaut à l'existence d'une...) de sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi élément du...) de N, c'est l'argument essentiel pour le théorème de Löwenheim-Skolem (Le théorème de Löwenheim-Skolem fait partie de la théorie des modèles. Sa simplicité et sa puissance en font un théorème majeur — avec le théorème de compacité.). 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 Taski utilise un argument diagonal (Dans les preuves mathématiques, notamment celles de logique mathématique, l'argument diagonal est un mécanisme de construction réflexive menant le plus souvent à une impossibilité. Une telle...) qui fait apparaître un énoncé similaire au paradoxe (Un paradoxe est une proposition qui contient ou semble contenir une contradiction logique, ou un raisonnement qui, bien que sans faille apparente, aboutit à une absurdité, ou encore, une situation qui...) du menteur.

Tarski suppose, en vue (La vue est le sens qui permet d'observer et d'analyser l'environnement par la réception et l'interprétation des rayonnements lumineux.) d'obtenir une contradiction (Une contradiction existe lorsque deux affirmations, idées, ou actions s'excluent mutuellement.), 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 diagonalisation (La diagonalisation est un procédé d'algèbre linéaire. Il s'applique à des endomorphismes d'un espace vectoriel. Il consiste à rechercher une base de...), en utilisant le prédicat (Les prédicats d’une théorie sont les formules qui contiennent des variables libres.) de substitution, on obtient un énoncé A vérifiant (le signe ¬ signifie la négation) :

A ⇔ ¬V(⌈A⌉) est vraie dans N

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.

Sources

  • Raymond Smullyan (Raymond Smullyan est un logicien, mathématicien et magicien américain né en 1919.), Les théorèmes d'incomplétude de Gödel - Dunod, 2000 - ISBN 210005287X

Notes

  1. voir l'article de W. Hodges, Tarski's Truth Definitions dans la "Stanford Encyclopedia of Philosophy".
  2. voir Solomon Ferferman, Kurt Gödel: Conviction and Caution (1984), repris dans In the light of Logic (1998).
Page générée en 0.091 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique