[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Teorema de Godel
Um sistema é completo se não existe sentença indecidível (que não dá pra
provar a sentença nem sua negação). Ou seja, um sistema incompleto é aquele
que "não decide tudo". A definição de consistência é semelhante. Um sistema
é CONSISTENTE se não entra em contradição (não dá pra provar uma sentença E
sua negação). Observe que, no teorema de godel, ao criarmos a fórmula P que
diz "eu não posso ser provada", uma das seguintes coisas ocorre:
1) Não dá para provar P nem ¬P. Nesse caso, o sistema é INCOMPLETO.
2) Tanto P como ¬P podem ser provados. Nesse caso, o sistema é
INCONSISTENTE (i.e., entra em contradição).
Observe que a sentença (A e ¬A)=>B é verdadeira, para quaisquer fórmulas A e
B. Portanto, se provarmos A e ¬A, podemos provar qualquer fórmula B. Ou
seja, DE UMA CONTRADIÇÃO PROVAMOS QUALQUER COISA. Por isso considero o
segundo teorema de godel (se um sistema é consistente, não podemos provar
sua consistência) muito mais drástico que o primeiro. Se um dia, alguém
provar que a matemática (o sistema ZFC de teoria dos conjuntos, que serve de
base para praticamente toda matemática moderna) é inconsistente, todas as
fórmulas matemáticas serão teoremas (1+1=3, todo triângulo é isósceles,
nenhum triângulo é isósceles, o Último Teorema de Fermat, etc), e portanto,
quase tudo que foi feito até agora, em matemática, será destruído, pois
sairá como corolário do teorema "a matemática é inconsistente". Mas, se a
matemática é consistente (como todos acreditam), nunca o provaremos, e
sempre haverá essa "chance" de provarmos que a matemática é inconsistente.
>From: "Frederico Pessoa" <fredao@mail.ru>
>Reply-To: obm-l@mat.puc-rio.br
>To: <obm-l@mat.puc-rio.br>
>Subject: Re: Teorema de Godel
>Date: Tue, 8 Jan 2002 16:31:56 -0200
>
>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
> >
> >
>
>
_________________________________________________________________
Send and receive Hotmail on your mobile device: http://mobile.msn.com