[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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