Teorema da indefinibilidade de Tarski

Teorema da indefinibilidade de Tarski (Redirecionado do teorema da indefinibilidade de Tarski) Pular para navegação Pular para pesquisar o teorema da indefinibilidade de Tarski, declarado e provado por Alfred Tarski em 1933, é um resultado limitativo importante em lógica matemática, os fundamentos da matematica, e na semântica formal. Informalmente, o teorema afirma que a verdade aritmética não pode ser definida em aritmética.

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

Conteúdo 1 História 2 Declaração 3 Forma geral 4 Discussão 5 Veja também 6 References History In 1931, Kurt Gödel publicou os teoremas da incompletude, que ele provou em parte mostrando como representar a sintaxe da lógica formal dentro da aritmética de primeira ordem. A cada expressão da linguagem formal da aritmética é atribuído um número distinto. Este procedimento é conhecido como numeração de Gödel, codificação e, De forma geral, como aritmetização. Em particular, vários conjuntos de expressões são codificados como conjuntos de números. Para várias propriedades sintáticas (como ser uma fórmula, sendo uma frase, etc.), esses conjuntos são computáveis. Além disso, qualquer conjunto computável de números pode ser definido por alguma fórmula aritmética. Por exemplo, existem fórmulas na linguagem da aritmética definindo o conjunto de códigos para sentenças aritméticas, e para sentenças aritméticas demonstráveis.

O teorema da indefinibilidade mostra que essa codificação não pode ser feita para conceitos semânticos como verdade. Mostra que nenhuma linguagem interpretada suficientemente rica pode representar 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, para que existam teoremas demonstráveis ​​na metalinguagem não demonstráveis ​​na linguagem objeto.

O teorema da indefinibilidade é convencionalmente atribuído a Alfred Tarski. Gödel também descobriu o teorema da indefinibilidade em 1930, ao provar seus teoremas de incompletude publicados em 1931, e bem antes do 1933 publicação da obra de Tarski (Murawski 1998). Embora Gödel nunca tenha publicado nada relacionado à sua descoberta independente da indefinibilidade, ele o descreveu em um 1931 carta a John von Neumann. Tarski havia obtido quase todos os resultados de sua 1933 monografia "O conceito de verdade nas linguagens das ciências dedutivas" entre 1929 e 1931, e falou sobre eles para o público polonês. No entanto, como ele enfatizou no jornal, o teorema da indefinibilidade foi o único resultado que ele não obteve anteriormente. De acordo com a nota de rodapé do teorema da indefinibilidade (Teorema I.) do 1933 monografia, o teorema e o esboço da prova foram acrescentados à monografia somente após o manuscrito ter sido enviado à gráfica em 1931. Tarski relata lá que, quando apresentou o conteúdo de sua monografia à Academia de Ciências de Varsóvia em março 21, 1931, ele expressou neste lugar apenas algumas conjecturas, baseado em parte em suas próprias investigações e em parte no breve relatório de Gödel sobre os teoremas da incompletude "Alguns resultados metamatemáticos sobre definição e consistência de decisão" [Alguns resultados metamatemáticos sobre a definição de decisão e consistência], Academia Austríaca de Ciências, Viena, 1930.

Statement We will first state a simplified version of Tarski's theorem, então demonstre e prove na próxima seção o teorema que Tarski provou em 1933.

Seja L a linguagem da aritmética de primeira ordem. Essa é a teoria dos números naturais, incluindo a sua adição e multiplicação, axiomatizado pelos axiomas de Peano de primeira ordem. Isto é um "primeira ordem" teoria: os quantificadores se estendem sobre os números naturais, mas não sobre conjuntos ou funções de números naturais. A teoria é forte o suficiente para descrever funções inteiras recursivamente definidas, como exponenciação, fatoriais ou a sequência de Fibonacci.

Seja N a estrutura padrão para L, ou seja. N consiste no conjunto ordinário de números naturais e sua adição e multiplicação. Cada sentença em L pode ser interpretada em N e então se torna verdadeira ou falsa. Desta forma (eu, N) é o "linguagem interpretada de primeira ordem da aritmética".

Cada fórmula φ em L tem um número de Gödel g(Phi). Este é um número natural que "codifica" Phi. Dessa forma, a linguagem L pode falar sobre fórmulas em L, não apenas sobre números. Seja T o conjunto de L-sentenças verdadeiras em N, e T* o conjunto de números de Gödel das sentenças em T. O seguinte teorema responde à questão: Pode T* ser definido por uma fórmula de aritmética de primeira ordem?

Teorema da indefinibilidade de Tarski: Não existe fórmula L Verdadeiro(n) que define T*. Aquilo é, não existe fórmula L Verdadeiro(n) tal que para cada L-sentença A, Verdadeiro(g(UMA)) ↔ A vale em N.

Informalmente, o teorema diz que o conceito de verdade de declarações aritméticas de primeira ordem não pode ser definido por uma fórmula em aritmética de primeira ordem. Isso implica em uma grande limitação no escopo de "autorrepresentação". É possível definir uma fórmula True(n) cuja extensão é T*, mas apenas valendo-se de uma metalinguagem cujo poder expressivo ultrapassa o de L. Por exemplo, um predicado de verdade para aritmética de primeira ordem pode ser definido em aritmética de segunda ordem. No entanto, esta fórmula só seria capaz de definir um predicado de verdade para fórmulas na língua original L. Definir um predicado de verdade para a metalinguagem exigiria uma metametalinguagem ainda mais alta., e assim por diante.

Para provar o teorema, procedemos por contradição e assumimos que uma fórmula L True(n) existe o que é verdadeiro para o número natural n em N se e somente se n é o número de Gödel de uma sentença em L que é verdadeira em N. Poderíamos então usar True(n) para definir uma nova fórmula L S(m) que é verdade para o número natural m se e somente se m é o número de Gödel de uma fórmula φ(x) (com uma variável livre x) tal que φ(m) é falso quando interpretado em N (ou seja. a fórmula φ(x), quando aplicado ao seu próprio número Gödel, produz uma declaração falsa). Se considerarmos agora o número de Gödel g da fórmula S(m), e pergunte se a sentença S(g) é verdade em N, obtemos uma contradição. (Isso é conhecido como um argumento diagonal.) O teorema é um corolário do teorema de Post sobre a hierarquia aritmética, provou alguns anos depois de Tarski (1933). Uma prova semântica do teorema de Tarski a partir do teorema de Post é obtida por reductio ad absurdum como segue. Assumindo que T* é aritmeticamente definível, existe um número natural n tal que T* é definível por uma fórmula no nível {estilo de exibição Sigma _{n}^{0}} da hierarquia aritmética. No entanto, T* é {estilo de exibição Sigma _{k}^{0}} -difícil para todos k. Assim, a hierarquia aritmética colapsa no nível n, contradizendo o teorema de Post.

General form Tarski proved a stronger theorem than the one stated above, usando um método totalmente sintático. O teorema resultante se aplica a qualquer linguagem formal com negação, e com capacidade suficiente para auto-referência que o lema diagonal mantém. A aritmética de primeira ordem satisfaz essas pré-condições, mas o teorema se aplica a sistemas formais muito mais gerais, como ZFC.

Teorema da indefinibilidade de Tarski (Forma geral): Deixar (eu,N) ser qualquer linguagem formal interpretada que inclui negação e tem uma numeração Gödel g(Phi) satisfazendo o lema da diagonal, ou seja. para cada L-fórmula B(x) (com uma variável livre x) existe uma sentença A tal que A ↔ B(g(UMA)) detém em N. Então não existe fórmula L Verdadeiro(n) com a seguinte propriedade: para cada L-sentença A, Verdadeiro(g(UMA)) ↔ A é verdadeiro em N.

A prova do teorema da indefinibilidade de Tarski nesta forma é novamente por reductio ad absurdum. Suponha que uma fórmula L True(n) como acima existia, ou seja, se A é uma sentença da aritmética, então Verdadeiro(g(UMA)) vale em N se e somente se A vale em N. Portanto, para todo A, a fórmula verdadeira(g(UMA)) ↔ A vale em N. Mas o lema da diagonal fornece um contra-exemplo para esta equivalência, dando um "mentiroso" fórmula S tal que S ↔ ¬True(g(S)) detém em N. Isso é uma contradição. É.

Discussion The formal machinery of the proof given above is wholly elementary except for the diagonalization which the diagonal lemma requires. A prova do lema da diagonal também é surpreendentemente simples; por exemplo, ele não invoca funções recursivas de forma alguma. A prova assume que toda 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árias. Portanto, o teorema de Tarski é muito mais fácil de motivar e provar do que os teoremas mais celebrados de Gödel sobre as propriedades metamatemáticas da aritmética de primeira ordem..

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

Uma linguagem interpretada é fortemente semanticamente auto-representativa exatamente quando a linguagem contém predicados e símbolos de função que definem todos os conceitos semânticos específicos da linguagem. Portanto, as funções necessárias incluem o "função de avaliação semântica" mapeando uma fórmula A para seu valor de verdade ||UMA||, e a "função de denotação semântica" mapeando um termo t para o objeto que ele denota. O teorema de Tarski então generaliza da seguinte forma: Nenhuma linguagem suficientemente poderosa é fortemente semanticamente auto-representativa.

O teorema da indefinibilidade não impede que a verdade em uma teoria seja definida em uma teoria mais forte. Por exemplo, o conjunto de (códigos para) fórmulas da aritmética de Peano de primeira ordem que são verdadeiras em N é definível por uma fórmula na aritmética de segunda ordem. De forma similar, o conjunto de fórmulas verdadeiras do modelo padrão da aritmética de segunda ordem (ou aritmética de ordem n para qualquer n) pode ser definido por uma fórmula em ZFC de primeira ordem.

See also Gödel's incompleteness theorems – Limitative results in mathematical logic References J. eu. Sino, e M. Machover, 1977. Curso de Lógica Matemática. Holanda do Norte. G. Boolos, J. Cidadão, e R. Jeffrey, 2002. Computabilidade e lógica, 4ª edição. Cambridge University Press. J. R. Lucas, 1961. "Mente, Máquinas, e Gödel". Filosofia 36: 112-27. R. Murawski, 1998. Indefinibilidade da verdade. O problema da prioridade: Tarski vs. Gödel. História e Filosofia da Lógica 19, 153-160 R. Smullyan, 1991. Teoremas da Incompletude de Gõdel. Universidade Oxford. Imprensa. R. Smullyan, 2001. "Teoremas da Incompletude de Gödel". Em L. Goble, ed., O Guia Blackwell para a Lógica Filosófica, Blackwell, 72-89. UMA. Tarski, 1933. O Conceito de Verdade nas Linguagens das Ciências da Educação.. Publicado pela Sociedade Científica de Varsóvia. UMA. Tarski (1936). "O conceito de verdade nas linguagens formalizadas" (PDF). Estudos filosóficos. 1: 261-405. Arquivado a partir do original (PDF) sobre 9 Janeiro 2014. Recuperado 26 Junho 2013. UMA. Tarski, tr. J. H. Woodger, 1983. "O Conceito de Verdade em Linguagens Formalizadas". tradução inglesa de Tarski 1936 artigo. Em um. Tarski, ed. J. Corcoran, 1983, Lógica, Semântica, Metamatemática, Hackett. show vte Metalógica e metamatemática show vte Truth show vte Lógica matemática Categorias: Lógica matemáticaMetateoremasFilosofia da lógicaTeoremas nos fundamentos da matemáticaTeorias da verdade