Teorema da indefinibilidade de Tarski

Teorema da indefinibilidade de Tarski, declarado e provado por Alfred Tarski em 1936, é um importante resultado limitativo em lógica matemática , os fundamentos da matemática, e em semântica formal. Informalmente, o teorema afirma que a verdade aritmética não pode ser definida em aritmética.

O teorema se aplica de forma mais geral a qualquer sistema formal suficientemente forte, mostrando que a verdade no modelo padrão do sistema não pode ser definido dentro do sistema.

História

Em 1931, Kurt Gödel publicou o seu famoso teorema da incompletude, que ele provou em parte, mostrando como representar sintaxe em aritmética de primeira ordem. Para cada expressão da linguagem aritmética é atribuído um número distinto. Esse procedimento também é conhecido como numeração Gödel , codificação, ou mais genericamente aritmetização. Em particular, vários conjuntos de expressões são codificadas como um conjunto de números. Acontece que por várias propriedades sintáticas (como ser uma formula, ser uma sentença, etc.), esses conjuntos são computáveis. Além disso, qualquer conjunto computável de números pode ser definido por uma fórmula aritmética. Por exemplo, existem fórmulas na linguagem da aritmética que definem o conjunto de códigos para sentenças aritméticas e para sentenças aritméticas demonstráveis.

O teorema da indefinibilidade mostra que esta codificação não pode ser feita por conceitos semânticos como verdade. Isso mostra que nenhuma linguagem suficientemente rica pode representar a sua própria semântica. Um corolário é que qualquer metalinguagem capaz de expressar a semântica de alguma linguagem objeto deve ter poder expressivo superior ao da linguagem objeto. A metalinguagem inclui noções primitivas, axiomas e regras ausentes da linguagem objeto, de modo que há teoremas demonstráveis na metalinguagem não demonstráveis na linguagem objeto.

O teorema de indefinibilidade é convencionalmente atribuído a Alfred Tarski. Gödel também descobriu o teorema da indefinibilidade em 1930, enquanto provava seus teoremas da incompletude publicados em 1931, e bem antes da publicação em 1936 da obra de Tarski (Murawski 1998). Enquanto Gödel nunca publicou nada tendo a sua descoberta independente de indefinibilidade , ele o descreveu em uma carta de 1931 a John von Neumann. Tarski tinha obtido quase todos os resultados de seu artigo de 1936 Der Wahrheitsbegriff em den formalisierten Sprachen entre 1929 e 1931, e falou sobre eles para o público polonês. No entanto, como ele enfatizou no papel, o teorema da indefinibilidade era o único resultado não obtido por ele mais cedo. De acordo com a nota do teorema da indefinibilidade (Satz I) do artigo de 1936, o teorema e o esboço da prova foram adicionados ao papel somente depois que o documento foi enviado para impressão. Quando ele apresentou o documento para a Academia de Varsóvia de Ciências em 21 de março de 1931, ele escreveu apenas algumas conjecturas, em vez dos resultados de suas próprias investigações e , em parte, depois de breve relatório de Gödel sobre os teoremas da incompletude " Einige metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit " , AKD . der Wiss . em Wien, 1930.

Demonstração do teorema

Vamos primeiro demonstrar uma versão simplificada do teorema de Tarski, em seguida, demonstrar e provar na próxima seção o teorema que Tarski realmente provou em 1936. Seja L a linguagem da aritmética de primeira ordem, e seja N o estrutura padrão para L. Assim, ( L, N) é a "linguagem de primeira ordem da aritmética interpretada". Cada sentença x em L tem um número de Gödel g (x). T denota o conjunto de L-sentenças verdadeiras em N, e T * o conjunto de números de Gödel de sentenças em T. O seguinte teorema responde à pergunta: Pode T * ser definido por uma fórmula da aritmética de primeira ordem?

Teorema da indefinibilidade de Tarski: Não há L-formula True(n) que defina T*. Isso é, não há L-formula True(n)que para toda L-formula A, True(g(A)) ↔ A .

Informalmente, o teorema diz que dada uma aritmética formal, o conceito de verdade nessa aritmética não é definível usando os meios expressivos que essa aritmética proporciona. Isto implica uma grande limitação no âmbito da "auto-representação" É possível definir uma formula True(n) cuja extensão é T*, mas apenas transcrevendo em uma metalinguagem cujo poder expressivo vai além do poder de L. Por exemplo, um predicado verdade para aritmética de primeira ordem pode ser definido na aritmética de segunda ordem . entretanto, esta formula só poderia ser capaz de definir um predicado verdade para sentenças na linguagem original L. Para definir um predicado verdade para a meta linguagem exigiria uma "metametalinguagem" ainda maior, e assim em diante.

O teorema demonstrado é um corolário do Teorema de Post sobre a Hierarquia aritmética, provado alguns anos após Tarski (1936). A prova semântica do teorema de Tarski a partir do teorema de Post é obtida por reductio ad absurdum. Suponde T* é aritmeticamente definível, há um número natural n tal que T* é definível através de uma fórmula de grau $\Sigma _{n}^{0}$ da Hierarquia aritmética. Contudo, T* é $\Sigma _{k}^{0}$ - difícil para todo k. Assim, a hierarquia aritmética cai a nível n, contradizendo o teorema de Post.

Forma geral do teorema

Tarski provou um teorema mais forte que o demonstrado acima, usando um método inteiramente sintático. O teorema resultante se aplica to a qualquer linguagem formal com negação, e com capacidade suficiente para auto-representação que o lema diagonal detém. aritmética de primeira ordem satisfaz essas precondições, mas o teorema se aplica a muito mais sistemas gerais formais.

Teorema da indefinibilidade de Tarski (Forma geral): Seja (L,N) qualquer linguagem formal que inclua a negação e que tenha uma numeração de Gödelg(x) tal que para toda L-formula A(x) existe uma formula B tal que B ↔ A(g(B)). seja T* o conjunto de números de Gödel de L-sentenças verdadeiras em N. Então não existe formula L Verdade(n) que define T*. Isso é, Não existe formula L Verdade(n) tal que para toda formula L A, Verdade(g(A)) ↔ A se mantém.

A prova do teorema da indefinibilidade de Tarski nesta forma é feita novamente por reductio ad absurdum. Suponha que uma formula L Verdadeira(n) define T*. Em particular, se A é uma sentença da aritmética então Verdade(g(A)) se mantém em N se somente se A é verdade em N. Assim para todo A, A sentença T de Tarski True(g(A)) ↔ A é verdade em N. Mas o lema diagonal produz um contraexemplo para essa equivalência, dando uma sentença "Mentirosa" S tal que S ↔ ¬Verdade(g(S)) se mantém. Assim nenhuma formula L verdade( n) pode definir T *. CQD.

O mecanismo formal desta prova é totalmente elementar, exceto para a diagonalização que o lema da diagonal requer. A prova do lema da diagonal é também surpreendentemente simples, por exemplo, ele não invoca funções recursivas de nenhuma forma. A prova assume que cada fórmula L tem um número de Gödel, mas as especificidades de um método de codificação não são necessários. Daí o teorema de Tarski é muito mais fácil para motivar e provar que o mais célebre teoremas de Gödel sobre as propriedades metamatemáticas da aritmética de primeira ordem.

Discussão

Smullyan (1991, 2001) argumentou vigorosamente que o teorema da indefinibilidade de Tarski merece muita da atenção que o teorema da incompletude de Gödel recebeu. Que os últimos teoremas têm muito a dizer sobre toda a matemática e mais controversa, sobre uma série de questões filosóficas (por exemplo, Lucas 1961) é menos do que evidente. O Teorema de Tarski, por outro lado, não é diretamente sobre a matemática, mas sobre as limitações inerentes de qualquer linguagem formal suficientemente expressiva para ser de interesse real. Tais linguagens são necessariamente capazes de o suficiente autorreferência para o lema diagonal se aplicar a elas. A ampla importância filosófica do teorema de Tarski é mais claramente evidente.

Uma linguagem interpretada é fortemente semanticamente auto-representativa exatamente quando a linguagem contém predicados e símbolos de função definindo todos os conceitos semânticos específicos para a linguagem. Daí as funções necessárias incluem a "função de avaliação semântica" mapeando de uma fórmula A à sua valoração verdade || A||, e a "função denotação semântica" mapeando um termo t ao objeto que ele denota. Teorema de Tarski, em seguida, generaliza o seguinte: Nenhuma linguagem suficientemente poderosa é fortemente semanticamente auto-representativa.

O teorema da indefinibilidade não previne a verdade em uma teoria de ser definida em uma teoria mais forte.Por exemplo, o conjunto(Códigos para) formulas da aritmética de Peano de primeira ordem que são verdade em N são definíveis por uma formula na aritmética de segunda ordem. Similarmente, O conjunto de formulas verdadeiras do modelo padrão da aritmética de segunda ordem pode ser definida pela formula na primeira ordem Axiomas de Zermelo-Fraenkel.

Referências

J.L. Bell, and M. Machover, 1977. A Course in Mathematical Logic. North-Holland.
G. Boolos, J. Burgess, and R. Jeffrey, 2002. Computability and Logic, 4th ed. Cambridge University Press.
J.R. Lucas, 1961. "Mind, Machines, and Gödel". Philosophy 36: 112-27.
R. Murawski, 1998. Undefinability of truth. The problem of the priority: Tarski vs. Gödel. History and Philosophy of Logic 19, 153-160
R. Smullyan, 1991. Godel's Incompleteness Theorems. Oxford Univ. Press.
R. Smullyan, 2001. "Gödel’s Incompleteness Theorems". In L. Goble, ed., The Blackwell Guide to Philosophical Logic, Blackwell, 72-89.
A. Tarski (1936). «Der Wahrheitsbegriff in den formalisierten Sprachen» (PDF). Studia Philosophica. 1: 261–405. Consultado em 26 de junho de 2013. Arquivado do original (PDF) em 9 de janeiro de 2014
A. Tarski, tr J.H. Woodger, 1983. "The Concept of Truth in Formalized Languages". English translation of Tarski's 1936 article. In A. Tarski, ed. J. Corcoran, 1983, Logic, Semantics, Metamathematics, Hackett.