Sim! No caso do Kunen, o algoritmo é todo primitivo recursivo, exceto numa passagem que corresponde à indução transfinita. E que é simplesmente o uso de uma função não p.r. Muito interessante.
2011/9/29 Rodrigo Freire <[email protected]> > 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 >> >> > -- fad ahhata alati, awienta Wilushati _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
