Post em 43 ou 44 publicou uma prova intuitiva, muito simples, do primeiro teorema de incompletude, que foi depois reformulada por Martin Davis em termos de máquinas de Turing. Novamente não usa nenhum paradoxo.
O próprio teorema de Chaitin pode ser provado sem referência a qualquer paradoxo. A prova dele, usando ``programas elegantes,'' leva umas poucas linhas e é muito simples. 2009/8/12 Francisco Antonio Doria <[email protected]> > Perdão, A recursivo. > > 2009/8/12 Francisco Antonio Doria <[email protected]> > > Tá no artigo de Kleene de 1936. >> >> 1) Enumera todas as sentenças demonstráveis da aritmética da forma ``para >> todo x existe y tal que A(x, y),'' A primitivo recursivo. >> >> 2) Estas sentenças enumeram (enumeração r.e.) todas as funções recursivas >> provadamente totais da aritmética onde estamos. >> >> 3) Diagonaliza em cima: temos uma função que é recursiva e total, mas não >> se prova isso na aritmética. >> >> 4) Tal função é total no modelo standard. >> >> 5) Se supusermos que a aritmética é sound, ela será parcial num modelo não >> standard. >> >> Basta uma diagonalização; não precisa de Berry ou Liar. >> >> Tem outras formas mais precisas de se construir tal função. Na aritmética, >> ela será p.r. na função F_\epsilon_0 da hierarquia de Kreisel-Wainer. >> > >
_______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
