Teoremas da Incompletude de Gödel

1. Teoremas da Incompletude de Godel
Teoremas da Incompletude de Godel
Helio H. L. C. Monte-Alto
Anderson da Silva Marcolino
Lucas de Oliveira Teixeira
2012
1 / 28

2. Teoremas da Incompletude de Godel
Sumario
Sumario
1Sumario
2Vis~ao geral
3Denic~oes
4Demonstrac~ao
5Prova usando Sistemas de Representac~ao Abstratos
2 / 28

3. Teoremas da Incompletude de Godel
Vis~ao geral
Vis~ao geral
Kurt Godel
Matematico austraco
Desenvolveu os dois teoremas da incompletude em 1931
Matematica no incio do seculo XX
Positivismo
Acreditava-se que seria possvel encontrar um conjunto de
axiomas completo e consistente para toda matematica
Segundo problema de Hilbert: provar que a aritmetica e
consistente
Os teoremas da incompletude s~ao largamente aceitos como
uma resposta negativa a este problema
3 / 28

4. Teoremas da Incompletude de Godel
Vis~ao geral
Teoremas - Vis~ao geral
Denic~ao informal:
1Qualquer teoria axiomatica recursivamente enumeravel e
capaz de expressar aritmetica elementar n~ao pode ser, ao
mesmo tempo, consistente e completa.
2Para qualquer teoria formal recursivamente enumeravel T que
inclui verdades aritmeticas basicas e tambem certas verdades
da teoria da prova, se T inclui uma armac~ao de sua propria
consist^encia, ent~ao T e inconsistente
4 / 28

5. Teoremas da Incompletude de Godel
Denic~oes
Denic~oes
Um sistema econsistentese n~ao e possvel deduzir
contradic~oes a partir de seus axiomas.
Um sistema ecompletose e de possvel deduzir todas as
formulas verdadeiras a partir de seus axiomas.
Umateoria axiomaticae uma teoria baseada num conjunto de
axiomas a partir dos quais s~ao deduzidos teoremas utilizando
procedimentos bem denidos.
Em sntese, Godel provou que, se a aritmetica e consistente, ent~ao
e incompleta.
5 / 28

6. Teoremas da Incompletude de Godel
Demonstrac~ao
Demonstrac~ao
Princpio: auto-refer^encia
Reescrita de um sistema formal utilizando a linguagem dos
numeros naturais
Exemplo: Problema de Smullyan
6 / 28

7. Teoremas da Incompletude de Godel
Demonstrac~ao
Problema Godeliano de Smullyan
Seja um programa que imprime cadeias com os seguintes smbolos
:;I;N;(;)
Uma cadeiaXe imprimvel se o programa pode imprimi-la.
Supomos que o programa imprimira, mais cedo ou mais tarde,
todas as cadeias imprimveis.
A norma de uma cadeiaXe a cadeiaX(X).
Uma sentenca e uma cadeia de uma das quatro formas abaixo:
1I(X)
2IN(X)
3:I(X)
4:IN(X)
ondeXe uma cadeia.
7 / 28

8. Teoremas da Incompletude de Godel
Demonstrac~ao
Problema Godeliano de Smullyan
Seja a sentenca:IN(:IN).
Por denic~ao, esta sentenca e verdadeira se e somente se a norma
da cadeia:INn~ao e imprimvel.
No entanto, a norma de:INe justamente a sentenca:IN(:IN),
logo esta sentenca e verdadeira se e somente se ela n~ao e
imprimvel. Temos duas hipoteses:
a sentenca e imprimvel, mas falsa - contradic~ao, pois o
programa so imprime sentencas verdadeiras;
a sentenca e verdadeira, mas n~ao imprimvel;
8 / 28

9. Teoremas da Incompletude de Godel
Demonstrac~ao
Problema Godeliano de Smullyan
Analogia:
O programa n~ao e capaz de imprimir todas as sentencas
verdadeiras
Um sistema formal possuira armac~oes verdadeiras que n~ao
podem ser provadas
9 / 28

10. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Prova usando Sistemas de Representac~ao Abstratos
Os teoremas foram inicialmente provados para o sistema
formal da aritmetica (Aritmetica de Peano)
Prova mais generica: utilizando Sistemas de Representac~ao
Abstratos (SRA)
SRAs permitem representar sistemas de alta diversidade de
estruturas sintaticas
10 / 28

11. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sistemas de Representac~ao Abstratos
Um sistema de representac~ao abstrato (SRA) Z e uma setupla
hE;g;S;T;R;P;ionde
Ee um conjunto enumeravel de elementos chamados de
express~oes;
ge uma func~ao deEemN, bijetora, chamada deenumerac~ao de
Godel;
S E: sentencas;
T Ssentencas verdadeiras, ou teoremas;
R Ssentencas falsas, ou anti-teoremas;
P Ee um conjunto de predicados unarios;
, chamada de func~ao derepresentac~ao, e uma func~ao deE N
emE, que atribui a cada express~ao H e numero natural n, a
express~ao (H;n), que sera abreviada porH(n).
11 / 28

12. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sistemas de Representac~ao Abstratos
Figure :
12 / 28

13. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sistemas de Representac~ao Abstratos
Exemplo: Teoria dos numeros - Numeros primos
Seja o predicadoPrimo.
Ent~ao (Primo;n) e a sentencaPrimo(n), lida como "ne
primo".
Supondo quen= 5 temos quePrimo(5) e uma sentenca
verdadeira (Primo(5)2 T) e que sen= 6 temos que
Primo(6) e uma sentenca falsa (Primo(6)2 R).
13 / 28

14. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
SRAs - Consist^encia e Completude
SejaZ=hE;g;S;T;R;P;ium SRA. Dizemos que Z e:
ConsistenteSeT \ R=;;
CompletoSeT [ R=S;
SaturadoSe Z e consistente e completo.
Ze completo se, e somente se, toda sentenca deZe decidvel em
Z
14 / 28

15. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Diagonalizac~ao, numeros e sentencas de Godel
Diagonalizac~ao
SejaZum SRA eXuma express~ao deZ, cujo numero de Godel e
g(X). A express~ao (X;g(X)) e a diagonalizac~ao ou norma deX.
CasoXseja um predicadoH, (H;g(H)) e uma sentenca,
chamada de sentenca diagonal, que denotamos porH(h).
Numeros de Godel
SejaZum SRA eW E.W

e o conjunto dos numeros de Godel
das express~oesXcuja diagonalizac~ao (X;X)2 W, isto e:
W

=fXjX=g(X) e (X;X)2 Wg
15 / 28

16. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Diagonalizac~ao, numeros e sentencas de Godel
Figure : X
qualquer e a de um predicadoH.
16 / 28

17. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sentencas de Godel
Sentencas de Godel
SejaXuma sentenca eAum conjunto de numeros. Dizemos que
Xe uma sentenca de Godel paraAse e somente seXtem a
propriedade:X2 T ()X2A.
Intuitivamente, uma sentenca de Godel arma que o numero de
Godel de um predicado satisfaz o predicado.
Xe uma sentenca de Godel para um conjuntoAde numeros
quandog(X) (o signicado deXemN) pertence ao conjuntoAse
e somente se este fato (sua pertin^encia) e provavel no sistema, isto
e, pertence aT.
17 / 28

18. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sentencas de Godel
Exemplo - Analogia
Conjunto das palavras que gozam da propriedade implicada
por seu signicado
Ex:proparoxtonoe umaproparoxtona
Vamos chamar as palavras que n~ao gozam dessa propriedade
deheterossignicantes.
Pergunta:heterossignicanteeheterossignicante?
CONTRADIC~AO!!
18 / 28

19. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sentencas de Godel
Exemplo - Analogia
Conjunto das palavras que gozam da propriedade implicada
por seu signicado
Ex:proparoxtonoe umaproparoxtona
Vamos chamar as palavras que n~ao gozam dessa propriedade
deheterossignicantes.
Pergunta:heterossignicanteeheterossignicante?
CONTRADIC~AO!!
18 / 28

20. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sentencas de Godel
Sentencas de Godel
Seja X uma sentenca eWum conjunto de express~oes. Dizemos
que X e uma sentenca de Godel paraWse e somente se X tem a
propriedade:X2 T ()X2 W.
Podemos concluir disso que todas as sentencas de Godel se
encontram na regi~ao (T \g
1
(A))[(S (T [g
1
(A)))
Figure : A[1].
19 / 28

21. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sentencas de Godel
Figure : W.
20 / 28

22. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sentencas de Godel
Primeiro lema da diagonalizac~ao
SejaZum SRA eW E. SeW

e representavel emZent~aoW
admite (existe) uma sentenca de Godel. Mais especicamente, se
He um predicado que representaW

, ent~aoH(h)e uma sentenca
de Godel paraW.
Teorema 1
Seja Z um SRA. O conjuntoT

n~ao e representavel em Z.
Demonstrac~ao:Suponha queT

e representavel. Ent~ao existe um
predicadoHque o representa emZ. Pelo Lema da diagonalizac~ao,
H(h)e uma sentenca de Godel paraT

. Desse modo,H(h)2 Tse
e somente seH(h)2T, o que e um absurdo. Logo,T

n~ao e
representavel.
21 / 28

23. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sentencas de Godel
Primeiro lema da diagonalizac~ao
SejaZum SRA eW E. SeW

e representavel emZent~aoW
admite (existe) uma sentenca de Godel. Mais especicamente, se
He um predicado que representaW

, ent~aoH(h)e uma sentenca
de Godel paraW.
Teorema 1
Seja Z um SRA. O conjuntoT

n~ao e representavel em Z.
Demonstrac~ao:Suponha queT

e representavel. Ent~ao existe um
predicadoHque o representa emZ. Pelo Lema da diagonalizac~ao,
H(h)e uma sentenca de Godel paraT

. Desse modo,H(h)2 Tse
e somente seH(h)2T, o que e um absurdo. Logo,T

n~ao e
representavel.
21 / 28

24. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sentencas de Godel
Figure : W.
E se considerarmosW=R, quais seriam as sentencas de Godel
paraR?
Corolario
Seja Z um SRA. Ent~ao, toda sentenca indecidvel e uma sentenca
de Godel paraR.
22 / 28

25. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sentencas de Godel
Figure : W.
E se considerarmosW=R, quais seriam as sentencas de Godel
paraR?
Corolario
Seja Z um SRA. Ent~ao, toda sentenca indecidvel e uma sentenca
de Godel paraR.
22 / 28

26. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sentencas de Godel
Teorema "Quase La"
Seja Z um SRA. SeR

e representavel em Z, ent~ao Z e
inconsistente ou incompleto.
Demonstrac~ao: SeR

e representavel ent~ao existe um predicado,
digamosH, que o representa. Pelo lema da diagonalizac~ao,H(h)e
uma sentenca de Godel paraR. Assim,H(h)2 T ()H(h)2 R.
Isto signica que: (i)H(h)2 T \ Re assim Z seria inconsistente
ou (ii)H(h)=2 T [ Re neste caso Z seria incompleto.
23 / 28

27. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sentencas de Godel
Figure :
24 / 28

28. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sistemas formais como SRAs
Teorema 1F
Seja Z uma SRAE. Se todo conjunto recursivo e representavel em
Z, ent~ao Z e um sistema formal indecidvel.
Demonstrac~ao: Suponha queTfosse recursivo. LogoTtambem
seria recursivo. Ent~ao,T

seria recursivo. Desta forma,T

seria
representavel em Z, pela hipotese do teorema, o que contraria um
dos teoremas mostrados.
25 / 28

29. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Sistemas formais como SRAs
Teorema 2F
Seja Z uma SRA. Se Z e um sistema formal indecidvel, ent~ao Z e
inconsistente ou incompleto.
Demonstrac~ao: Se Z e saturado (negac~ao do teorema), tera ambos
TeRcomo conjuntos recursivamente enumeraveis e
complementares com respeito aS, portanto ambosTeRseriam
recursivos e portanto Z decidvel. Logo Z e n~ao saturado, ou seja,
inconsistente ou incompleto.
26 / 28

30. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Teorema nal
Primeiro Teorema de Godel
Se um sistema formal Z e sucientemente poderoso para
representar todos os conjuntos recursivos, ent~ao Z e inconsistente
ou incompleto.
Demonstrac~ao:Por hipotese todo conjunto pode ser representado
em Z, ent~ao, pelo Teorema 1F, Z e indecidvel e, portanto, pelo
Teorema 2F, Z e inconsistente ou incompleto.
27 / 28

31. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
Conclus~oes
Ate hoje se especula as implicac~oes dos Teoremas da
Incompletude na matematica e na losoa.
Godel discute exaustivamente em seus trabalhos posteriores
quest~oes que variam, desde o conceito de intelig^encia ate a
exist^encia de Deus (argumento ontologico de Godel).
Em teoria da computabilidade: os teoremas s~ao relacionados a
varios resultados
Stephen Cole Kleene (1947) mostrou que se a aritmetica fosse
consistente e completa isto forcaria o problema da parada a ser
decidvel, o que implica em uma contradic~ao.
Sempre havera mais coisas que s~ao verdadeiras do que se
pode provar;
Todos os sistemas fechados dependem de suposic~oes feitas
fora do sistema e que n~ao podem ser provadas;
28 / 28

32. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
[1] Modelos de computac~ao e sistemas formais.
DCC/IM, COPPE/UFRJ, NCE-UFRJ, 1998.
[2] Computational complexity - a conceptual
perspective. Cambridge University Press, 2008.
[3] Mathematische Probleme, ser. Archiv der
Mathematik und Physik, M. W. English Translation, Ed.
Bulletin of the American Mathematical Society 8, 1901, vol. 3,
no. 1. [Online]. Available:
http://aleph0.clarku.edu/
djoyce/hilbert/problems.html
[4] Introduction to
automata theory, languages, and computation.
Addison-wesley Reading, MA, 1979, vol. 2.
[5] Mathematical logic. Dover publications, 2002.
28 / 28

33. Teoremas da Incompletude de Godel
Prova usando Sistemas de Representac~ao Abstratos
[6] Introduc~ao a teoria da
computac~ao. Thomson Learning, 2007.
[7] Five Thousand BC and Other Philosophical
Fantasies. St. Martin's Press, 1983.
[8] Principia mathematica.
University Press, 1912, vol. 2.
28 / 28