Tem várias provas simples do primeiro teorema de incompletude. Tem uma, imediata, de Kleene, que vale para sentenças ∏2.
On 8/5/09, Rodrigo Oliveira <[email protected]> wrote: > > > Olá Marcelo Finger, > Obrigado pelos esclarecimentos. > Fiquei com certo receio ao ler a apresentação do teorema que o Watzlawick > faz, por isso minha pergunta sobre a apresentação que ele faz do teorema, > embora conheça o teorema apenas pela apresentação informal do livro Prova de > Gödel, do Newman e do Nagel, acompanho a lista e vi algumas correções sobre > o teorema de Gödel sendo feitas. Meu desconforto foi exatamente o ponto que > abordou, quando ele afirma que G é demonstrável a partir das premissas e > axiomas do sistemas. Nesse ponto fiz bem em postar o texto, pois eliminou > minha dúvida. Fico com a sensação, porém de que talvez ele pudesse querer > dizer que ela era permitida pelos axiomas do sistema, ou expressável no > sistema, dai teria que ver o original em inglês. Mesmo assim pecaria ao se > referir a qualquer sistema, como apontou o Décio, muitos sistemas não > conseguem nem reproduzir o teorema. > Eu tenho certo receio quanto à essas abordagens também, embora ache que seja > necessário e creio que será o caminho pelo qual irei. Postar o texto aqui na > lista foi uma forma de filtrar o texto. Mesmo com os pequenos erros > identificados, trata-se de um apêndice, um complemento no espírito do texto, > mas sem ligação direta com este. Não compromete o livro. > > Nunca tinha ouvido falar em omega-consistência, pode falar mais a respeito? > Abraço > Rodrigo > Date: Mon, 3 Aug 2009 14:21:04 -0300 > Subject: Re: [Logica-l] Paul Watzlawick, o teorema de Gödel e o Tractatus de > Wittgenstein > From: [email protected] > To: [email protected] > CC: [email protected] > > Caro Rodrigo. > > Os problemas começam quando se toma o Teorema de Goedel como sendo o que ele > não é. Segundo o seu texto: > > "Gödel > pôde demonstrar que nesse sistema ou algum outro equivalente é possível > construir uma frase, G, que (1) é demonstrável a partir das premissas e > axiomas do sistema, mas que (2) afirma de si mesma que é > indemonstrável. " > > Lamento, mas o que o Teorema diz é que, se uma teoria T for uma extensão da > Aritmética de Peano, então existe uma fórmula A: > > a) SE A TEORIA T FOR CONSISTENTE, A não é demonstrável em T; e > > b) SE A TEORIA T FOR omega-CONSISTENTE, a negação de A não é demonstrável > em T. > > Essas pré-condições de consistência são absolutamente fundamentais tanto > para a demonstração quanto para a compreensão do teorema. (Rosser depois > mostrou que a omega-consistência pode ser reduzida a apenas consistência > usando uma outra fórmula). A sua análise, e muitas outras, omitem este > facto. > > > Aliás, o teorema é chamado de "incompletude", pois uma teoria é incompleta > se existe uma fórmula tal que nem ela nem sua negação podem ser > demonstradas. O Teorema de Gödel diz q a aritmética de Peano é incompleta e > não pode ser completada. > > > Em nenhum lugar está dito que a fórmula A responsável pela incompletude é > "demonstrável a partir das premissas e > axiomas do sistema". Aliás, se ela assim fosse, ou o teorema ou a > aritmética seriam inconsistentes. Por sinal, a auto referência da fórmula A > não é direta, mas se dá através de um sistema > de codificação de fórmulas e provas em elementos da aritmética (de > peano). Esta codificação não é única, diversas codificações distintas > servem de base para o teorema. > > Espero ter ajudado. > > []s > > Marcelo > > > > > 2009/8/3 Rodrigo Oliveira <[email protected]> > > > > > > > > > > > > > > > > > > Olá a todos, > > Estou lendo o livro Pragmática da Comunicação Humana, do Paul Watzlawick. No > fim do livro ele faz uma relação entre o teorema de Gödel e o que ele chama > de o paradoxo fundamental da existência humana, sendo o Tractatus de > Wittgenstein uma maneira de expressar esse paradoxo. Reproduzo aqui o texto, > que é um pouquinho longo para um e-mail. Gostaria de ouvir comentários obre > ele, dado que qui se encontram especialistas nos temas abordados. Penso em > coisas como: o modo como ele apresenta o teorema é adequado? A relação que > ele apresenta faz sentido? Se a estrutura é semelhante mesmo, como > Wittgenstein aparentemente não entendeu o teorema de Gödel? O teorema de > Gödel envolve a auto-referência, Wittgenstein negava tal coisa... Que pensam > disso? > > > Abraços > > Rodrigo > > > Segue o texto: > > As hierarquias como aquelas com que estamos agora ocupados foram > detalhadamente exploradas num ramo da matemática moderna, com o qual nosso > estudo tem grande afinidade, exceto o fato de que a matemática é de uma > coerência e rigor incomparavelmente maiores do que nós podemos ter sequer > esperança de alcançar. O Ramo em questão é a teoria da prova - ou > metamatemática. Tal como esta última denominação claramente implica, essa > área da matemática trata de si mesma, isto é, das leis inerentes à > matemática e o problema de saber se a matemática é ou não coerente. > Portanto, não surpreenderá que os matemáticos tenham encontrado e > investigado, essencialmente, as mesmas consequências paradoxais da > auto-reflexividade, muito antes de que analistas da comunicação humana > estivessem cônscios sequer de sua existência. De fato, o trabalho nessa área > remonta a Schöder (1895), Löwenheim (1915) e, especialmente, a Hilbert > (1918). A teoria da prova, ou metamatemática, era então a preocupação > altamente abstrata de um brilhante, embora reduzido, grupo de matemáticos, > situado, por assim dizer, fora da corrente principal da atividade > matemática. Segundo parece, dois acontecimentos serviram, subsequentemente, > para que a teoria da prova ocupasse o foco das atenções. Um deles foi a > publicação, em 1931, do histórico artigo de Gödel sobre as proposições > formalmente indetermináveis, um trabalho que os professores da Universidade > de Harvard descreveram como o mais importante progresso realizado num quarto > de século no campo da lógica matemática. O Outro acontecimento foi o > aparecimento quase explosivo do computador, depois da II Guerra Mundial. > Essas máquinas foram rapidamente desenvolvidas a partir de autômatos > rigidamente programados, até se converterem em organismos artificiais > imensamente versáteis que começaram a propor problemas fundamentais sobre a > teoria da prova, logo que a sua complexidade estrutural atingiu um ponto em > que foi possível fazê-los decidir por si mesmos qual era, entre vários, o > procedimento otimal de computação. Por outras palavras, surgiu a > possibilidade de projetar computadores que não só executavam um programa > mas, ao mesmo tempo, eram capazes de efetuar mudanças em seus programas. > > > > Na teoria da prova, a expressão procedimento de decisão, refere-se à questão > de apurar se existe ou não um procedimento do tipo que se acaba de > descrever. Portanto, um problema de decisão tem uma solução positiva de > puder ser encontrado um procedimento de decisão para resolvê-lo, enquanto > que uma solução negativa consiste em provar que tal procedimento não existe. > Nesta conformidade, os problemas de decisão são referidos ou como > computáveis ou como insolúveis. > > Entretanto, existe uma terceira possibilidade. As soluções definidas > (positivas ou negativas) de um problema de decisão só são possíveis quando o > problema em questão se encontra dentro do domínio (a área de aplicabilidade) > desse específico procedimento de decisão. Se esse procedimento de decisão > for aplicado a um problema fora do seu domínio, a computação prosseguirá > indefinidamente, sem provar jamais que uma solução (positiva ou negativa) > está prestes a ser alcançada. É neste ponto que voltamos a encontrar o > conceito de indeterminabilidade. > > Este conceito é o tema central do acima citado artigo de Gödel sobre as > proposições formalmente indetermináveis. O sistema formalizado que esse > autor escolheu para o seu teorema foi os Principia Mathematica, a monumental > obra de Whitehead e Russel, explorando os alicerces da matemática. Gödel > pôde demonstrar que nesse sistema ou algum outro equivalente é possível > construir uma frase, G, que (1) é demonstrável a partir das premissas e > axiomas do sistema, mas que (2) afirma de si mesma que é indemonstrável. > Isto significa que, se G é demonstrável no sistema, a sua > indemonstrabilidade (que é o que di de si mesmo) também seria demonstrável. > Mas se tanto a demonstrabilidade como a indemonstrabilidade podem ser > derivadas dos axiomas do sistema e os próprios axiomas são coerentes (o que > faz parte da prova de Gödel, então G é indemonstrável em termos do sistema, > tal como a previsão paradoxal apresentada em s. 6.441 é indeterminável em > termos do seu "sistema", que é a informação contida no anúncio do diretor da > escola e o contexto em que é feito. A prova de Gödel reveste-se de > consequências que vão muito além da lógica matemática; de fato, demonstra de > uma vez para sempre que qualquer sistema formal (matemático, simbólico etc.) > é necessariamente incompleto no sentido acima estabelecido e que, além > disso, a coerência de um tal sistema só pode ser demonstrada recorrendo a > métodos de prova que são mais genéricos do que aqueles que o próprio sistema > pode gerar. > > Detivemo-nos mais demoradamente no trabalho de Gödel porque vemos nele a > analogia matemática do que chamaríamos o paradoxo fundamental da existência > humana. O homem é, em última instância, sujeito e objeto de sua busca. > Conquanto seja sobre se a mente pode ser considerada algo semelhante a um > sistemaformalizado, tal como foi definido no parágrafo precedente, a bsca > humana de uma compreensão do significado de sua existência constitui uma > tentativa de formalização. Somente nesse sentido entendemos que certos > resultados da teoria da prova especialmente nas áreas da auto-reflexividade > e da indeterminabilidade) são pertinente. Isto não é, de maneira alguma, uma > descoberta nossa; de fato, dez anos antes de Gödel apresentar o seu > brilhante teorema, outras das grandes inteligências do nosso século já > formulara esse paradoxo em termos filosóficos; referimo-nos a Ludwig > Wittgenstein, em seu Tractatus Logico-Philosophicus. Provavelmente, em > nenhuma outra obra foi esse paradoxo existencial definido de maneira mais > lúcida nem ao místico foi conferido uma posição mais digna como o passo > final que transcende esse paradoxo. > > Wittgenstein mostra-nos que só poderíamos saber algo sobre o mundo, em sua > totalidade, se pudéssemos sair fora dele; mas se isso fosse possível, este > mundo já não seria todo o mundo. Contudo, a nossa lógica nada conhece fora > dele: > > "A lógica enche o mundo: os limites do mundo são também seus > imites.Portanto, não podemos dizer em lógica: Isto e isto há no mundo, > aquilo não há.Pois isso, evidentemente, pressuporia que excluímos certas > possibilidades e tal não pode ocorrer, dado que, de outro modo, a lógica tem > que sair dos limites do mundo; que dizer, se pudéssemos considerar estes > limites também do outro lado. > O que não podemos pensar, não podemos pensar; portanto não podemos dizer o > que não podemos pensar." > O mundo, assim, é finito e, ao mesmo tempo, ilimitado; ilimitado, > precisamente, porque nada existe fora que, junto ao de dentro, possa > constituir uma fronteira. Mas, assim sendo, deduz-se que "O mundo e a vida > são uma só coisa. Eu sou o meu mundo". Logo, sujeito e mundo já não são > entidades cuja função relacional é, de algum modo, governada pelo verbo > auxiliar ter (que um tem o outro, contém ou lhe pertence) mas, outrossim, > pelo ser existencial: "O sujeito não pertence ao mundo, é um limite do > mundo". > > Dentro desse limite, é possível formular e responder a perguntas > significativas: "Se é víavel formular uma pergunta, então também se pode > responder-lhe". Mas "a solução do enigma da vida no espaço e no tempo está > fora do espaço e do tempo". Pois, como já deve estar mais do que > esclarecido, nada dentro de um quadro de referência pode enunciar ou mesmo > perguntar coisa alguma sobre esse quadro de referência. Portanto, a solução > não consiste em encontrar uma resposta para o enigma da existência mas em > compreender que esse enigma não existe. Esta é a essência das belas frases > finais do Tractatus, com seu sabor reminiscente do Budismo Zen: > > "Para uma resposta que não pode ser expressa, tampouco a pergunta pode ser > expressa. O enigma não existe. (...)Sentimos que, mesmo se respondêssemos a > todas as possíveis perguntas científicas, mesmo assim os problemas da vida > continuariam intocados. É claro, não restará então pergunta alguma e esta é > precisamente a resposta. > A solução do problema da vida vislumbra-se quando esse problema se dissipa. > (Não é essa, porventura, a razão pela qual os homens a quem, após longas > dúvidas, o sentido da vida se lhes torna claro, não podem dizer em que > consiste esse sentido?) > Existe, sem dúvida, o inexpressável. Este mostra-se a si mesmo, é o > místico...Do que não podemos falar, devemos guardar silêncio." > Conheça os novos produtos Windows Live. Clique aqui! > > > _______________________________________________ > > Logica-l mailing list > > [email protected] > > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > > > > > -- > Marcelo Finger > Departamento de Ciencia da Computacao > Instituto de Matematica e Estatistica > Universidade de Sao Paulo > Rua do Matao, 1010 > > 05508-090 Sao Paulo, SP Brazil > Tel: +55 11 3091-9688, 3091-6135, 3091-6134 (fax) > http://www.ime.usp.br/~mfinger > > > _________________________________________________________________ > Descubra todas as novidades do novo Internet Explorer 8 > http://brasil.microsoft.com.br/IE8/mergulhe/?utm_source=MSN%3BHotmail&utm_medium=Tagline&utm_campaign=IE8 _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
