[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Teorema de Godel

To: <obm-l@xxxxxxxxxxxxxx>
Subject: Re: Teorema de Godel
From: "Frederico Pessoa" <fredao@xxxxxxx>
Date: Tue, 8 Jan 2002 16:31:56 -0200
References: <F87pROF86jlxdNlI0500001b1ef@hotmail.com>
Reply-To: obm-l@xxxxxxxxxxxxxx
Sender: owner-obm-l@xxxxxxxxxxxxxxxxxxxxx
Tava tentando ignorar essa parte por enquanto... Mas j� que est�o falando
tanto...


O que � um sistema consistente ???


[]'s
   Fred


----- Original Message -----
From: "Rogerio Fajardo" <rogeriofajardo@hotmail.com>
To: <obm-l@mat.puc-rio.br>
Sent: Monday, January 07, 2002 5:54 PM
Subject: Re: Teorema de Godel


>
> Tamb�m n�o entendi o que ele chama de "lema diagonal", mas creio que se
> refere �s f�rmulas de 2 vari�veis livres �ExPROVA(x,y,z) que eu mencionei.
> De fato, se imaginarmos essas f�rmulas, substituindo y e z por n�mero,
> obtemos, para cada para (y,z) uma senten�a (p.ex. �ExPROVA(x,1000,100)).
Se
> considerarmos as f�rmulas �ExPROVA(x,y,z) com y=z (como fizemos) isso nos
d�
> uma esp�cie de diagonal de Cantor, e uma dessas senten�as dessa "diagonal"
> (aquela da forma �ExPROVA(x,n,n) onde n � o n�mero de Godel da f�rmula de
> uma vari�vel livre �ExPROVA(x,y,y)) � a senten�a G que diz "G n�o pode ser
> demonstrado". Para o primeiro terorema da incompletude, temos:
>    1)Se provarmos G, provamos que "G pode ser demonstrada", isto �,
provamos
> �G, e o nosso sistema � inconsistente.
>    2)Se provarmos �G, ent�o provamos que "G pode ser demonstrada", e,
logo,
> provamos G e, novamente, obtemos um sistema inconsistente.
>    Portanto, se o sistema for consistente, e nele conseguirmos construir
uma
> f�rmula como G, n�o conseguiremos provar nem G nem �G (nosso sistema ser�
> incompleto). Mas godel mostra que, para construirmos uma senten�a como G,
> basta que o sistema seja capaz de exprimir a aritm�tica e seus axiomas e
> regras de infer�ncia formem um conjunto "recursivo" (pode ser codificado
na
> aritm�tica). Essa � a hip�tese que est� no site.
>    Para o 2�teorema, vimos que, se provarmos G, nosso sistema ser�
> inconsistente. Logo, se o sistema � consistente, n�o podemos provar G.
> Portanto, se provarmos que o sistema � consistente, provamos que n�o
podemos
> provar G. Mas dizer "G n�o pode ser provada" � a pr�pria G, portanto,
nosso
> sistema ser� inconsistente (como vimos). Portanto, o segundo teorema nos
diz
> que se um sistema � consistente e obedece as condi��es do teorema 1, ent�o
> n�o podemos provar sua consist�ncia.
>
>
>
> >From: Carlos Ma�aranduba <soh_lamento@yahoo.com.br>
> >Reply-To: obm-l@mat.puc-rio.br
> >To: obm-l@mat.puc-rio.br
> >Subject: Re: Teorema de Godel
> >Date: Sat, 5 Jan 2002 15:48:40 -0300 (ART)
> >
> >D� uma olhada neste endere�o e explica-me por favor
> >que diagonal � essa.� a mesma usada por
> >Cantor???Ajuda-me a compreender o 1 teorema que esta
> >neste site.
> >
> >http://www.cle.unicamp.br/prof/carnielli/teoremas_de_godel.htm
> >
> >
> >  --- Rogerio Fajardo <rogeriofajardo@hotmail.com>
> >escreveu: >
> > > A id�ia � criar uma senten�a que diz: "eu n�o posso
> > > ser provada", ou seja,
> > > uma senten�a, cujo n�mero de godel � x, que diz que
> > > n�o existe demonstra��o
> > > para a f�rmula cujo n�mero de godel � x.
> > >    Para entender a f�rmula que godel criou, �
> > > necess�rio o conceito de
> > > vari�vel livre. A f�rmula "x � primo" possui uma
> > > vari�vel livre x, n�o
> > > podemos deizer que ela � verdadeira ou falsa sem
> > > conhecer o valor de x. Para
> > > eliminar essa vari�vel livre, tem duas maneiras: uma
> > > � substituir x por um
> > > n�mero (p.ex. "7 � primo"), outra � colocar um
> > > quantificador ("existe x t.q.
> > > x � primo"). Note que uma f�rmula sem vari�vel livre
> > > (que chamamos
> > > "senten�a") deve ser ou verdadeira ou falsa (i.e,
> > > sua nega��o verdadeira) em
> > > um modelo matem�tico fixado (que precisa ser
> > > definido, mas, intuitivamente,
> > > � uma interpreta��o para o significado das
> > > f�rmulas). O sistema de axiomas
> > > ideal deve provar ou a senten�a ou sua nega��o. Pois
> > > bem, godel cria uma
> > > senten�a que n�o pode ser provada nem ela nem sua
> > > nega��o.
> > >
> > > Para obter essa senten�a, godel criou a f�rmula
> > > PROVA(x,y,y) que significa:
> > > "A sequ�ncia de f�rmulas cujo n�mero � x � uma
> > > demonstra��o da f�rmula (de
> > > n�mero y) de uma vari�vel livre, substituindo sua
> > > vari�vel livre pelo valor
> > > y". Por exemplo, se 1000 � o n�mero da f�rmula "x �
> > > primo",
> > > PROVA(12345,1000,1000) diz: "12345 � o n�mero da
> > > demonstra��o de "1000 �
> > > primo".
> > >
> > > A f�rmula �ExPROVA(x,y,y) diz "a f�rmula de n�mero
> > > y, substituindo sua
> > > vari�vel livre por y, n�o p�de ser provada". No
> > > nosso exemplo,
> > > �ExPROVA(x,100,1000) diz "n�o existe demonstra��o de
> > > que 1000 � primo". Pois
> > > bem, �ExPROVA(x,y,y) tem uma vari�vel livre y, e tem
> > > um n�mero (seja g esse
> > > n�mero). Portanto a f�rmula �ExPROVA(x,g,g) � uma
> > > senten�a (note que g n�o �
> > > uma vari�vel, mas um n�mero conhecido, que eu j�
> > > calculei). E essa senten�a
> > > diz: "A f�rmula de n�mero g, substituindo sua
> > > vari�vel livre por g, n�o pode
> > > ser provada". Mas quem � a f�rmula de n�mero g? � o
> > > pr�prio �ExPROVA(x,y,y).
> > > E substituindo sua vari�vel livre por g? � a propria
> > > senten�a
> > > �ExPROVA(x,g,g). Portanto, �ExPROVA(x,g,g)  diz
> > > "�ExPROVA(x,g,g) n�o pode
> > > ser provada", que gera o paradoxo que quer�amos (uma
> > > senten�a que diz "eu
> > > n�o posso ser provada").
> > >
> > > Observe que, se um sistema for consistente, eu de
> > > fato n�o consigo provar
> > > �ExPROVA(x,g,g). Mas isso se o sistema for
> > > consistente (i.e., n�o provar uma
> > > f�rmula e sua nega��o). Caso contr�rio, tudo vira
> > > teorema, e tudo pode ser
> > > provado (de uma contradi��o provamos qualquer
> > > coisa), inclusive
> > > �ExPROVA(x,g,g). Mas se eu provar a consist�ncia do
> > > sistema, eu acabei de
> > > provar que �ExPROVA(x,g,g) n�o pode ser provada. Mas
> > > isso, como vimos, � o
> > > pr�prio �ExPROVA(x,g,g), e chegamos numa
> > > contradi��o. Concluindo: a segunda
> > > parte do Teorema de Godel (conhecido como segundo
> > > teorema de godel) diz que,
> > > se um sistema for consistente, sua consist�ncia n�o
> > > pode ser provada (dentro
> > > do pr�prio sistema).
> > >
> > > Uma observa��o importante � que, apesar de dar a
> > > id�ia geral da
> > > demonstra��o, a demonstra��o que est� no site est�
> > > longe de ser completa.
> > > Fica a pergunta: como godel criou (ou provou que
> > > existe) a f�rmula
> > > PROVA(x,y,y) usando s� o fato de que o sistema �
> > > capaz de exprimir a
> > > aritm�tica e de que seus axiomas formam um conjunto
> > > recursivo (consigo
> > > decidir, atrav�s de um algoritmo finito, se uma
> > > f�rmula � axioma ou n�o). �
> > > interessante olhar no trabalho original de godel
> > > ("On formally undecidable
> > > propositions of principia mathematica and related
> > > systens") como ele
> > > codifica cada axioma, e cada regra de infer�ncia, em
> > > termos de rela��es
> > > aritm�ticas. Repare que a f�rmula indecid�vel
> > > �ExPROVA(x,g,g), no fundo �
> > > uma gigantesca f�rmula que s� envolve n�meros,
> > > conectivos l�gicos, e as
> > > opera��es + e *.
> > >
> > >
> > > >From: Carlos Ma�aranduba <soh_lamento@yahoo.com.br>
> > > >Reply-To: obm-l@mat.puc-rio.br
> > > >To: obm-l@mat.puc-rio.br,
> > > ciencialist@yahoogrupos.com.br
> > > >Subject: Teorema de Godel
> > > >Date: Wed, 2 Jan 2002 18:43:16 -0300 (ART)
> > > >
> > > >neste endere�o h� uma demonstra��o do teorema de
> > > godel
> > > >que aparentemente � simples de se entender.Alguem
> > > >poderia ver a parte que ele usa o predicado
> > > >PROVA(x,g,g) e explicar-me pq ele faz isso?????
> > > >
> > > >
> > >
> >
>http://www.pr.gov.br/celepar/celepar/batebyte/edicoes/2000/bb95/teorema.htm
> > > >
> > >
> >
>___________________________________________________________________________
____________________
> > > >Yahoo! GeoCities
> > > >Tenha seu lugar na Web. Construa hoje mesmo sua
> > > home page no Yahoo!
> > > >GeoCities. � f�cil e gr�tis!
> > > >http://br.geocities.yahoo.com/
> > >
> > >
> > >
> >_________________________________________________________________
> > > Send and receive Hotmail on your mobile device:
> > > http://mobile.msn.com
> > >
> >
>
>___________________________________________________________________________
____________________
> >Yahoo! GeoCities
> >Tenha seu lugar na Web. Construa hoje mesmo sua home page no Yahoo!
> >GeoCities. � f�cil e gr�tis!
> >http://br.geocities.yahoo.com/
>
>
> _________________________________________________________________
> Send and receive Hotmail on your mobile device: http://mobile.msn.com
>
>
References:
- Re: Teorema de Godel
  - From: Rogerio Fajardo
Prev by Date: Re: En: ajuda em an�lise
Next by Date: RE: Sobre a equacao do MUV
Prev by thread: Re: Teorema de Godel
Next by thread: Re: Teorema de Godel
Index(es):
- Date
- Thread