Théorème d'indéfinissabilité de Tarski

Théorème d'indéfinissabilité de Tarski (Redirigé à partir du théorème d'indéfinissabilité de Tarski) Aller à la navigation Aller à la recherche Théorème d'indéfinissabilité de Tarski, affirmé et prouvé par Alfred Tarski dans 1933, est un résultat limitatif important en logique mathématique, les fondements des mathématiques, et en sémantique formelle. Informellement, le théorème déclare que la vérité arithmétique ne peut pas être définie en arithmétique.

Le théorème s'applique plus généralement à tout système formel suffisamment fort, montrant que la vérité dans le modèle standard du système ne peut pas être définie à l'intérieur du système.

Contenu 1 Histoire 2 Déclaration 3 Forme générale 4 Discussion 5 Voir également 6 Historique des références dans 1931, Kurt Gödel a publié les théorèmes d'incomplétude, qu'il a prouvé en partie en montrant comment représenter la syntaxe de la logique formelle dans l'arithmétique du premier ordre. Chaque expression du langage formel de l'arithmétique se voit attribuer un numéro distinct. Cette procédure est connue sous le nom de numérotation de Gödel, codage et, plus généralement, sous forme d'arithmétisation. En particulier, divers ensembles d'expressions sont codés comme des ensembles de nombres. Pour diverses propriétés syntaxiques (comme étant une formule, étant une phrase, etc.), ces ensembles sont calculables. En outre, tout ensemble calculable de nombres peut être défini par une formule arithmétique. Par exemple, il existe des formules dans le langage de l'arithmétique définissant l'ensemble des codes pour les phrases arithmétiques, et pour les phrases arithmétiques prouvables.

Le théorème d'indéfinissabilité montre que cet encodage ne peut pas être fait pour des concepts sémantiques tels que la vérité. Il montre qu'aucun langage interprété suffisamment riche ne peut représenter sa propre sémantique. Un corollaire est que tout métalangage capable d'exprimer la sémantique d'un langage objet doit avoir un pouvoir expressif supérieur à celui du langage objet. Le métalangage comprend des notions primitives, axiomes, et règles absentes du langage objet, de sorte qu'il y a des théorèmes prouvables dans le métalangage non prouvables dans le langage objet.

Le théorème d'indéfinissabilité est classiquement attribué à Alfred Tarski. Gödel a également découvert le théorème d'indéfinissabilité dans 1930, tout en démontrant ses théorèmes d'incomplétude publiés dans 1931, et bien avant le 1933 publication de l'oeuvre de Tarski (Murawski 1998). Alors que Gödel n'a jamais rien publié concernant sa découverte indépendante de l'indéfinissabilité, il l'a décrit dans un 1931 lettre à John von Neumann. Tarski avait obtenu presque tous les résultats de son 1933 monographie "Le concept de vérité dans les langages des sciences déductives" entre 1929 et 1931, et en a parlé au public polonais. Cependant, comme il le souligne dans le journal, le théorème d'indéfinissabilité était le seul résultat qu'il n'avait pas obtenu auparavant. D'après la note de bas de page du théorème d'indéfinissabilité (Théorème I.) de la 1933 monographie, le théorème et l'esquisse de la preuve n'ont été ajoutés à la monographie qu'après l'envoi du manuscrit à l'imprimeur en 1931. Tarski y rapporte que, lorsqu'il a présenté le contenu de sa monographie à l'Académie des sciences de Varsovie en mars 21, 1931, il n'a exprimé à cet endroit que quelques conjectures, basé en partie sur ses propres recherches et en partie sur le bref rapport de Gödel sur les théorèmes d'incomplétude "Quelques résultats métamathématiques sur la précision et la cohérence des décisions" [Quelques résultats métamathématiques sur la précision de la décision et la cohérence], Académie autrichienne des sciences, Vienna, 1930.

Statement We will first state a simplified version of Tarski's theorem, puis énoncez et prouvez dans la section suivante le théorème que Tarski a démontré dans 1933.

Soit L le langage de l'arithmétique du premier ordre. C'est la théorie des nombres naturels, y compris leur addition et leur multiplication, axiomatisé par les axiomes de Peano du premier ordre. C'est un "Premier ordre" la théorie: les quantificateurs s'étendent sur des nombres naturels, mais pas sur des ensembles ou des fonctions de nombres naturels. La théorie est suffisamment solide pour décrire des fonctions entières définies de manière récursive telles que l'exponentiation, les factorielles ou la suite de Fibonacci.

Soit N la structure standard de L, c'est à dire. N se compose de l'ensemble ordinaire des nombres naturels et de leur addition et multiplication. Chaque phrase de L peut être interprétée en N et devient alors vraie ou fausse. Ainsi (L, N) est le "langage interprété du premier ordre de l'arithmétique".

Chaque formule φ dans L a un nombre de Gödel g(Phi). C'est un nombre naturel qui "encode" Phi. De cette façon, le langage L peut parler de formules en L, pas seulement des chiffres. Soit T l'ensemble des L-phrases vraies dans N, et T* l'ensemble des nombres de Gödel des phrases de T. Le théorème suivant répond à la question: T* peut-il être défini par une formule d'arithmétique du premier ordre?

Théorème d'indéfinissabilité de Tarski: Il n'y a pas de formule L Vrai(n) qui définit T*. C'est-à-dire, il n'y a pas de formule L Vrai(n) tel que pour chaque L-phrase A, Vrai(g(UN)) ↔ A tient dans N.

Informellement, le théorème dit que le concept de vérité des énoncés arithmétiques du premier ordre ne peut pas être défini par une formule en arithmétique du premier ordre. Cela implique une limitation majeure de la portée de "représentation de soi". Il est possible de définir une formule True(n) dont l'extension est T*, mais seulement en puisant dans un métalangage dont la puissance expressive dépasse celle de L. Par exemple, un prédicat de vérité pour l'arithmétique du premier ordre peut être défini en arithmétique du second ordre. Cependant, cette formule ne pourrait définir un prédicat de vérité que pour les formules dans la langue d'origine L. Définir un prédicat de vérité pour le métalangage nécessiterait un métamétalangage encore plus élevé, etc.

Pour prouver le théorème, on procède par contradiction et on suppose qu'une L-formule Vraie(n) existe qui est vrai pour l'entier naturel n dans N si et seulement si n est le nombre de Gödel d'une phrase dans L qui est vrai dans N. Nous pourrions alors utiliser True(n) pour définir une nouvelle formule L S(m) ce qui est vrai pour l'entier naturel m si et seulement si m est le nombre de Gödel d'une formule φ(X) (avec une variable libre x) tel que φ(m) est faux lorsqu'il est interprété dans N (c'est à dire. la formule φ(X), lorsqu'il est appliqué à son propre nombre de Gödel, donne une fausse déclaration). Si l'on considère maintenant le nombre de Gödel g de la formule S(m), et demandez si la phrase S(g) est vrai dans N, on obtient une contradiction. (C'est ce qu'on appelle un argument diagonal.) Le théorème est un corollaire du théorème de Post sur la hiérarchie arithmétique, prouvé quelques années après Tarski (1933). Une preuve sémantique du théorème de Tarski à partir du théorème de Post est obtenue par reductio ad absurdum comme suit. En supposant que T* est définissable arithmétiquement, il existe un entier naturel n tel que T* soit définissable par une formule au niveau {style d'affichage Sigma _{n}^{0}} de la hiérarchie arithmétique. Cependant, T* est {style d'affichage Sigma _{k}^{0}} -dur pour tous k. Ainsi la hiérarchie arithmétique s'effondre au niveau n, contredire le théorème de Post.

General form Tarski proved a stronger theorem than the one stated above, en utilisant une méthode entièrement syntaxique. Le théorème résultant s'applique à tout langage formel avec négation, et avec une capacité suffisante pour l'auto-référence que le lemme diagonal détient. L'arithmétique du premier ordre satisfait ces conditions préalables, mais le théorème s'applique à des systèmes formels beaucoup plus généraux, comme ZFC.

Théorème d'indéfinissabilité de Tarski (Forme générale): Laisser (L,N) être tout langage formel interprété qui inclut la négation et a une numérotation de Gödel g(Phi) satisfaisant le lemme diagonal, c'est à dire. pour chaque formule L B(X) (avec une variable libre x) il existe une phrase A telle que A ↔ B(g(UN)) tient en N. Alors il n'y a pas de formule L Vrai(n) avec la propriété suivante: pour chaque phrase L A, Vrai(g(UN)) ↔ A est vrai dans N.

La preuve du théorème d'indéfinissabilité de Tarski sous cette forme est à nouveau par reductio ad absurdum. Supposons qu'une formule L Vrai(n) comme ci-dessus existait, c'est à dire., si A est une phrase arithmétique, alors Vrai(g(UN)) tient dans N si et seulement si A tient dans N. Donc pour tout A, la formule vrai(g(UN)) ↔ A tient dans N. Mais le lemme diagonal donne un contre-exemple à cette équivalence, en donnant un "menteur" formule S telle que S ↔ ¬Vrai(g(S)) tient en N. C'est un contresens. EST.

Discussion The formal machinery of the proof given above is wholly elementary except for the diagonalization which the diagonal lemma requires. La preuve du lemme diagonal est également étonnamment simple; par exemple, il n'invoque aucunement les fonctions récursives. La preuve suppose que chaque formule L a un nombre de Gödel, mais les spécificités d'une méthode de codage ne sont pas requises. Par conséquent, le théorème de Tarski est beaucoup plus facile à motiver et à prouver que les théorèmes plus célèbres de Gödel sur les propriétés métamathématiques de l'arithmétique du premier ordre..

Smullyan (1991, 2001) a soutenu avec force que le théorème d'indéfinissabilité de Tarski mérite une grande partie de l'attention suscitée par les théorèmes d'incomplétude de Gödel. Que ces derniers théorèmes ont beaucoup à dire sur toutes les mathématiques et plus controversé, sur une série de questions philosophiques (par exemple., Lucas 1961) est moins qu'évident. Théorème de Tarski, d'autre part, ne concerne pas directement les mathématiques mais les limites inhérentes à tout langage formel suffisamment expressif pour présenter un réel intérêt. De tels langages sont nécessairement capables d'une auto-référence suffisante pour que le lemme diagonal s'applique à eux.. La portée philosophique plus large du théorème de Tarski est plus frappante.

Un langage interprété est fortement-sémantiquement-auto-représentatif précisément lorsque le langage contient des prédicats et des symboles de fonction définissant tous les concepts sémantiques propres au langage. Par conséquent, les fonctions requises incluent la "fonction d'évaluation sémantique" mapper une formule A à sa valeur de vérité ||UN||, et le "fonction de dénotation sémantique" mapper un terme t à l'objet qu'il désigne. Le théorème de Tarski se généralise alors comme suit: Aucun langage suffisamment puissant n'est fortement sémantiquement auto-représentatif.

Le théorème d'indéfinissabilité n'empêche pas la vérité dans une théorie d'être définie dans une théorie plus forte. Par exemple, l'ensemble des (codes pour) formules de l'arithmétique de Peano du premier ordre qui sont vraies dans N est définissable par une formule de l'arithmétique du second ordre. De la même manière, l'ensemble des vraies formules du modèle standard de l'arithmétique du second ordre (ou arithmétique d'ordre n pour tout n) peut être défini par une formule en ZFC du premier ordre.

See also Gödel's incompleteness theorems – Limitative results in mathematical logic References J. L. Cloche, et M. Machover, 1977. Un cours de logique mathématique. Hollande du Nord. g. Boolos, J. Bourgeois, et R. Jeffrey, 2002. Calculabilité et logique, 4e ed. la presse de l'Universite de Cambridge. J. R. Lucas, 1961. "Dérange, Machines, et Godel". Philosophie 36: 112–27. R. Murawski, 1998. Indéfinissabilité de la vérité. Le problème de la priorité: Tarski contre. Gödel. Histoire et philosophie de la logique 19, 153–160 R. Smullyan, 1991. Théorèmes d'incomplétude de Godel. Université d'Oxford. Presse. R. Smullyan, 2001. "Théorèmes d'incomplétude de Gödel". En L. Goble, éd., Le guide Blackwell de la logique philosophique, Blackwell, 72–89. UN. Tarski, 1933. Le concept de vérité dans les langues des sciences de l'éducation. Publié par la Société Scientifique de Varsovie. UN. Tarski (1936). "Le concept de vérité dans les langages formalisés" (PDF). Etudes philosophiques. 1: 261–405. Archivé de l'original (PDF) sur 9 Janvier 2014. Récupéré 26 Juin 2013. UN. Tarski, tr. J. H. Woodger, 1983. "Le concept de vérité dans les langages formalisés". Traduction anglaise de Tarski 1936 article. Dans un. Tarski, éd. J. corcoran, 1983, Logique, Sémantique, Métamathématiques, Hacket. show vte Métalogique et métamathématique show vte Vérité show vte Logique mathématique Catégories: Logique mathématiqueMétathéorèmesPhilosophie de la logiqueThéorèmes des fondements des mathématiquesThéories de la vérité