Oi Dória, É verdade que Gentzen 36 é equivalente a G que é equivalente a Con(PA), o que acho que Smorynski e outros querem dizer com "verdade aritmética nao-Godeliana", ou algo assim, é que nao se trata de uma sentenca baseada em algo do tipo "afirmar que ela própria é nao-demonstrável", obtida por diagonalizacao e etc.
Achei os comentários do Paul Smith sobre o review do Smorynskï, ele praticamente se desculpa pelo escorregao histórico: Finally, on p. 210 (p. 211 in the current printing), I write The first example of a more natural, non-Gödelian, arithmetical statement which is true, statable in the language of basic arithmetic, yet demonstrably not provable in PA, was found by Jeff Paris and Leo Harrington in 1977. Im more than a bit embarrassed that this survives into the fourth printing, for Smorynski isnt the first to point out to me that, as in a sense I knew perfectly well, This is simply false. The first natural, non-Gödelian arithmetical statement unprovable in PA was induction up to ε0, shown underivable by Gentzen in his Habilitationschrift in 1939. Following that, there was the unprovability of the totality of certain recursive functions as emphasized by Kreisel circa 1958. Indeed. Até, []s Samuel Quoting Francisco Antonio Doria <famado...@gmail.com>: > Gentzen 36 equivale à sentença de Gödel, Samuel. Tem Kleene 36. Dá pra fazer > infinidades. > > 2010/8/2 <sam...@ufba.br> > >> Olá Dória, >> >> Grato pela respostas também ! >> >> Eu já tinha percebido isso. Alguns autores chegam a chamar de "sentencas >> nao-godelianas" as sentencas aritméticas verdadeiras (no modelo standard) >> que nao podem ser demonstradas, indo pela ordem no tempo: >> >> - Gentzen 36 (Con(PA) por inducao sobre epsilon_zero) >> >> - Paris Harrington >> >> - Goodstein >> >> Tem um review do Smorynski sobre um livro de Smith (nao li o review inteiro >> mas li uns comentários do próprio Smith) no qual o Smorynski critica >> duramente o Smith por uma imprecisao histórica, pois o Smith no livro dele >> (Introduction to Godel Theorems) teria dito que o primeiro exemplo de uma >> "nao-Godeliana" seria Paris-Harrington, tendo se esquecido de Gentzen 36 (e >> de mais algumas coisas dos anos 50, nao me recordo agora). >> >> Até, >> >> []s Samuel >> >> >> >> >> >> Quoting Francisco Antonio Doria <famado...@gmail.com>: >> >> Cuidado que a sentença de Paris-Harrington ***não é*** equivalente a >>> Consis >>> PA. >>> >>> 2010/8/2 <sam...@ufba.br> >>> >>> Olá a todos, >>>> >>>> Agradeco pelas respostas. A universidade aqui (estou no México) está >>>> em seu (extenso) recesso de verao, nao tinha ninguém pra bater bola, >>>> foi bom bater bola com voces. >>>> >>>> Walter: obrigado pelos comentários e pelo material. Seu aluno Anderson >>>> também me mandou alguma coisa, já o agradeci também. Vou comentar algo >>>> da sua resposta: >>>> >>>> >>>> Quoting Walter Carnielli <walter.carnie...@gmail.com>: >>>> >>>> > Caro Samuel: >>>> > >>>> > o que você levanta são questões profundamente interessantes. >>>> > >>>> > Envio a voce em separado (parece que a Lista não aceita o arquivo) >>>> > um prefácio de Robert Vaught sobre o "review" que Gödel publicou >>>> > sobre os trabalhos de Skolem de 1933 e 1934 (dos quais >>>> > Gödel diz que "são praticamente os mesmos"). Isso aparece nos >>>> > "Collected Works" vol I, editado S. Fefermann, pp. 376-379, que são >>>> > as páginas que envio. >>>> > >>>> > O texto contem a resenha que você procura, e ainda a importante >>>> > opinião de Vaught. >>>> > >>>> > Aparentemente Gödel não viu que a existência dos modelos não standard >>>> > segue do Teorema da Compacidade (que ele mesmo demonstrou em 1930!). >>>> > Como Vaught nota na pag. 377, Gödel afirma que tais modelos >>>> > não-standard seguiriam do seu Teorema de Incompletude (o que não é >>>> > incorreto da maneira que Gödel coloca, mas não revela a razão >>>> > principal). >>>> > >>>> > Dou aí abaixo algumas opiniões sobre o que você pergunta (mas >>>> > não são mais que opiniões- não me considero nenhum "especialista" >>>> > sobre o assunto--de resto, parece que nem Gödel, nem Skolem o >>>> > eram...). >>>> > ************************************************************** >>>> > >>>> >>>> ----------> Pois é, é um assunto derrapante mesmo, como vc disse depois. >>>> >>>> >> "Suponha PA consistente. Entao, pelo Primeiro Teorema de Incompletude, >>>> >> PA nao prova a sentenca de Godel G. >>>> >> >>>> >> Segue que PA + ~G é consistente, logo, pelo Teorema da Completude para >>>> >> teorias de primeira ordem, tem modelo. >>>> >> >>>> >> Nesse modelo vale ~G. Entao esse modelo difere do modelo standard, no >>>> >> qual a sentenca de Godel G é verdadeira". >>>> >> >>>> > >>>> > >>>> > Sim, os modelos não- standard suportam essa situação perfeitamente >>>> bem. >>>> > >>>> > ************************************************************** >>>> >> >>>> >> Apresento algumas questoes, nao sei se elas sao "bobagem" ou nao... >>>> >> >>>> >> 1) Alguém sabe se este é o argumento de Gödel na tal resenha, ou se >>>> >> ele usou esse argumento depois ? >>>> > >>>> > >>>> > Não usou, e acho (mas não tenho certeza) que Gödel nunca usou >>>> > este argumento. Mas nos trabalhos contemporâneos acredito que isso >>>> > já seja "folclore". >>>> > >>>> >>>> ------------> Estou sem o meu Kleene aqui, mas na página 377 do Review >>>> que vc me mandou o Vaught diz que na página 430 do Kleene tem um >>>> comentário sobre o argumento de Gödel, e penso que deve ser algo >>>> parecido mesmo, pegar uma A nao provável, olhar para consistencia de >>>> PA + ~A e aplicar completude. >>>> >>>> Mesmo pensando em termos do modelo standard, o Francicleber me mandou >>>> uma mensagem (a qual também agradeco) lembrando que nao há porque se >>>> preocupar só com a sentenca de Gödel, pois para qualquer A que nao >>>> seja demonstrável, teremos uma entre A, ~A será válida no modelo >>>> standard, e assim teremos uma fórmula válida no modelo standard que >>>> nao será consequencia sintática de PA e que portanto nao vale em todos >>>> os modelos, garantindo a existencia dos modelos nao-standard (mas >>>> passando pelo Teorema da Completude...). >>>> >>>> >>>> >>>> >>>> >> >>>> >> 2) Usualmente se diz que "G é verdadeira e nao pode ser demonstrada". >>>> >> Bem, G é (facilmente) equivalente à consistência de PA (o que >>>> >> inclusive já prova o Segundo Teorema de Incompletude). >>>> >> >>>> >> Muitas vezes se diz que "G é verdadeira no modelo standard" (isso >>>> >> aparece inclusive no argumento que eu destaquei acima). Essa afirmacao >>>> é >>>> >> intuitiva ou pode ser mesmo formalizada ? >>>> > >>>> > Sim, pode ser verificada no modelo standard. >>>> >>>> >>>> >>>> --------> Nao achei nenhuma boa referencia sobre isso, mas deu pra >>>> entender que a argumentacao usa a nocao de "truth-in-a-model"... >>>> Essencialmente, a codificacao de Gödel é em cima dos naturais >>>> standard, e depois de feita a prova, olhamos para as codificacoes e >>>> checamos que uma certa fórmula com quantificador vale no modelo >>>> standard (como é semântico, "basta olhar", se fosse sintático teria >>>> que aparecer algo como \omega-consistência). Essa fórmula é G. OK. >>>> >>>> >>>> >>>> > >>>> >> (sobre esse problema eu vi que se tem uma discussao filosófica >>>> >> interessante, "saber" (ou "ser capaz de deduzir que") que a sentenca G >>>> >> é verdadeira seria uma prova de que a mente humana supera os >>>> >> computadores, isso seria um tal argumento de Lucas/Penrose...) >>>> > >>>> > >>>> > Mas essa é outra questão-- a propósito, dê uma olhada em: >>>> > >>>> > "Why is the Lucas-Penrose Argument Invalid?" Manfred Kerber, >>>> > http://www.cs.bham.ac.uk/~mmk/papers/05-KI.html >>>> > >>>> >>>> >>>> --------> Essa questao do argumento de Lucas\Penrose, eu já tinha >>>> visto que era bem polêmica... Vou ler esse artigo que vc me indicou. >>>> Trombei na internet com um artigo do Shapiro de nome engracado, >>>> tratando nao exatamente disso mas de algo relacionado: "A sentenca de >>>> Godel é verdadeira - mas alguém mudou de assunto ?" >>>> >>>> >>>> >>>> >>>> >> 3)(e aqui uma pergunta que se alguém me fizer hoje eu nao sei >>>> responder) >>>> >> >>>> >> A sentenca de Godel G é equivalente a Con(PA). Assim, se eu assumo >>>> >> Con(PA), estou assumindo que G é verdadeira. Ela nao deveria entao ser >>>> >> verdadeira em todos os modelos de PA ? Como fica o argumento acima >>>> >> para modelos nao-standard ? >>>> > >>>> > Se eu entendi bem questão (essas coisas são derrapantes), tudo >>>> > isso vale para o modelo standard de PA. Para os não -standard, seria >>>> > outra coisa. Mas não há nada de chocante nisso (pelo menos como eu >>>> > vejo). >>>> > >>>> >>>> >>>> ------> É, aqui eu dei uma derrapda, por falta de experiencia de >>>> trabalhar com PA (faco argumentos do tipo para ZFC e nunca tive >>>> problema nenhum !). Como PA nao prova Con(PA), entao, como a >>>> aritmética, apesar de ser sintaticamente incompleta, é semanticamente >>>> completa, nao vai ter Con(PA) válida em todos os seus modelos. >>>> Tranquilo. Devo estar entre os que pensam no Teorema da Completude >>>> como sendo para LÓGICAS de primeira ordem, sendo que podemos enunciar >>>> para TEORIAS de primeira ordem... Simplesmente, esqueci de aplicar >>>> Completude quando fiz a pergunta (3) !!! >>>> >>>> "Assumir a consistencia de PA" nao é uma frase "cataclismica" que muda >>>> a compreensao das coisas, só equivale a dizer que uma certa fórmula >>>> (ou string de números...) está sendo suposta verdadeira. "Assumir a >>>> consistencia de PA" é "Estamos trabalhando num modelo onde a sentenca >>>> de Godel é satisfeita". >>>> >>>> Como disse, estou sempre fazendo isso em ZFC. Existem muitas assercoes >>>> matemáticas equivalente a CH (Hipótese do Contínuo) - uma simples e >>>> que estou fazendo propaganda é a seguinte: "Se do plano R^2 retiramos >>>> um conjunto de tamanho aleph_1, o que resta é um conjunto simplesmente >>>> conexo". "Assumir CH" nao faz com que essa frase sobre o R^2 seja >>>> verdadeira, "Assumir CH" é trabalhar num modelo em que CH vale (e essa >>>> frase sobre o plano também). >>>> >>>> >>>> > Estou trabalhando na questão da consistência, preparando um artigo >>>> > para os "Proceedings" do evento "CLE/AIPS - Science, Truth and >>>> > Consistency" (em homenagem >>>> > aos 80 anos do Newton) . Minha proposta, mas isso leva uma 25 >>>> > páginas, é que há tantas noções de "consistência" que o conceito >>>> > axiomatizado (como nas LFI's) deveria ser levado a sério, e teria >>>> > talvez até modelos não standard! >>>> > >>>> > >>>> >>>> ------> Bom, depois gostaremos todos de ter acesso ao trabalho ! >>>> A nocao de "consistencia nao-standard" deve ser interessante... Grato, >>>> Walter. >>>> >>>> >>>> Décio: meio sem querer, durante a preparacao dessa minha palestra, eu >>>> acabei me preocupando com essas questoes do tipo que vc levantou, "as >>>> más interpretacoes" do Teorema da Incompletude. Fora as questoes mais >>>> óbvias, aplicando incompletude para a Bíblia ou para a Constituicao, >>>> existem outras mais sutis. >>>> >>>> Por exemplo, uma frase que eu já falei para os meus alunos e que nao >>>> está errada, mas dá a entender algo que nao é lá muito correto: >>>> >>>> "O Teorema da Incompletude mostra que existem questoes matemática >>>> indecidíveis, como por exemplo a Hipótese do Contínuo" >>>> >>>> Bem, tem que se tomar cuidado aí. O Teorema da Incompletude mostra que >>>> existem questoes *aritméticas* indecidíveis. Claro que sao questoes >>>> matemáticas, mas usar a Hipótese do Contínuo como exemplo pode dar a >>>> entender que a indecidibilidade da Hipótese do Contínuo (CH) seria um >>>> "corolário da demonstracao" dos teoremas de incompletude, o que nao é >>>> o caso (a consistencia >>>> de CH veio da construcao do modelo construtível, e a de ~CH veio da >>>> invencao do método de forcing). >>>> >>>> Tem um livro recente do Torkel Franzen, "Incomplete guide for use and >>>> abuse...etc.", acredito que o Walter conhece este livro, assim como >>>> outros colegas também... Nesse livro o autor (que aparentemente >>>> morreu há pouco) faz comentários bastante interessantes sobre este >>>> tipo de problemas. Os teoremas da incompletude nao impedem que alguém >>>> faca uma teoria sobre números e fantasmas que seja sintaticamente >>>> completa no que se refere a... fantasmas. >>>> >>>> Antes de me despedir, levanto uma outra questao, já que falei no >>>> Torkel Franzen: >>>> >>>> Ele tem uma visao interessante sobre o que é dizer que uma assercao >>>> (aritmética) A é verdadeira. >>>> >>>> Ele diz que "A é verdadeira" é equivalente ao... enunciado de A. >>>> >>>> Por exemplo, "A Conjectura de Goldbach é verdadeira" é equivalente a >>>> "Todo par maior do que 2 é soma de dois primos". Pronto, acabou, é uma >>>> afirmacao sobre números naturais. >>>> >>>> OK, legal, mas concordam que ele está se referindo ao modelo standard >>>> ? Que na verdade ele está se referindo a naturais standard ? >>>> >>>> Pelo que percebi, isso acontece também quando se discutem teoremas >>>> como o de Paris-Harrington e o de Goodstein: dizer que "uma afirmacao >>>> é verdadeira e nao pode ser demonstrada" é dizer que "uma afirmacao é >>>> verdadeira no modelo standard e nao pode ser demonstrada". >>>> >>>> Aí eu pergunto aos colegas: é consenso entre os filósofos da matemática >>>> que >>>> >>>> fato aritmético verdadeiro = fato aritmético verdadeiro no modelo >>>> standard >>>> ? >>>> >>>> Se sim, acho que é por aí a nocao do Torkel Franzen. >>>> >>>> Até mais, >>>> >>>> []s Samuel >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> ---------------------------------------------------------------- >>>> Universidade Federal da Bahia - http://www.portal.ufba.br >>>> >>>> _______________________________________________ >>>> Logica-l mailing list >>>> Logica-l@dimap.ufrn.br >>>> http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l >>>> >>>> >>> >>> >>> -- >>> fad >>> >>> ahhata alati, awienta Wilushati >>> >>> >> >> >> ---------------------------------------------------------------- >> Universidade Federal da Bahia - http://www.portal.ufba.br >> >> > > > -- > fad > > ahhata alati, awienta Wilushati > ---------------------------------------------------------------- Universidade Federal da Bahia - http://www.portal.ufba.br _______________________________________________ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
