Obrigado, mas a análise não é só minha. O Terence Tao já viu isso antes, e eu identifiquei o problema junto com um colega (que já escreveu para o Nelson).
Não conheço especificamente o algoritmo do Kunen, mas conheço outro algoritmo para a mesma coisa (a consistência de Peano). Esses algoritmos não são primitivos recursivos. Mas tudo bem, não importa. A afirmação do Nelson não é que alguma teoria T não prova que uma função primitiva recursiva é total. Isso de fato existe, teorias mais fracas que PRA. A afirmação do Nelson é que superexponenciação não é total, e não apenas que alguma teoria não prova isso. É essa afirmação mais forte que não sei o que quer dizer. A propósito, para localizar bem o erro do Nelson no livro: página 37, linha 8 de baixo para cima. O que segue sobre o \mu está errado. Em particular, está errado que \mu >= l_1, que seria a contradição. Abraço Rodrigo 2011/9/28 Francisco Antonio Doria <[email protected]> > Gostei da tua análise; te cumprimento por ela, mas tem um ponto de que > discordo: > > *não acho que exista a mais remota possibilidade de > Nelson ter provado o que ele afirma, que alguma função primitiva recursiva > não é total. Afinal, o que faz o algoritmo que calcula a função em termos > dos valores anteriores? * > > O que a gente vê intuitivamente, nesse caso ou em casos similares, não é > necessariamente o que se prova. Vc conhece o algoritmo de Kunen para provar > Paris-Harrington? A gente vê que o algoritmo converge, mas PA não... > > 2011/9/28 Rodrigo Freire <[email protected]> > >> Li, junto com um colega, uma parte do manuscrito do Nelson. Identificamos >> o >> erro que o Terence Tao apontou: no livro ocorre na página 37 na parte de >> aritmetização do teorema de Chaitin e da prova de Kritchman e Raz. >> >> O problema é que a cada subteoria de Q* corresponde um l diferente na >> aritmetização do teorema de Chaitin, e o Nelson está usando sempre o mesmo >> l >> da teoria Q*. >> >> A descrição de Nelson da sua construção na seção "The plan" usa apenas >> resultados conhecidos de lógica e generalidades de teoria da complexidade. >> Ele poderia tentar mostrar como fica a construção se substituir PRA por >> ZFC >> e Q por PA, o que facilitaria bastante a codificação. Afinal, é um >> corolário >> do que ele propõe (e um corolário bem mais modesto) que ZFC provaria que >> PA >> é inconsistente. Ele tenta usar o fato que Q* prova a consistência de suas >> subteorias finitas para tentar tirar alguma inconsistência. PA e ZFC >> provam >> que suas subteorias finitas são consistentes, a construção parece não ter >> nada de especial em relação a Q*. Além disso ele usa que PRA prova a >> consistência de Q. Claro que ZFC também prova a consistencia de PA. Acho >> que >> seria útil ver nesse caso "modesto" como fica a prova. >> >> Para deixar bem claro, não acho que exista a mais remota possibilidade de >> Nelson ter provado o que ele afirma, que alguma função primitiva recursiva >> não é total. Afinal, o que faz o algoritmo que calcula a função em termos >> dos valores anteriores? Essa afirmação não me parece inteligível. >> >> Obs: Vi que o Nelson escreveu na lista fom, supostamente respondendo o >> comentário do Terence Tao. Não acho que ele tenha respondido >> satisfatoriamente. Parece que o Terence Tao não se expressou muito bem >> falando de "complexidade da teoria", o que Nelson diz que não está >> definido. >> No entanto, parece claro que Tao se referia ao l que é um para cada >> teoria. >> >> Abraço >> Rodrigo >> _______________________________________________ >> Logica-l mailing list >> [email protected] >> http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l >> > > > > -- > fad > > ahhata alati, awienta Wilushati > > _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
