Aula08

Primeiro teorema de incompletude de G¨ odel Teoremas de incompletude de G¨ odel Elaine Pimentel

P : Sejam n o n´ umero de G¨ odel de alguma seq¨ uˆ encia de express˜ oes e1, . . . , en e m o n´ umero de G¨ odel de uma express˜ ao bem formada e. Definimos o predicado P nm como sendo verdadeiro se e1, . . . , en ` e. Dizemos que P prova o par hn, mi.

1o Semestre - 2005

Q : Seja Qx uma express˜ ao bem formada que possui uma u ´ nica vari´ avel livre x e seja n o seu n´ umero de G¨ odel. Representamos por Qn a express˜ ao bem formada (fechada) formada a partir de Qx instanciando todas as ocorrˆ encias de x por n. Uma vez que Qn possui um n´ umero de G¨ odel, definimos o predicado Qxy que diz que y ´ e o n´ umero de G¨ odel de Qx.

Primeiro teorema de incompletude de G¨ odel

• Qn significa que algum n´ umero n possui a propriedade n. • Mas Qn tamb´ em diz que a express˜ ao bem formada com n´ umero de G¨ odel n (a saber, Qx), possui a propriedade Q, uma vez que n ´ e apenas a referˆ encia a Qx. • Ou seja, n cria um tipo de auto-referˆ encia indireta. Observe que predicados que fazem referˆ enca a si pr´ oprios correspondem a fun¸ c˜ oes recursivas.

Primeiro teorema de incompletude de G¨ odel • Com o predicado P xy, podemos tamb´ em dizer que uma express˜ ao bem formada A n˜ ao ´ e um teorema, ou n˜ ao pode ser provada em S. • De fato, seja a o n´ umero de G¨ odel de A. • Ent˜ ao a express˜ ao ¬(∃x.P xa) diz que n˜ ao existe seq¨ uˆ encia que prova A, ou simplesmente: ¬(` A)

G • O segundo passo para provar o teorema de G¨ odel consiste em construir a senten¸ ca bem formulada F de S:

Alguns coment´ arios sobre G

F : ¬(∃x.∃y.P xy ∧ Qzy) • Em palavras, F diz que n˜ ao existe uma prova do par hx, yi onde y ´ e o n´ umero de G¨ odel de Qz. Ou seja, Qz n˜ ao pode ser provado em S. • Para fazer F falar de si pr´ oprio, instanciamos au ´nica vari´ avel livre de F , z, ao n´ umero f de G¨ odel de F :

i. G = Qf , ou seja, G ´ e a auto referˆ encia de F . ii. G diz que n˜ ao existe prova do par hx, yi, onde y´ e o n´ umero de G¨ odel de Qf . Mas Qf ´ e G. iii. Ou seja, G diz que n˜ ao existe prova em S de G: G ≡ ¬(` G)

G : ¬(∃x.∃y.P xy ∧ Qf y)

Alguns coment´ arios sobre G Observa¸c˜ oes finais

iv. Mas a nega¸c˜ ao de G tamb´ em n˜ ao pode ser provada em S. De fato, suponha que ¬G seja prov´ avel em S. Ou seja, ` ¬G Como G ´ e o mesmo que a proposi¸c˜ ao ¬(` G), obtemos ` ¬G ≡ ` ¬(¬(` G)) ≡ `G o que contraria a nossa hip´ otese. v. Desta forma, dizemos que G ´ e indecid´ıvel em S, ou seja, nem G nem a sua nega¸c˜ ao podem ser provados em S.

• O coment´ ario v acima j´ a´ e suficiente para provar a incompletude de S e, portanto, provar o primeiro teorema de incompletude de G¨ odel para S. • Mas o fato mais extraordin´ ario sobre G ´ e que ele ´ e verdadeiro! De fato, G diz que n˜ ao existe prova de G em S e isso n´ os acabamos de ver que ´ e verdadeiro. Observe que n´ os “provamos” que G ´ e verdadeiro atrav´ es de uma meta-an´ alise, n˜ ao dentro de S. • Ou seja, n˜ ao obstante existem express˜ oes bem formadas que n˜ ao podem ser provadas em S, existem teoremas que n˜ ao podem ser provados.

Dilema da incompletude

Incompletude omega

• Uma pergunta interessante que surge ´ e: o que acontece se adicionarmos G ao conjunto de axiomas de S? O sistema resultante seria completo? • A resposta ´ e n˜ ao. De fato, chamemos S’ a uni˜ ao de S e G. G¨ odel provou que podemos sempre construir uma outra express˜ ao bem formada G0 que n˜ ao pode ser provada em S’. Claro, podemos adicionar G0 a S’ e assim por diante. • Atrav´ es do uso abstrato do m´ etodo de diagnaliza¸c˜ ao, G¨ odel provou que todos os sistemas dessa forma s˜ ao incompletos. Esse tipo de incompletude ´ e chamado incompletude omega.

• O teorema de G¨ odel n˜ ao se aplica a todos os sistemas de aritm´ etica: s´ o aos suficientemente fortes. • Isso cria o dilema da incompletude: ou o sistema ´ e incompleto porque ´ e muito fraco, ou ele ´ e forte mas ainda incompleto pelo teorema de G¨ odel. • Moral da est´ oria: se a matem´ atica ´ e consistente (e todos acreditamos que sim!), ela ´ e incompleta.

Segundo teorema de incompletude de G¨ odel

• O segundo teorema de incompletude de G¨ odel ´ e t˜ ao revolucion´ ario quanto o primeiro. • Em poucas palavras, o segundo teorema diz que nenhum sistema (suficientemente forte) pode provar a sua pr´ opria consistˆ encia, a n˜ ao ser que o sistema em si seja inconsistente. • A express˜ ao bem formada utilizada para provar esse teorema ´ e: SC : {S ´ e consistente}

Segundo teorema de incompletude de G¨ odel

1. 2. 3. 4.

SC ⇒ G (` SC) ⇒ (` G) ¬(` G) ¬(` SC)

provado no primeiro teorema (1) e meta-argumenta¸c˜ ao provado no primeiro teorema (2), (3) e modus tollens

Segundo teorema de incompletude de G¨ odel • O resultado do segundo teorema implica que, para provar a consistˆ encia de um sistema A, devemos fazˆ e-lo ou informalmente, ou atrav´ es de argumenta¸ c˜ ao em um sistema B. • Desta forma, obtemos apenas uma consistˆ encia relativa para A, uma vez que a consistˆ encia de A agora depende da consistˆ encia de B. • Mas, por sua vez, a consistˆ encia de B deve ser provada atrav´ es da argumenta¸ c˜ ao em um sistema C, e assim por diante.

G¨ odel • O primeiro teorema de G¨ odel provou que sistemas que cont´ em a aritm´ etica n˜ ao podem ser completos, e que alguns teoremas de teoria de n´ umeros nunca poder˜ ao se provadas verdadeiras ou falsas, n˜ ao importa o esfor¸ co que fa¸camos. • O segundo teorema mostra que a confian¸ca que temos na aritm´ etica n˜ ao pode nunca ser perfeita. • Ou seja, G¨ odel conseguiu, com uma tacada s´ o, destruir dois ideais da matem´ atica, e o fez em 1931, aos 25 anos de idade.