Oi Samuel. Taí um tópico que sempre me interessou, pois eu me considero um "anti-infinitista"
> Esse argumento é mais ou menos o seguinte: se tiramos o Axioma do > Infinito de ZFC, podemos até mesmo incluir um Axioma do tipo "Todos os > conjuntos sao finitos" e essa teoria fica consistente - basta cortar o > universo no nível \omega da "Hierarquia Cumulativa" e temos lá um > modelo disso. Então, será que alguém já estudou estes modelos e uma teoria dos conjuntos com este axioma: "todos os cjs são finitos"? Como seria uma matemática não-transcendental, totalmente baseada em conjuntos finitos. O Problema da Parada seria 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 > > O argumento de transcendência é, sendo absurdamente reducionista, > dizer que "assumir a existencia de inacessíveis é um ato de > transcendência análogo ao de assumir a existência de conjuntos > infinitos". Tipo - se já fizemos uma vez, qual o problema em se fazer > de novo ? Para alguns teoristas de conjuntos, é uma maneira de > estender ZFC "mais natural" que o forcing... > > Na verdade, o meu interesse maior é em trabalhar com fatos topológicos > que nao podem ser discutidos sem incluir a presenca de inacessíveis na > jogada, escrevi algo sobre isso nos Proceedings de Itatiaia 2006. > > http://jigpal.oxfordjournals.org/cgi/content/short/15/5-6/433 > > No entanto, acho que mais relacionado ao que estamos discutindo sao > alguns resultados de Harvey Friedman nos quais "assercoes sobre > conjuntos finitos" acabam sendo associados a grandes cardinais. Nunca > pesquisei isso, mas me parece bem interessante. Lembremos também que a > própria nocao de finitude nao fica suficientemente clara se retirarmos > o Axioma da Escolha ! Perde-se a equivalência com a nocao de > infinitude de Dedekind. > > Até mais, > > []s Samuel > > > > > > > Quoting Carlos Gonzalez <gonza...@gmail.com>: > >> Olá Samuel, >> >> Além de Con(PA) poder ser provada em ZF, podemos trabalhar com teorias >> mais fortes, como ZF + "existe um cardinal inacessível"=ZFI. >> Trivialmente, Con(ZFI) implica Con(ZF). >> >> Em ZFI pode ser demonstrada Con(ZF), que é um enunciado aritmético >> (com a numeração de Gödel) e que implica Con(PA). >> >> Se ZF é consistente, então Con(ZF) não implica Con(ZFI), de modo que a >> consistência de ZFI é mais duvidosa que as outras mencionadas. >> >> Gödel tinha muitas esperanças nos grandes cardinais, mas depois de >> muita pesquisa não se chegou a nenhum resultado amplamente aceito. >> (Ver o trabalho de Gödel sobre a Hipótese do Contínuo.) >> >> Carlos >> >> Em 2 de agosto de 2010 20:58, Francisco Antonio Doria >> <famado...@gmail.com> escreveu: >>> 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 <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 >>>> >>> >>> >>> >>> -- >>> fad >>> >>> ahhata alati, awienta Wilushati >>> >>> >>> _______________________________________________ >>> Logica-l mailing list >>> Logica-l@dimap.ufrn.br >>> http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l >>> >>> >> > > > > ---------------------------------------------------------------- > 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 > -- 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 Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
