Re: Teorema de Godel e um Enigma

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Tue, 4 May 1999, Dopelg�nger wrote:

> 	Vamos definir que um l�giko ser� correto se tudo que ele for capaz de
> provar for verdadeiro; Ele jamais provar� nada que seja falso.
> 	Certo dia, um l�giko correto visitou a ilha dos cavaleiros e dos
> cavilosos, em que cada habitante � ou um cavaleiro ou um caviloso, e os
> cavaleiros s� fazem afirma��es verdadeiras e os cavilosos s� fazem
> afirma��es falasa. O l�giko encontra um habitante que lhe faz uma
> declara��o da qual decorre que ele pr�prio s� pode ser um cavaleiro, mas o
> l�giko n�o tem como prov�-lo!
> 	Que afirma��o teria este efeito?
> 
> *Nota do Autor: Este enigma tem uma rela��o pr�xima com o famoso resultado
> conhecido como teorema de G�del, de modo que discutiremos em seguida �
> solu��o.

Uma tentativa de solu��o que me ocorre �:
"Voc� [o logiko] jamais poder� demonstrar que eu sou um cavaleiro!".

Um caviloso jamais faria esta afirma��o, pois ela seria verdadeira.
Um cavaleiro talvez pudesse fazer esta afirma��o, mas s� se o logiko
de fato n�o pudesse demonstrar que ele era um cavaleiro.
Mas a d�vida �: ser� que cavaleiro poderia mesmo fazer esta afirma��o?
O teorema de G�del mostra que existe uma frase que indiretamente afirma:
"eu n�o sou demonstr�vel"; a frase � verdadeira mas n�o demonstr�vel.
Mas a dificuldade est� em mostrar que existe uma tal frase.

[]s, N.
http://www.mat.puc-rio.br/~nicolau