---------- Forwarded message ---------- From: Francisco Antonio Doria <[email protected]> Date: 2010/8/3 Subject: Re: [Logica-l] Resenha de Gödel sobre Skolem-- um deslize acerca dos modelos não standard To: Marcelo Finger <[email protected]>, [email protected], [email protected]
Sempre tem um algoritmo pa resolver instâncias finitas e número do problema da parada; não tem é ***um só** algoritmo. 2010/8/3 Marcelo Finger <[email protected]> Oi Samuel. > > eria trivialmente resolvível, pois as > máquinas de Turing sempre parariam (um conjunto de estados de uma > execução infinita não existiria). Existe algo sobre isso? > > []s > > Marcelo > > > > > > > > > > > > > >>>>>>> > 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 > >>> > >>> > >> > > > > > > > > ---------------------------------------------------------------- > > 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 > > > > > > -- > 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 > _______________________________________________ > Logica-l mailing list > [email protected] > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > -- 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
