Por exemplo: posso escrever explicitamente um conjunto de máquinas de Turing P tal que:
``as máquinas P são polinomiais'' é indecidível em ZFC, e não equivale à sentença de Gödel. 2010/8/2 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 > > -- fad ahhata alati, awienta Wilushati
_______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
