Teorema De Godel.ppt

Teorema de Gödel

Qué es una demostración TEOREMA

AB es un segmento   un punto C tal que AB  AC  BC DEMOSTRACIÓN

AB es un segmento AB es un segmento  A es un punto  B es un punto

A es un punto  B es un punto

A es un punto A es un punto  AB es un segmento A es un punto  AB es un segmento   un círculo con centro A que pasa por B  un círculo con centro A que pasa por B ……….  un punto C tal que AB  AC  BC

AB es un segmento   un punto C tal que AB  AC  BC

Qué es una demostración TEOREMA

Y:

AB es un segmento   un punto C tal que AB  AC  BC

DEMOSTRACIÓN

AB es un segmento AB es un segmento  A es un punto  B es un punto

A es un punto  B es un punto

A es un punto A es un punto  AB es un segmento A es un punto  AB es un segmento   un círculo con centro A que pasa por B  un círculo con centro A que pasa por B

X

……….  un punto C tal que AB  AC  BC

AB es un segmento   un punto C tal que AB  AC  BC

Dem(X,Y) es verdadero

Axiomatización de los Naturales

Peano (1889) Términos básicos: número, 1, sucesor 1. 1 es un número 1  N 2. Para todo número n existe otro número Sn llamado el sucesor de n. n  N Sn  N 3. 1 no es el sucesor de ningún número n (Sn  1) 4. Si Sn= Sm entonces n = m nm Sn  Sm  n  m 5. Adición – Para todo n, n+1 = Sn n(n  1  Sn) – Para todo n, m, n+Sm = S(n+m).nm n  Sm  S(n  m)  6. Multiplicación – Para todo n, n·1 = n n(n  1  n) – Para todo n, m, n·Sm = n·m+n nm n  Sm  (n  m  n) 

Demostración Teorema de Lógica: xA  xA 1. xA  A 2. xA  A

axioma 1 axioma 1

3. xA  A   A  xA axioma p  q   q  p  regla modus ponens 2 y 3 4. A  xA definición xA  xA 5. A  xA 6. xA  A   A  xA regla conjunción 1 y 5

axioma 7. xA  A   A  xA  xA  xAp  q   q  r    p  r  regla modus ponens 6 y 7 8. xA  xA

Conclusión xA  xA

Ambición de la Escuela Formalista • De la Teoría Axiomática de Conjuntos con los Axiomas de la Lógica (Russell) se deduce toda la matemática (casi) • Utilización de símbolos para no equivocarse– Sistema Formal: Teoría Formal de Conjuntos • ¿La matemática se reduce a un juego de símbolos?

Respuesta de los Intuicionistas • Nos rehusamos a que la matemática se reduzca a un juego de símbolos • La matemática tiene como base la intuición, como en los números naturales (Platón) • No estamos de acuerdo con la teoría de los Reales ni con la de Conjuntos, por su uso del infinito “actual”

• No estamos de acuerdo con la lógica de Russell, por su uso del “Tercio Excluso”

Propuesta de Hilbert • Tarea: Utilizar lógica intuicionista para demostrar completitud y consistencia de la Teoría Formal de Conjuntos • Consistencia - no lleva a contradicciones • Completitud - todas las verdades se pueden demostrar

Kurt Gödel (Austria 1906-Princeton 1978) 1931 Teorema de Incompletitud “El Sistema Formal de los Números Naturales es incompleto”

Su demostración se basa en analizar la afirmación: “Esta afirmación no se puede demostrar.”

Completitud Completo q

~p

Incompleto q

~q Verdadero = Demostrable

~p

~q Verdadero

p

r p

~r Falso

Falso

La Metamatemática

• Tres niveles

Meta-Aritmética: Lenguaje del entendimeinto (Intuicionista). Nos va a decir si la Aritmética está bien hecha. Si es consistente.

Aritmética Formal: sólo fórmulas lógicas que representan funciones, afirmaciones, cadenas de demostraciones sobre números

Números: Naturales únicamente MC Escher (1955)

Codificación de Gödel Símbolos

1. 2. 3. 4. 5. 6. 7. 8.

  

 

( ) S 9. 1 10. = 11.  12. +

Predicados

13. 16. 19. 22.

P Q R T

Variables

14. 17. 20. 23.

Proposiciones

n m x y

15. E 18. F 21. G ……

Número de Gödel

n (Sn  1) 22314517611813141710199237 Decodificación: 3280500000000 = 283859 que corresponde a

SS1 ó 3

Demostración 1. xA  A 3. xA  A   A  xA

m1 m1 m3

4. A  xA

m4

5. A  xA 6. xA  A   A  xA

m5 m6

2. xA  A

7. xA  A   A  xA  xA  xA m7 m8 8. xA  xA m8 Conclusión xA  xA Dem( x, y )  Dem(2m1 3m2 5m3 7m411m513m617m719m8 , m8 )

es verdadero en este caso

Desenlace • Dem( x, y ) es una función de la aritmética; si x, y son números, es Verdadera o Falsa. • x Dem( x, y ) también, si y es un número • Po un proceso de “diagonalización” Gödel muestra que existe un número G tal que G es el número de Gödel de x Dem( x, G) • x Dem( x, G) es una afirmación de la aritmética • ¿Es Verdadera o Falsa? • ¿Qué significa esto?

El método de Gödel • Reflejar la Meta-Aritmética en la Aritmética y la Aritmética en los números

Meta-Meta-Aritmética interpretar

Meta-Aritmética Aritmética

reflejar

Números

René Magritte (1930)