Meio confuso esse conceito de non-Gödelian... 2010/8/2 <[email protected]>
> 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.” I’m > more than a bit embarrassed that this survives into the fourth printing, for > Smorynski isn’t 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 <[email protected]>: > > Gentzen 36 equivale à sentença de Gödel, Samuel. Tem Kleene 36. Dá pra >> fazer >> infinidades. >> >> 2010/8/2 <[email protected]> >> >> 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 <[email protected]>: >>> >>> Cuidado que a sentença de Paris-Harrington ***não é*** equivalente a >>> >>>> Consis >>>> PA. >>>> >>>> 2010/8/2 <[email protected]> >>>> >>>> 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 <[email protected]>: >>>>> >>>>> > 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 >>>>> [email protected] >>>>> 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 > > -- fad ahhata alati, awienta Wilushati
_______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
