On Thu, Mar 04, 2004 at 11:06:02AM -0300, [EMAIL PROTECTED] wrote: > Isso que vc citou � o famoso teorema da incompletude de > G�del que afirma que existem proposi��es e problemas > indecid�veis na matem�tica (que n�o podem ser > provadas nem negadas). > Exemplo de uma tal proposi��o: > > Teorema X: O teorema X n�o pode ser demonstrado. > Quest�o: Demonstre o teorema X. > > A quest�o acima � indecid�vel. A metamatem�tica lida > com quest�es do tipo acima.
Desculpe, mas acho que esta sua explica��o do que � uma quest�o indecid�vel confunde mais do que esclarece. Uma proposi��o � indecid�vel quando nem ela nem a sua nega��o seguem dos axiomas da teoria (que podem ser dados explicita ou implicitamente). Mas uma proposi��o � algo claro, sem autorefer�ncias expl�citas, como no seu exemplo. A hip�tese do cont�nuo diz que se X � um subconjunto infinito de R ent�o ou existe uma bije��o entre X e N ou entre X e R. Ela � um exemplo de proposi��o indecid�vel em ZFC: isto significa que com os axiomas de ZFC n�o � poss�vel nem demonstrar nem refutar a hip�tese do cont�nuo. Outro exemplo � dado por m�quinas de Turing. Uma m�quina de Turing � uma esp�cie de computador idealizado que vai fazendo um monte de opera��es e que pode parar em tempo finito ou n�o. O problema da parada consiste em reconhecer (de forma algor�tmica) quais m�quinas de Turing param e quais n�o (n�o se exige uma *demonstra��o* de que o algoritmo funciona, s� o pr�prio algoritmo) e Turing demonstrou que n�o existe um tal algoritmo. O que isto prova � que *qualquer* que seja o nosso conjunto de axiomas, desde que ele seja recursivamente enumer�vel (isto �, desde que exista um algoritmo que cospe todos os axiomas e *apenas* os axiomas), sempre existir�o m�quinas de Turing x para as quais a proposi��o "a m�quina de Turing x para em tempo finito" � indecid�vel. Veja ali�s http://www.research.att.com/~njas/sequences/Seis.html para ver como s�o pequenas e simples as m�quinas de Turing para as quais ningu�m sabe se elas param ou n�o. O que voc� parece ter em mente � o exemplo original de G�del de uma proposi��o indecid�vel em PA (aritm�tica de Peano). O exemplo de G�del � uma frase G, bem expl�cita e bem complicada, que fala de n�meros naturais: ela n�o fala de proposi��es serem verdadeiras ou falsas, demonstr�veis ou refut�veis. � s� usando o processo de encodificar a l�gica de primeira ordem na aritm�tica de Peano, criado tamb�m por G�del, que vemos que G pode ser traduzida como "G n�o � demonstr�vel em PA". Assim vemos que G � verdadeira mas n�o � demonstr�vel em PA. Existem outros exemplos de frases sobre n�meros naturais que s�o sabidamente verdadeiras e sabidamente n�o demonstr�veis em PA: a demonstra��o de que a frase � verdadeira � feita em outra teoria, claro, por exemplo em ZFC. Tem um exemplo de uma vers�o forte do teorema de Ramsey (sobre o qual falamos muito recentemente) que � assim: a coisa est� descrita com detalhes no �ltimo artigo do Handbook of Mathematical Logic. []s, N. ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================
