Download Teorema de Gödel

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)