[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Teorema de Godel



Eu li a HP e não ficou claro para mim a seguinte passagem:
 
Suponha que ~$x PROVA(x,g,g) é provável (no mesmo sentido) e seja p o número de Gödel dessa prova P. Então, nós temos que PROVA(p,g,g) é verdadeiro
 
Após ler este e-mail, eu entendi as coisas, mas me abstraindo da matemática e pensando apenas na semântica da coisa: "Eu não posso ser demonstrada". Depois tentei entender e essa passagem continuava obscura.... Depois de pensar bastante, acho que entendi (?). Gostaria de saber se as coisas são, de fato, como pensei.
 
g "incorpora" ~$x Prova (x,y,y)
Chamarei g(g)  ~$x Prova (x,g,g) - substituindo y por g
 
Se ~$x PROVA(x,g,g) é provável, isso quer dizer que g(g) não é provável.
Das duas uma: ou g(g) é verdadeira e não é provável, daí está provado o teorema,
                         ou g(g) é falso e sua negação é provável (portanto verdadeira).
A negação de g(g) é  $x Prova (x,g,g). Chamando esse x de p, segue o "Então, nós temos que PROVA(p,g,g) é verdadeiro".
 
[ ]'s
  Fred
 
PS - talvez isso devesse ser óbvio, mas para mim não é nada óbvio ... :)
 
 
 
 
----- Original Message -----
From: "Rogerio Fajardo" <rogeriofajardo@hotmail.com>
To: <obm-l@mat.puc-rio.br>
Sent: Thursday, January 03, 2002 12:38 AM
Subject: Re: Teorema de Godel

>
> 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
> >
>