[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