Download "un lenguaje de" -gnu -else -tarde

Teoremas de
Completitud e Incompletitud
de Gödel
Roberto Moriyón
Teorema de completitud de
Gödel
• Todas las consecuencias de un conjunto
de axiomas se deducen de él.
• La afirmación inversa (todas las fórmulas
que se deducen de un conjunto de
axiomas son consecuencias de él) es el
teorema de coherencia.
• Ya los hemos demostrado en el caso más
sencillo de la Lógica proposicional.
Teorema de Coherencia de la
Lógica de Predicados
• Al igual que en la Lógica Proposicional, es
consecuencia de que en todas las reglas
de deducción, de la forma AB, B es
consecuencia de A.
Recordatorio: Demostración del
Teorema de Completitud proposicional
• Primer paso: Si un conjunto de axiomas
es inconsistente, entonces todas sus
consecuencias se deducen de él.
• Segundo paso: Si un conjunto de axiomas
es consistente maximal, entonces todas
sus consecuencias se deducen de él.
• La demostración del Teorema de
Completitud de Gödel se basará en dos
pasos análogos.
Recordatorio: Inconsistencia
• A  G v ~G

Recordatorio: Inconsistencia
• A  G v ~G  F

(F cualquiera)
Teorema de completitud de Gödel
para axiomas inconsistentes
• Todas las fórmulas se deducen de los
axiomas si éstos son inconsistentes
– Se debe a que, como consecuencia de la
regla de deducción de implicaciones, de una
contradicción se deduce cualquier fórmula
• Todas las fórmulas son consecuencia de
los axiomas si éstos son inconsistentes
– Se debe a que todas las fórmulas que se
deducen a partir de A son consecuencia de A
Recordatorio: Conjuntos
consistentes maximales
• Un conjunto de fórmulas es consistente
maximal si al añadirle cualquier otra
fórmula deja de ser consistente.
• Por ejemplo, las fórmulas ciertas en una
interpretación cualquiera forman un
conjunto consistente maximal.
Recordatorio: Conjuntos
consistentes maximales, II
• En la Lógica Proposicional:
– Si A es consistente maximal, las fórmulas de
A son las únicas que se deducen de A
– Si A es consistente, entonces es maximal si y
solamente si GA  ~GA
– A es consistente maximal si y solamente si
A corresponde a una interpretación
– De lo anterior se deduce el Teorema de
Completitud para conjuntos de axiomas
consistentes maximales
Conjuntos consistentes maximales
en la Lógica de Predicados
• Los dos últimos puntos no se verifican en
la Lógica de Predicados, pues un conjunto
de fórmulas no determina una
interpretación: hace falta un dominio y una
interpretación en el dominio de cada
símbolo de constante, función y predicado
• Los puntos anteriores son válidos, y se
demuestran como en la Lógica
Proposicional
Dominio sintáctico asociado a
un lenguaje lógico
• El dominio sintáctico asociado a un
lenguaje de la Lógica de Predicados es el
conjunto formado por los términos sin
variables del lenguaje.
• Ejemplo: El modelo sintáctico de un
lenguaje con un símbolo constante, 0, y
otro de función, f (unaria) es
D={0,f0,ff0,…}.
Interpretación natural simple de
una teoría lógica
• La interpretación natural simple asociada
a una teoría lógica tiene como dominio a
su dominio sintáctico. La interpretación de
los símbolos de constante y función es
puramente sintáctica (no depende de
cuáles sean los axiomas de la teoría): las
constantes se interpretan como ellas
mismas (cI=c) y las funciones actúan
simbólicamente sobre n-plas de términos:
fI(T1, …, Tn) = fT1…Tn.
Interpretación sintáctica de una
teoría lógica, II
En el ejemplo de un lenguaje con un
símbolo constante, 0, y otro de función, f
(unaria) la interpretación natural simple de
estos símbolos es la siguiente:
– 0I = 0,
– fI:DD es la función definida por fI(fk)0)=fk+1)0
Por ejemplo, fI(fff0)=ffff0.
Interpretación natural simple de
una teoría lógica, III
• La interpretación natural simple de los
símbolos de predicado de una teoría
lógica es la que corresponde a la validez
de cada término dependiendo de los
axiomas: si P es un símbolo de predicado
n-ario y T1, …, Tn son términos
cualesquiera, PI(T1, …, Tn) es cierto si
PT1…Tn es un teorema de la teoría.
Interpretación natural simple de
una teoría lógica, IV
• Ejemplo: En la interpretación natural
simple de la teoría lógica con símbolos 0
(constante), f (función unaria) y P y
axiomas
-
x,Pxx
x,y,(PxyPyx)
x,y,z,(Pxy^PyzPxz)
x,Pxffx,
PI (fk)0, fh)0) es cierto si y sólo si k-h es par
Interpretación natural simple de
una teoría lógica, IV
• Si los axiomas incluyen igualdades, la
interpretación natural simple de una teoría
puede no ser un modelo.
• Por ejemplo, en la interpretación natural
simple de la teoría lógica con símbolos 0 y
f y axioma x,x=ffx, el dominio sintáctico
es D0={0,f0,ff0,…} y la interpretación de la
fórmula 0=ff0 es falsa a pesar de que la
fórmula es un teorema.
Dominio natural asociado
a una teoría lógica
• El problema anterior se evita mediante el
cociente del dominio sintáctico por una
relación de equivalencia.
• El dominio natural asociado a una teoría
es el cociente del dominio sintáctico por la
relación de equivalencia T S si y sólo si
AT=S
Dominio natural asociado a una
teoría lógica, II
• Ejemplo:
El dominio natural de la teoría lógica con
símbolos 0 y f y axioma x,x=ffx es el
cociente del dominio sintáctico D0={0,f0,ff0,…}
por la relación de equivalencia
fj)0  fk)0  k-j es un número par.
El conjunto cociente D=D0/={[0],[f0]} es un
modelo de la teoría con la interpretación
0I=[0], fI([fk)0])=[fk+1)0].
Interpretación natural asociada
a una teoría lógica
• La interpretación natural simple de una
teoría lógica da lugar a otra interpretación
sobre el dominio natural, que llamamos
interpretación natural. Por cada símbolo
de constante c, de función f y de
predicado P,
– cI = [cI].
- fI([T1], …, [Tn]) = [fT1…Tn].
– PI([T1], …, [Tn]) es cierto si PT1…Tn es un
teorema de la teoría.
Interpretación natural asociada
a una teoría lógica, II
• La interpretación natural de la Aritmética
es la siguiente:
• Los elementos del dominio sintáctico son
expresiones numéricas construidas a
partir del 0 y las operaciones S, + y .,
como S0+(S0.0).
• En la relación de equivalencia inducida
por los axiomas de la Aritmética todas las
expresiones numéricas son equivalentes a
otra de la forma Sn0. Por ejemplo,
S0+(S0.0)  S0.
Interpretación natural asociada
a una teoría lógica, III
• Como consecuencia de lo anterior, el
dominio natural es D={[Sn0] | n0} y la
interpretación natural es
– 0I = [0]
– SI[Sn0]  [Sn+10]
– [Sn0]+I[Sm0]  [Sn+m0]
– [Sn0].I[Sm0]  [Sn.m0]
• La interpretación anterior da lugar al
modelo estándar de la Aritmética. La
interpretación natural de la semiótica
también es la estándar.
Interpretación natural asociada
a una teoría lógica, IV
• La construcción anterior no nos
proporciona un modelo de una teoría si
ésta contiene axiomas existenciales. Por
ejemplo, la teoría que tiene como único
axioma x,x=x, que admite como modelo
a cualquier conjunto no vacío, tiene como
dominio natural al conjunto vacío, que no
es un modelo de la teoría.
Eskolemización
• El problema anterior se puede solucionar
considerando un símbolo adicional c que se
interpreta como el elemento del dominio final a
construir D que existe según el axioma y que
verifica que c=c.
• Para integrar esta idea con la construcción
anterior del dominio mínimo, el símbolo c se
puede introducir como constante de una lógica
extendida, y junto al axioma x,x=x se puede
considerar el nuevo axioma c=c.
• La idea anterior permite construir un modelo
mínimo, D={c}.
Eskolemización, II
• Análogamente, para poder interpretar un axioma
como y,x,~y=x, se puede extender la lógica
introduciendo un símbolo de función H y
añadiendo el axioma y,~y=Hy.
• Esta construcción se puede hacer con fórmulas
arbitrarias del tipo y1,y2,…yN,x,F. En este
caso se añade un símbolo de función N-aria J y
el axioma y1, y2,…yN,FJy1…yN/x.
• Los términos introducidos en los ejemplos (c,
Hy, Jy1,…,yN) se denominan testigos.
Normalización de cuantificadores
• A partir de cualquier fórmula lógica se
deduce otra equivalente a ella (normalizada)
sin implicaciones y que tiene todos los
cuantificadores en su parte exterior.
• Ejemplos (suponemos que las fórmulas son
simples):
– ~x,x+x=x equivale a x,~x+x=x.
– x,y,~((z,F)G) equivale a x,y,z,(F^~G).
Normalización de cuantificadores, II
• En general, las implicaciones de la forma
FG equivalen a ~FvG, y las negaciones
(~) se pueden pasar al interior de los
cuantificadores y operaciones lógicas
proposicionales mediante las reglas de
intercambio y De Morgan. Tras esto, las
reglas de ámbito permiten pasar los
cuantificadores restantes al exterior.
Fórmulas atestiguadoras
• Una fórmula FT es atestiguadora de otra F que
está en forma normal si se obtiene eliminando
todos los cuantificadores existenciales de F y
sustituyendo las correspondientes variables por
términos de la forma Jy1,…,yN, donde y1,…,yN
son las variables que afectan al cuantificador
existencial correspondiente mediante
cuantificadores universales.
• Los símbolos de funciones y constantes que se
introducen han de ser nuevos.
Fórmulas atestiguadoras, II
• Por ejemplo, una fórmula atestiguadora de la
fórmula lógica
F  x,y,z,u,(~x=y^~x=u^~y=u^~z=u)
es
FT  x,z,(~x=Hx^~x=Jxz^~Hx=Jxz^~z=Jxz).
En esta fórmula, Hx y Jxz son testigos de los
cuantificadores existenciales de y y u.
Fórmulas Atestiguadoras, III
• FTF, pero no al revés
• Ejemplo: F  x, y,~x=y, FT  ~c=d.
• Si A es consistente y FA, entonces
A{FT} también es consistente.
Fórmulas Atestiguadoras, IV
• Ejemplo:
Si Fx,y,~x=y, entonces FTx,~x=Jx.
Si A fuera consistente y A{FT} no lo
fuera, de A se deduciría ~FTx,x=Jx.
Como las fórmulas de A no contienen el
símbolo J, la deducción de ~FT introduciría
Jx en algún paso.
…
Fórmulas Atestiguadoras, V
…
Los únicos pasos en los que se pueden
introducir términos nuevos en una
deducción son al aplicar la regla de
especificación o en el primer paso de una
“deducción al margen” para su utilización
en la regla de deducción de implicaciones.
…
Fórmulas Atestiguadoras, VI
• En el primer caso, si la deducción de ~FT
introdujera Jx al utilizar la regla de
especificación, se podría hacer otra
deducción quitando esa regla y siguiendo
los mismos pasos de la deducción inicial,
deduciéndose ~F x,y,x=y. Esto es
imposible, pues entonces A sería
inconsistente.
Fórmulas Atestiguadoras, VII
• En el segundo caso, si la deducción de ~FT
introdujera Jx en el primer paso de una “deducción al margen” para su utilización en la
regla de deducción de implicaciones, se podría sustituir esta fórmula por otra con un
cuantificador existencia que la tuviera como
atestiguadora. Continuando como en el
caso anterior también se deduciría ~F
x,y,x=y, lo que de nuevo es imposible,
pues A sería inconsistente.
Fórmulas Atestiguadoras, VIII
• La demostración anterior se extiende al
caso de cualquier otra fórmula F.
Teorema de Satisfactibilidad
simplificado
• Si un conjunto de axiomas M es consistente maximal y con testigos, entonces
en la interpretación natural de la teoría
asociada a M las fórmulas ciertas son
precisamente las de M.
Teorema de Satisfactibilidad
simplificado: Demostración
• Por su definición, las fórmulas atómicas
(igualdades y predicados) pertenecen a M
si y sólo si son ciertas en la interpretación.
• ~FM si y sólo si FM, pues:
• Si ~FM y FM, M no sería consistente.
• Si FM, entonces MF (si no, M no sería
maximal), luego M{~F} es consistente, por lo
que ~FM.
Teorema de Satisfactibilidad
simplificado: Demostración, II
• Suponemos que FM si y sólo si FI es cierto y que lo mismo ocurre con G. Entonces:
– F ^ G  M si y sólo si FM y GM, pues en
caso contrario M no sería consistente maximal.
– F v G  M si y sólo si FM o GM, pues si
FM o GM y FvGM, M no sería consistente
maximal, e inversamente, si FvGM, FM y
GM, entonces ~F,~GM, por lo que
~(FvG)M y M no sería consistente.
Luego F^G y FvG tienen la misma propiedad.
Teorema de Satisfactibilidad
simplificado: Demostración, III
• De lo anterior, se deduce que las fórmulas
sin cuantificadores que pertenecen a M
son las que son ciertas en la
interpretación natural.
• Como consecuencia de las reglas de
generalización y de especificación, lo
mismo ocurre con todas las fórmulas que
en forma normal no tienen cuantificadores
existenciales.
Teorema de Satisfactibilidad
simplificado: Demostración, IV
• Por otra parte, como consecuencia de la
última observación sobre fórmulas
atestiguadoras, las fórmulas con
cuantificadores existenciales pertenecen a
M si y solamente si pertenece a M alguna
fórmula atestiguadora suya.
• El teorema simplificado de satisfactibilidad
es consecuencia de lo anterior.
Teorema de Completitud de
Gödel: Demostración
• Si A es un conjunto de axiomas y F es una
consecuencia de A, entonces F se puede
deducir a partir de A.
• Demostración:
– Ya hemos demostrado el caso particular en
que A es inconsistente.
– El caso en que A es consistente maximal y
con testigos es consecuencia del Teorema de
Satisfactibilidad simplificado.
–…
Teorema de Completitud de
Gödel: Demostración, II
• En general, si A es un conjunto consistente
de axiomas y F no se deduce de A, entonces
A{~F} es consistente. Veremos más adelante que entonces hay un conjunto de fórmulas M maximal consistente y con testigos
que contiene a A{~F}. Por lo tanto, hay una
interpretación de M en la cual ~F es cierta.
Restringiendo la interpretación a los símbolos de la Lógica inicial, se ve que F no es
consecuencia de A.
Teorema de Completitud de
Gödel: Demostración, III
• Si B es un conjunto consistente de
axiomas, entonces se puede ampliar su
conjunto de constantes y funciones,
definiendo una nueva teoría lógica en la
que hay un conjunto de fórmulas M
maximal consistente y con testigos que
contiene a B.
Teorema de Completitud de Gödel:
Demostración, IV
• La demostración de la afirmación anterior es
análoga al caso proposicional, excepto por la
incorporación de fórmulas atestiguadoras
adicionales.
• Se incorporan símbolos nuevos de funciones
de todos los órdenes Hn,k con n0 y k0.
• Si {Fj | j0} es una numeración de todas las
fórmulas de la nueva teoría, se va añadiendo
a B consecutivamente Fj si con ello el
conjunto ampliado de axiomas sigue siendo
consistente.
Teorema de Completitud de Gödel:
Demostración, V
• Además, en cada paso se añade una
fórmula atestiguadora correspondiente a
la fórmula Fj si finalmente Fj pertenece al
conjunto ampliado. Como consecuencia
de la última observación sobre fórmulas
atestiguadoras, cada conjunto Aj así
obtenido es consistente.
• Por construcción, el conjunto obtenido de
fórmulas es consistente maximal y con
testigos.
Teorema de satisfactibilidad de
la Lógica de Predicados
• Como consecuencia de la demostración
del Teorema de Completitud de Gödel
hemos demostrado lo siguiente:
Todo conjunto consistente de axiomas es
satisfactible.
Teorema de Incompletitud de
Gödel
• En cualquier teoría que incluya los axiomas
de la Semiótica y que sea compatible con
su modelo natural hay fórmulas que son
válidas en el mismo que no se pueden
demostrar y su negación tampoco.
Teorema de
Incompletitud de Gödel, II
• Las fórmulas anteriores son ciertas en el
sentido de que su interpretación natural
sobre cadenas de caracteres es cierta. Sin
embargo, ni ellas ni sus negaciones se
pueden demostrar. Esto no contradice el
Teorema de Completitud.
Teorema de Incompletitud de
Gödel, III
• Idea de la demostración: Hallar una
fórmula cerrada F cuyo significado en la
interpretación natural sea “F no tiene
demostración”.
Teorema de Incompletitud de
Gödel, IV
• Si la interpretación natural de F fuera
falsa, F tendría demostración, luego su
interpretación natural sería cierta.
• Por lo anterior, F no tiene demostración y
su interpretación natural es cierta.
• Si ~F tuviera demostración, sería cierta en
cualquier modelo de la Semiótica, luego F
sería falsa en la interpretación natural.
Preparativos para la
demostración del teorema
• El predicado D demuestra E es
computable. (D y E son variables).
• Como consecuencia del teorema de
representación, hay una fórmula , con
dos variables libres, d y e, cuya interpretación natural es “la demostración d
demuestra la fórmula representada por e”.
• La interpretación natural de la fórmula
d,~ es “e no tiene demostración.
Preparativos para la
demostración del teorema, II
• En lo sucesivo consideraremos fórmulas
con una variable libre. Les llamaremos
fórmulas parametrizadas.
• Corresponden en lenguaje natural a frases
sin sujeto.
• Ejemplos:
– empieza por a
x,y=Sax
– contiene “=S”
u,v,z=u+“=S”+v
– no tiene demostración d,~
Preparativos para la
demostración del teorema, III
• Las fórmulas parametrizadas definen
funciones que a cada cadena de caracteres
le hace corresponder una fórmula cerrada.
• En el lenguaje natural esta función asocia
un sujeto a la fórmula.
• Ejemplo: al aplicar la fórmula empieza por a
a la cadena “aaaaa” se obtiene “aaaaa”
empieza por a.
(Si F  x,y=Sax y G  “aaaaa”, entonces
FG  x,“aaaaa”=Sax).
Preparativos para la
demostración del teorema, IV
• En particular, la cadena de caracteres a la
que se aplica una fórmula parametrizada
puede ser otra fórmula.
• Ejemplo: Si F es contiene “=S” (F 
u,v,z=u+“=S”+v) y G es empieza por a
(G  x,y=Sax), entonces la aplicación de
F a G es
FG  u,v,“x,y=Sax”=u+“=S”+v.
Preparativos para la
demostración del teorema, VII
• La función que a dos fórmulas v y w (vistas
como cadenas de caracteres) les hace
corresponder la fórmula vw es recursiva, por
lo que se puede representar mediante una
fórmula , con tres variables libres, u, v y w,
cuya interpretación natural es “el resultado
de sustituir la variable libre de la fórmula
parametrizada u por la fórmula parametrizada v es la fórmula parametrizada w”.
Preparativos para la
demostración del teorema, VIII
• En este contexto, la demostración del
Teorema de incompletitud de Gödel se
reduce a la de un teorema del punto fijo
del tipo del de Turing: Buscamos una
fórmula cerrada F tal que F  (d,~)F.
Preparativos para la
demostración del teorema, IX
• La solución es totalmente análoga a la de
Turing: F es la aplicación de la fórmula G
a sí misma, donde G es la fórmula
parametrizada XX no tiene demostración,
pues al aplicársela a ella misma se
obtiene la fórmula GG no tiene
demostración.
Preparativos para la
demostración del teorema, X
• Solamente nos queda demostrar que hay
una fórmula parametrizada G cuya
interpretación natural es XX no tiene
demostración. Esto es fácil de obtener en
base a lo dicho anteriormente, pues basta
con tomar G d,~ ^e/w,u/v.
El Teorema de Incompletitud
para la Aritmética
• Gödel demostró su teorema de incompletitud
para la Aritmética.
• La demostración es análoga al caso de la
Semiótica, excepto que las fórmulas lógicas
no se representan mediante cadenas de
caracteres, sino que se codifican mediante
números utilizando la numeración de Gödel.
Lo mismo ocurre con las demostraciones y
con la representación de funciones
recursivas totales.
Comentario
• La demostración del teorema de
representación de Gödel es constructiva
en el sentido de que da una fórmula
concreta que no se puede demostrar así
como su negación.
• La fórmula construida en la demostración
depende del conjunto de axiomas, pues la
fórmula  que representa al predicado d
demuestra f depende del mismo.
Consecuencias del
Teorema de Incompletitud
• El conjunto de fórmulas de la Aritmética (o
de la Semiótica) ciertas en la interpretación
estándar (o en otra) no es computable.
• Demostración: Si lo fuera, formaría un
conjunto computable consistente maximal
de axiomas que contendrían a los
habituales, y cualquier fórmula o su
negación sería uno de ellos, por lo que no
tendría fórmulas indecidibles.