Godel (-) (Para Todos) - Guillermo Martinez
Godel (-) (Para Todos) - Guillermo Martinez
Godel (-) (Para Todos) - Guillermo Martinez
INTRODUCCIN
www.godelparatodos.blogspot.com
Pondremos all tambin en forma completa
algunos de los textos citados que debimos
resumir para el formato libro, y tambin distintos
artculos de la bibliografa que nos resultaron
particularmente interesantes.
Queremos finalmente agradecer a Xavier
Caicedo
por
varias
conversaciones
y
explicaciones esclarecedoras sobre puntos
delicados de la teora y tambin la lectura final
generosa y atenta de Pablo Coll, Gisela Serrano y
Pablo Amster.
Para esta nueva edicin espaola quisiramos
agradecer tambin los comentarios y aportes de
Vernica Becher, Roberto Cignoli, Cristian
Caravello, Mximo Dickmann, Francisco
Espinosa, Javier Fresn, Hernn Gonzlez,
Toms Ibarluca, Mara Celia Ibarra, Pablo
Kaczor, Laureano Luna, Luciano Robino y Enzo
Tagliazucchi.
PRIMERA PARTE
CAPTULO UNO
UN PANORAMA GENERAL
Lo verdadero y lo demostrable. Los sistemas
axiomticos formales. Completitud y axiomas. El
infinito: La bte noire en los fundamentos de la
matemtica. El Teorema de Incompletitud. La prueba
original de Gdel. El Teorema de Consistencia.
Extensin y alcance del Teorema de Gdel.
Precauciones. Gdel, las computadoras y la
inteligencia artificial. Derivaciones filosficas.
Ejemplos y ejercicios.
1. LO VERDADERO Y LO DEMOSTRABLE
El Teorema de Incompletitud de Gdel trata
de la verdad en matemtica y de la parte de
verdad que puede ser comprobada a partir de
axiomas, en esos fragmentos de texto de lneas
sucesivas encadenadas por pasos lgicos que los
matemticos llaman demostracin.
En otras disciplinas del conocimiento
siempre ha sido claro que lo verdadero no
necesariamente coincide con lo demostrable.
Imaginemos, para dar una analoga con la
justicia, que se comete un crimen en un cuarto
cerrado y que el juez de instruccin, al llegar,
encuentra que hay nicamente dos sospechosos
junto al cadver.
3. COMPLETITUD Y AXIOMAS
Histricamente, la nocin de axioma estuvo
primero asociada a la nocin de verdad, y a la
posibilidad de seleccionar, en cierta rea u objeto
propsito es imposible:
En lo que sigue mostraremos que esto no
es as, sino que ms bien, en ambos
sistemas, existen problemas relativamente
simples de la teora elemental de nmeros
naturales que no pueden ser decididos
sobre la base de los axiomas.
De esta manera, la situacin entre lo
verdadero y lo demostrable en el terreno de la
aritmtica elemental es anloga a la del crimen
con dos sospechosos en el cuarto cerrado:
cualquiera que sea el sistema axiomtico
(recursivo) propuesto, habr enunciados que
quedan fuera del alcance del mtodo de
demostracin, enunciados que para el sistema
son indecidibles, en el sentido de que no puede
demostrarse ni su verdad ni su falsedad, ni su
inocencia ni su culpabilidad. Dicho de otro
modo, la verdad no puede reducirse enteramente
5. EL TEOREMA DE INCOMPLETITUD
Hemos dicho que un conjunto de enunciados
verdaderos seleccionados como axiomas es
completo
si
pueden
reobtenerse,
va
demostraciones, como teoremas, todos los
enunciados verdaderos del rea o del objeto que
nos proponemos axiomatizar.
Hay, sin embargo, una segunda definicin de
completitud que prescinde de la nocin de
verdad, y que es la que us Gdel para enunciar
su teorema. De acuerdo con esta definicin un
como:
Esta afirmacin ma es falsa.
Esta frase, que es en s misma una
afirmacin, no es ni verdadera ni falsa. En efecto,
si fuera verdadera, de acuerdo con lo que dice,
sera falsa, y si fuera falsa, otra vez por lo que
afirma, sera verdadera.
Los lgicos Bertrand Russell y Alfred
Whitehead haban propuesto eludir esta clase de
paradojas imponiendo la restriccin de que los
enunciados no pudieran referirse a s mismos
(esto es, que no pudieran afirmar nada de s
mismos). En el caso de la frase de Epimnides, la
afirmacin se refiere a s misma, para decir de s
misma que es falsa.
Pero, tal como seala Gdel, esta restriccin
total de la autorreferencia es demasiado drstica,
porque se puede establecer, con una sencilla idea
matemtica, una manera libre de paradojas en
que los enunciados pueden expresar distintas
propiedades de s mismos.
Esto es justamente lo que hizo Gdel en su
teorema
fundamental:
estableci
una
correspondencia entre enunciados del lenguaje y
nmeros naturales, de tal manera que a cada
enunciado se le asigna un nico nmero, que es
su cdigo de identidad. Conocido el nmero,
puede saberse exactamente de qu enunciado
proviene, de la misma manera que el nmero de
documento permite identificar sin ambigedad a
cada persona. Ahora bien, al mirar los
enunciados como nmeros, Gdel logr expresar
en el lenguaje de la aritmtica, utilizando slo las
operaciones de suma y multiplicacin, distintas
propiedades sobre los enunciados como
relaciones aritmticas entre nmeros. En
particular, prob que para cada conjunto
recursivo de axiomas propuesto, el hecho de que
un enunciado sea demostrable a partir de esos
axiomas puede ser expresado con una frmula en
el lenguaje de la aritmtica. Y, por lo tanto,
7. EL TEOREMA DE CONSISTENCIA
Am
donde cada uno de estos axiomas est escrito con
una cantidad finita de smbolos.
Dado ahora un enunciado E cualquiera, E
tambin tiene una cantidad finita de smbolos.
Chequeamos los smbolos de E uno a uno con los
de A1. Si hay ms o menos smbolos, o no hay
coincidencia perfecta, proseguimos el chequeo
E1 E2 E3
E1
E2
E3
Primera fila:
(enunciados)
Segunda fila:
(sucesiones de
dos enunciados)
Tercera fila:
(sucesiones de
tres enunciados)
Cuarta fila:
(sucesiones de
cuatro enunciados)
nmeros naturales).
Este ejercicio permite concluir que todos los
textos escritos y por escribir desde el inicio de la
escritura hasta el fin de los tiempos, en cualquier
idioma, no pueden sobrepasar el infinito de los
nmeros naturales. (Vase el Apndice I,
Ejemplo 5, sobre otros infinitos ms grandes).
Resolucin: Un alfabeto numerable ser un
conjunto de smbolos (las letras), que podemos
notar S1, S2, S3,
Las palabras de dos letras se obtienen por
concatenacin de dos smbolos, es decir,
escribiendo un smbolo a continuacin del otro, y
pueden listarse de este modo: S1S1, S1S2, S2S1,
S1S3, S2S2, S3S1,
Observemos que esto no es ms que el listado
que da el mtodo diagonal de Cantor. Probamos
as que el conjunto de palabras de dos letras es
numerable. De la misma manera puede probarse
(asociatividad)
(2) x + 0 = x
0+x=x
(existencia de
elemento neutro)
(3) y(x + y = 0
y + x = 0)
(existencia de
elemento inverso
para +)
(4) x + y = y + x
(conmutatividad)
(6) x (y z) = (x y) z (asociatividad de )
(7) x y = y x
(conmutatividad de )
(8) x (y + z) =
(x y) + (x z)
(distributividad de
sobre +)
(9) x y = 0
(x = 0 y = 0)
(10) x 0
y(y x = 1)
(11n) n1 0
(existencia de
elemento inverso
para )
(una lista infinita de
axiomas: 1 0;
1 + 1 0; etc.)
(12n) y(x yn + x
n1 + + x y +
n
n1 y
1
x0 = 0) xn = 0
Una paradoja?
Sabemos que los nmeros naturales son un
subconjunto de los nmeros complejos y pueden
obtenerse como 1, 1 + 1, 1 + 1 + 1, etctera. Ms
an, las operaciones de suma y producto que
definimos ms arriba, restringidas a este
subconjunto, coinciden con la suma y el producto
habitual de nmeros naturales. Contradice acaso
esto lo que hemos dicho sobre la extensin del
Teorema de Gdel y el fenmeno de
incompletitud a los sistemas donde pueden
definirse los nmeros naturales con las
de la izquierda de la igualdad).
Afirmacin 7: El factor primo 2 aparece una
cantidad par de veces en el nmero a2. (Sigue
inmediatamente de las afirmaciones 5 y 6).
Afirmacin 8: En 2b2 (el miembro de la
izquierda en la igualdad (*)) el factor primo 2
aparece una cantidad impar de veces. En
efecto, si el factor primo 2 aparece en el
nmero b2 lo har, por las razones ya vistas,
un nmero par de veces, y con el primer 2
que aparece como factor la cantidad total de
veces se incrementa en uno y cambia la
paridad, de modo que la cantidad total de
veces que aparece el factor 2 en el miembro
izquierdo ser impar. (Si 2 no aparece en la
factorizacin de b2, la cantidad total de
apariciones del factor 2 ser 1, que tambin
es impar).
CAPTULO DOS
HILBERT Y EL
PROBLEMA DE LOS
FUNDAMENTOS
El programa de Hilbert. Discusin: Qu dicen y qu
no dicen los teoremas de Gdel. Ejemplos y
ejercicios.
El nombre de la cancin se
llama Ojos de bacalao dijo el
Caballero Blanco.
As que se es el nombre de la
cancin, no? pregunt Alicia,
que
comenzaba
a
sentirse
interesada.
No, veo que no me entiende. As
es como se llama el nombre. El
nombre en realidad es El hombre
viejo viejo.
LEWIS CARROLL
A travs del espejo
La Paradoja de Russell
Los conjuntos, por lo general, no son
elementos de s mismos: el conjunto de
todos los nmeros no es en s mismo un
nmero, el conjunto de todos los alumnos
de una clase no es en s mismo un alumno
de la clase. Sin embargo, pueden
absolutamente
mecnico,
que
pueda
implementarse en una computadora, debe
explicitarse tambin, en forma sintctica, como
axiomas agregados, y como marco general de
toda teora, la lgica que se emplea en los
razonamientos matemticos. Esto incluye a los
axiomas puramente lgicos, como el principio de
tercero excluido (o bien vale una afirmacin, o
bien su negacin es vlida), y las reglas de
deduccin lgica, llamadas reglas de inferencia,
que se emplean para pasar de una lnea en la
demostracin a la siguiente. Un ejemplo tpico es
lo que se llama la regla de modus ponens: si en
una lnea est escrito un enunciado del tipo
A B y en alguna lnea posterior aparece el
enunciado A, la regla dice que puede escribirse a
continuacin, como una derivacin lgica, el
enunciado B.
Un resultado fundamental de la lgica,
debido tambin a Gdel (su tesis doctoral,
publicada como La suficiencia de los axiomas del
1. EL PROGRAMA DE HILBERT
La preocupacin fundamental que da origen
al programa de David Hilbert es la cuestin de
cmo manipular con reglas lgicas los conjuntos
infinitos pensados como totalidades acabadas,
por ejemplo, la totalidad de los nmeros
naturales, o la totalidad de los puntos de un
segmento. Esto es lo que se llama el infinito
actual, en contraposicin con el infinito
potencial, que se corresponde con la idea de un
conjunto que puede ampliarse tanto como se
quiera (para cada nmero n puede encontrarse
La eleccin, la interpretacin y la
manipulacin de los axiomas no pueden
estar basadas simplemente en la buena fe
y en lo que nuestras creencias nos
indiquen. Tanto en la geometra como en
la fsica es posible dar pruebas de
consistencia relativa. Esto es, de reducir
el problema de la consistencia en esas
esferas a la consistencia de los axiomas
de la aritmtica. Pero es evidente que no
tiene sentido buscar una demostracin de
ese tipo [consistencia relativa] para la
aritmtica misma. En la medida en que
nuestra teora de la demostracin, basada
en el mtodo de los elementos ideales,
hace posible este ltimo y decisivo paso,
constituye una especie de punto final
necesario en la construccin del edificio
de la teora axiomtica. Y lo que ya
hemos tenido que padecer en dos
ocasiones, primero con las paradojas del
clculo infinitesimal y luego con las
2. DISCUSIN: QU DICEN Y QU NO
DICEN LOS TEOREMAS DE GDEL
Qu dicen y qu no dicen los teoremas de
Gdel? Nos proponemos aqu revisar algunos de
los malentendidos ms frecuentes en relacin con
el enunciado y los alcances de los teoremas de
Incompletitud y Consistencia.
1. El Teorema de Gdel establece un lmite a las
pretensiones de la razn humana.
Falso. Ya hemos dicho que el propio Gdel
afirm que tanto su teorema como los resultados
de Turing, no establecen ningn lmite para los
poderes del razonamiento humano, sino ms bien
para las potencialidades del formalismo puro en
matemtica.
Por supuesto, tampoco debe entenderse la
frase de Gdel en el sentido opuesto, como una
(vase [Matijasevich]).
El Teorema de Gdel inaugur tambin toda
una rama de la matemtica alrededor de los
mtodos de decisin y la prueba de Gdel ha
incorporado una idea importante que se ha
utilizado en una multitud de trabajos: la
utilizacin de la autorreferencia a travs de la
codificacin de enunciados.
3. EJEMPLOS Y EJERCICIOS
Ejercicio 2.1: Probar la siguiente proposicin:
Proposicin: Si un conjunto de axiomas es
recursivo, toda demostracin a partir de los
axiomas es corroborable en una cantidad
finita de pasos.
Demostracin: Imaginemos que nos dan una
CAPTULO TRES
EL LENGUAJE PARA LA
ARITMTICA
Y LA DEFINICIN DE
VERDAD
El lenguaje formal. Los enunciados. Los axiomas y
reglas de inferencia de la lgica de primer orden.
Demostraciones y teoras. La verdad en matemtica:
una definicin formal. Completitud y consistencia en
nuestra teora formal. La solucin de un dilema.
Ejercicios.
Mefistfeles.
Aproveche
el
tiempo, pasa tan pronto! Pero
el mtodo le ensear a ganarlo.
Para ello, querido amigo, le
aconsejo ante todo el Collegium
Logicum. All se adiestrar bien su
espritu,
aprisionado
borcegues espaoles
en
GOETHE
Fausto
1. EL LENGUAJE FORMAL
Las distintas operaciones lgicas pueden
expresarse con los smbolos que detallamos a
continuacin, y que incluimos en nuestro
lenguaje formal:
es el cuantificador universal y
significa Para todo.
es el cuantificador existencial y
significa Existe algn.
: es la implicacin; P Q significa
Si P entonces Q.
: es la disyuncin, P Q significa
P o Q.
: es la conjuncin, P Q significa
P y Q.
: es la negacin, P significa no P.
P Q equivale a (P Q);
P Q equivale a P Q;
xP equivale a xP.
La aritmtica trata de los nmeros naturales
(que son los que usamos para contar: 0, 1, 2, 3, 4,
), con las operaciones bsicas de suma y
multiplicacin tal como se ensean en el colegio
primario. Algunas afirmaciones, o enunciados,
tpicos de la aritmtica son:
Dos ms dos es cuatro.
La suma de dos nmeros pares es un
nmero par.
Todo nmero mayor que uno es divisible
por algn nmero primo.
Sabemos tambin que los nmeros naturales
pueden obtenerse a partir del 0 contando de uno
en uno. En otras palabras, el conjunto de los
nmeros en negrita: 0, 1, 2, 3,
Por otra parte, dado que la teora trata de la
suma y el producto, el lenguaje deber contener a
los smbolos +, , =, que representan la suma, el
producto y la igualdad, respectivamente.
Con los smbolos hasta aqu definidos ya
podemos traducir al lenguaje formal la primera
de las dos afirmaciones que escribimos ms
arriba. Dos ms dos es cuatro se traduce como:
SS0 + SS0 = SSSS0, o bien, con las
abreviaturas, como 2 + 2 = 4.
La segunda afirmacin: La suma de dos
nmeros pares es un nmero par, ya no se refiere
a dos o tres nmeros especficos, sino que habla
simultneamente de una infinidad de nmeros.
La suma de dos nmeros pares es un nmero par
quiere decir que 2 + 2 es par, 2 + 4 es par,
4 + 2 es par, 4 + 4 es par, 4 + 6 es par y
as sucesivamente.
Para capturar esta infinitud en una sola
como
variables
numeradas
de
esta
forma:
v3 (v1 = 2v3). Utilizaremos como abreviatura
Par(v1) para la expresin v3 (v1 = 2v3) y
Par(v2) para la expresin v3 (v2 = 2v3).
Ahora s, estamos listos para escribir en
nuestro lenguaje formal la segunda de las
afirmaciones: La suma de dos nmeros pares es
un nmero par:
v1v2 (Par(v1) Par(v2) Par(v1 + v2))
Finalmente, para escribir la tercera de las
afirmaciones, recordemos que un nmero x es
primo si es mayor que 1 y no tiene divisores
propios, es decir, si aparece escrito como
producto de dos nmeros y, z, uno de estos
nmeros tiene que ser x (y el otro el nmero 1).
Podemos definir entonces Ser primo en
nuestro lenguaje mediante la frmula
Pr(x): (x = 0) (x = 1) yz(yz = x
(y = x z = 1) (y =1 z = x))
La tercera de las afirmaciones: Todo
nmero mayor que 1 es divisible por algn
primo, puede escribirse ahora en el lenguaje
formal como
x((x = 0) (x = 1) yz (Pr(y) x
= y z))
2. LOS ENUNCIADOS
Todas las afirmaciones del lenguaje formal
pueden escribirse utilizando solamente los
siguientes doce smbolos:
S 0 +
1. Identificamos
ciertas
frmulas
elementales: las ecuaciones o
identidades que resultan de igualar
dos trminos.
2. A partir de estas frmulas
elementales, que hemos llamado
atmicas, obtenemos todas las
frmulas por aplicacin reiterada de
los conectivos lgicos y los
cuantificadores.
Notemos ahora que tenemos todava que
distinguir cules son entre las frmulas aquellas
a las que podemos asignarles un valor de verdad
(verdadero o falso). stas son realmente las
frmulas que nos interesan: las afirmaciones, o
enunciados. En efecto: no toda frmula es una
afirmacin. Para entender esto, observemos que a
la segunda frmula atmica que dimos como
ejemplo:
L1: P (Q P)
ste es en realidad un esquema de axioma, es
decir, no estamos dando un axioma especfico
sino la forma general de una familia infinita de
axiomas, cada uno de los cuales se obtiene
reemplazado a P y a Q por enunciados, o ms en
general por frmulas especficas. La misma
aclaracin vale para los axiomas L2 y L3:
L2: (P (Q R)) ((P Q)
(P R))
L3: (P Q) (Q P)
El siguiente es el axioma L4:
L4: xP(x) P(xt)
Como los anteriores, ste es un esquema de
axioma, pero requiere alguna explicacin
L8: x = y (y = z x = z)
L9: x = y t(v1, vi1, x, vi+1, vn) =
t(v1, vi1, y, vi+1, vn) donde t es un
trmino cualquiera.
L10: x = y ((v1, vi1, x, vi+1, vn)
(v1, vi1, y, vi+1, vn)) donde es
una frmula atmica cualquiera.
Si bien estos diez esquemas definen lo que es
en realidad un conjunto infinito de axiomas (ya
que es infinito el nmero de posibles reemplazos
por frmulas y trminos que corresponde a cada
esquema), este conjunto infinito es recursivo
porque dada una frmula cualquiera, es siempre
posible determinar en una cantidad finita de
pasos si corresponde o no a alguno de los diez
esquemas indicados. (Pensarlo!).
Fijados los axiomas lgicos, debemos
enunciar ahora las reglas de inferencia, que son
Axiomas lgicos:
L1: P (Q P)
L2: (P (Q R)) ((P Q)
(P R))
L3: (P Q) (Q P)
L4: xP(x) P(x/t) (Si las variables de t no
estn bajo cuantificadores en P)
L6: x = x
L7: x = y y = x
L8: x = y (y = z x = z)
L9: x = y t(v1 vi1, x, vi+1, vn) =
t(v1, vi1, y, vi+1, vn)
L10: x = y ((v1, vi1, x, vi+1, vn)
(v1, vi1, y, vi+1, vn))
Reglas de inferencia:
Regla de modus ponens: De P y de
(P Q) se deduce Q.
Regla de generalizacin: De P se deduce
xP.
4. DEMOSTRACIONES Y TEORAS
En el captulo 2 llamamos informalmente
teora a cualquier seleccin de afirmaciones,
propuestas como axiomas (en el Apndice I se
muestran algunos ejemplos concretos de teoras).
Los conceptos que hemos expuesto en este
captulo nos permiten precisar ms esta nocin.
(1) (0 = Sx)
(2) Sx = Sy x = y
(3) x + 0 = x
(4) x + Sy = S(x + y)
(5) x 0 = 0
(6) x Sy = (x y) + x
Axiomas de la
funcin
sucesor
Axiomas para
la suma
Axiomas para
el producto
5. x + Sy = S(x + y)
Modus ponens (de lneas 3 y 4)
Axioma
2. x(x + 0 = x)
Regla de
generalizacin
4. 1 + 0 = 1
Axioma de Peano
(3)
2. 1 + 0 = 1
Sustitucin de x
por el trmino 1
3. x + S(y) = S(x + y)
Axioma de Peano
(4)
4. x + S(0) = S(x + 0)
Sustitucin de y
por el trmino 0
5. 1 + S(0) = S(1 + 0)
Sustitucin de x
por el trmino 1
6. x = y S(x) = S(y)
Axioma de
igualdad (L9)
7. x = 1 S(x) = S(1)
Sustitucin de y
por el trmino 1
8. 1 + 0 = 1 S(1 + 0) =
S(1)
Sustitucin de x
por el trmino
1+0
9. S(1 + 0) = S(1)
Modus ponens
(de lneas 2 y 8)
Axioma de
igualdad L8
Modus ponens
(de lneas 5 y 10)
Modus ponens
(de lneas 9 y 11)
6. COMPLETITUD Y CONSISTENCIA EN
NUESTRA TEORA FORMAL
7. LA SOLUCIN DE UN DILEMA
Ya observamos en el Ejemplo 1.1 que la
teora de primer orden de los nmeros complejos
plantea un aparente dilema respecto al Teorema
de Gdel. En efecto, Gdel observ que si en una
teora cualquiera pueden definirse los nmeros
naturales junto con las operaciones de suma y
multiplicacin, entonces pueden desarrollarse los
argumentos de su demostracin para probar la
incompletitud de la teora. Dentro de los nmeros
complejos estn incorporados los nmeros
8. EJERCICIOS
Ejercicio
3.5:
Dar
una
demostracin
formalizada en la aritmtica de primer orden de
Peano de que 2 + 2 = 4.
Sugerencia: probar primero que 2 + 1 = 3,
siguiendo las lneas de la demostracin de
1 + 1 = 2.
CAPTULO CUATRO
EL TEOREMA DE GDEL
FUERA DE LA
MATEMTICA
Julia Kristeva: Gdel y la semitica. La elaboracin
de una teora formal para el lenguaje potico. Paul
Virilio: Gdel y las nuevas tecnologas. Rgis Debray
y Michel Serres: Gdel y la poltica. Deleuze y
Guattari: Gdel y la filosofa. Jacques Lacan: Gdel y
el psicoanlisis. Jean-Franois Lyotard: Gdel y la
condicin posmoderna. Ejercicios.
conjuntos de Gdel-Bernays
molestarse en justificarlo):
dice
(sin
mquinas de Turing.
En segundo lugar, ms importante, Nagel y
Newman sealan tambin muy claramente que la
representacin que eligi Gdel es a travs de
relaciones aritmticas (y no a travs de
figuras). De manera que en todo caso, si se
invoca el enfoque de Gdel, la lgica queda
sumergida en la aritmtica. No es una
ideografa sino que puede verse como una
parte de la aritmtica. As lo vea Gdel, tal
como queda muy claro en su conferencia Gibbs
[Gdel (2)]. Ya en su trabajo On Undecidable
Propositions of Formal Mathematical Systems
(vase en [Gdel (1)] o en [Davis]) Gdel
observa que la incompletitud de la aritmtica
puede verse como la imposibilidad de decidir si
ciertas ecuaciones llamadas diofnticas tienen o
no solucin (vase tambin [Matijasevich]).
Pareciera ms bien aqu que al leer el libro de
Nagel y Newman, Deleuze y Guattari quedaron
encandilados con las figuras y los ejemplos de
(1) (x < x)
(Prop. reflexiva)
(Prop,
antisimtrica)
(Prop, transitiva)
(Orden total)
del sujeto?
[]
Lo que se revela aqu de falta revela
sin duda la presencia del sujeto, pero
slo de ese sujeto que hizo el corte, ese
que
separa
el
denominado
metalenguaje
de
cierto
campo
matemtico que es simplemente su
discurso de otro lenguaje aislado,
de un lenguaje de artificio, del
lenguaje formal.
Lacan, as, cree encontrar la presencia del
sujeto en la falla de la textura lgica que
revelara el Teorema de Gdel. Veremos un poco
ms adelante que Lyotard da una explicacin
alternativa de esta situacin a travs de los
llamados juegos del lenguaje, en que los
jugadores competentes de una disciplina se
ponen de acuerdo sobre nuevas reglas.
lgica.
Entonces, ya que est all aquello de lo
que toma sentido todo discurso, a saber, a
partir de un otro, propongo bastante
claramente desde hace suficiente tiempo
para que baste recordarlo aqu: lo Real, la
categora que en la trada de la que parti
mi enseanza, lo Simblico, lo
Imaginario y lo Real, lo real se afirma
por un efecto del que no es el mnimo
el afirmarse en los impasses de la
lgica. Me explico: lo que al comienzo,
en su ambicin conquistadora, la lgica se
propona, no era nada menos que la malla
del discurso en tanto se articula y al
articularse, esta malla deba cerrarse en
un universo supuesto encerrar y recubrir,
como por una red, lo que poda haber de
lo que era ofrecido al conocimiento. La
experiencia, la experiencia lgica ha
evidentemente, un desplazamiento de la
idea de la razn. El principio de un
metalenguaje universal es reemplazado
por el de una pluralidad de sistemas
formales y axiomticos capaces de
argumentar enunciados denotativos, esos
sistemas que estn descritos en un
metalenguaje
universal,
pero
no
consistente. Lo que pasaba por paradoja, o
incluso por paralogismo, en el saber de la
ciencia clsica y moderna, puede
encontrar en uno de esos sistemas una
fuerza de conviccin nueva y obtener el
asentimiento de la comunidad de
expertos.
El mtodo para los juegos de lenguaje que
hemos seguido aqu se considera
modestamente incluido dentro de esa
corriente de pensamiento.
7. EJERCICIOS
Ejercicio 4.1: Discutir la siguiente exposicin
de Lacan sobre el Teorema de Gdel y las
observaciones que intercalamos:
Qu ms tentador para la lgica que las
matemticas,
donde
el
discurso
demostrativo pareca asentado en una
entera autonoma respecto de lo que se
llama experiencia? Pudo parecer, en
efecto, que este discurso no sostena su
certeza ms que por s mismo, a saber,
por las exigencias de coherencia que l se
impona.
[]
Qu ocurre en matemtica con el uso del
formalismo?
Se ha dicho que el discurso matemtico
SEGUNDA PARTE
La demostracin de
los teoremas
HOJA DE RUTA
LA CONCATENACIN Y
EL TEOREMA DE
INCOMPLETITUD
Si hay una concatenacin expresable, valen los
teoremas de Gdel.
smbolos y supondremos:
1. Que
esta
concatenacin
es
expresable en el lenguaje de la
aritmtica.
2. Que toda propiedad recursiva es
expresable en el lenguaje de la
aritmtica.
Bajo estas dos suposiciones daremos (en el
mismo captulo 5) la demostracin de la versin
semntica del Teorema de Gdel y (en el
captulo 6) la demostracin de la versin general
del Teorema de Gdel.
En el captulo 7 probaremos que la
concatenacin propuesta verdaderamente es
expresable en el lenguaje de la aritmtica.
En el captulo 8 probaremos que la
condicin 1 implica la condicin 2. Mostraremos
en realidad que toda propiedad recursiva puede
CAPTULO CINCO
LA VERSIN SEMNTICA
DEL
TEOREMA DE
INCOMPLETITUD
La concatenacin con punto y raya. Mtodo de
autorreferencia. Ser verdadero no es expresable.
ISAAC ASIMOV
Un sistema anticuado
separado en el captulo 8.
La demostracin que desarrollaremos es
constructiva, en el sentido de que exhibiremos y
escribiremos efectivamente un enunciado
verdadero y no demostrable. Puede verse en s
misma como un procedimiento, la aplicacin de
una receta que, a partir de una axiomatizacin
recursiva para la aritmtica dada por frmulas
verdaderas, permite obtener un enunciado
verdadero pero no demostrable para esa
axiomatizacin.
El enunciado G depender as de la
axiomatizacin que nos hayan dado (porque, por
supuesto, un enunciado que no es demostrable a
partir de ciertos axiomas, podra ser demostrado
a partir de otros).
Los elementos fundamentales para escribir
enunciados son los smbolos del lenguaje formal
que, para el caso de la aritmtica, recordemos,
son los siguientes:
S 0 +
Nmero
Abreviatura
10
11
12
13
posibles:
3=1+1+1
3=1+2
3=2+1
En consecuencia 3 tendra tres escrituras
diferentes como puntos y rayas:
3 =
3 =
3 =
La secuencia corresponde al smbolo 0,
pero las otras dos secuencias no corresponden a
ningn smbolo del lenguaje. Si al programa que
describimos antes le ingresamos el nmero 3 y le
pedimos que compruebe si es el nmero de Gdel
de una sucesin de smbolos, debe traducirlo al
lenguaje formal como el smbolo 0 o debe decir
que no corresponde a ningn smbolo? Vemos as
que la falta de unicidad en la escritura provoca
2. MTODO DE AUTORREFERENCIA
Para completar la demostracin del Teorema
de Gdel necesitamos una herramienta que nos
permita considerar enunciados autorreferentes,
es decir, enunciados que aludan a propiedades de
s mismos. Observemos que hasta ahora la
expresin
x(x Dem y),
cuando
reemplazamos y por cdigo de frmulas, nos
Gdel no es el de un enunciado
demostrable o, en el plano del lenguaje,
Soy un enunciado no demostrable.
8. Si G fuera un enunciado falso entonces
tendramos un teorema falso. Esto no es
posible porque los axiomas son todos
verdaderos, y entonces los enunciados
que se deducen de ellos tambin son
verdaderos (Teorema de Correccin).
Por lo tanto G es verdadero, lo que
significa que es verdad lo que dice de s
mismo, es decir, G es un enunciado
verdadero y no demostrable.
Observemos que, tal como habamos
anunciado, toda la argumentacin del teorema
puede desarrollarse a partir de las dos hiptesis
provisorias del primer punto. Estas dos hiptesis
sern probadas en los captulos 7 y 8.
CAPTULO SEIS
LA VERSIN GENERAL
(SINTCTICA) DEL
TEOREMA DE
INCOMPLETITUD.
EL TEOREMA DE
CONSISTENCIA
La versin general (sintctica) del Teorema de
Incompletitud. El Teorema de Consistencia.
Ejercicios.
sino
la
oposicin
entre
comprensin del objeto y aquello
que quiere ver la mayora de los
hombres. Precisamente por ello
puede ser lo cercano lo ms
difcilmente comprensible. Lo que
hay que vencer no es una
dificultad del entendimiento sino
de la voluntad
LUDWIG WITTGENSTEIN
Aforismos
omega-consistencia).[10]
Una teora es -consistente si toda vez que se
puede demostrar que 0 cumple la propiedad P,
1 cumple la propiedad P, 2 cumple la
propiedad P y as sucesivamente para todos los
nmeros naturales entonces no se puede
demostrar que existe x que no cumple la
propiedad P. Es decir, si P(0), P(1), P(2),
P(3), son todos enunciados demostrables
entonces xP(x) no es demostrable.
Toda teora -consistente es tambin
consistente, sin embargo la recproca no es
cierta: existen teoras que son consistentes pero
no -consistentes. En cierto sentido, hay ms
teoras consistentes que -consistentes, y es por
eso que el teorema de Rosser da una versin ms
general del teorema original de Gdel.
Como la consistencia se conserva tanto si se
agrega G como su negacin, la versin general
nos asegura, en ambos casos, la existencia de un
enunciado indecidible. Esta versin puramente
enunciado x(x n n x) es
demostrable.
3. Cualquiera que sea el numeral n, el
enunciado x(x n (x = 0 x =
1 x = n)) es demostrable.
(La expresin x y es una abreviatura para
Existe z tal que x + z = y).
Demostracin: Para esta demostracin slo
necesitamos suponer, como en el captulo
anterior, las siguientes dos hiptesis (que
probaremos en los captulos 7 y 8):
Hiptesis 1: La concatenacin es expresable
en el lenguaje formal.
Hiptesis 2: Toda propiedad recursiva es
expresable en el lenguaje formal.
(Recordemos que una propiedad es recursiva
si la verificacin de esa propiedad puede
(*)
(x Dem neg(p)).
Por otra parte, la condicin 3 nos dice que
x k (x = 0 x = 1 x= k) es
demostrable. Entonces:
x k (x = 0 x = 1 x = k) es
demostrable
x = 0 (x Dem neg(p)) es demostrable
x = 1 (x Dem neg(p)) es demostrable
x = 2 (x Dem neg(p)) es demostrable
Y as sucesivamente hasta k.
Un principio de la lgica dice que si
P (Q R) es una frmula demostrable y
tambin son demostrables Q S y R S
entonces P S es demostrable. La demostracin
puede verse en el Ejercicio 6.6. Esta afirmacin
se generaliza as: si P (Q0 Q1 Qk)
es demostrable y tambin son demostrables
Q0 S, Q1 S, , Qk S, entonces P S es
demostrable. Deducimos en consecuencia que la
frmula x k
(x Dem neg(p))
es
demostrable.
Pero x k (x Dem neg(p)) es
equivalente a (x k x Dem neg(p)) (de
hecho, esta segunda frmula es solamente una
abreviatura de la primera).[13] Luego, (x k
x Dem neg(p)) es demostrable.
A una demostracin de (x k
x Dem neg(p)) agregumosle inmediatamente a
continuacin la siguiente secuencia de frmulas
(y comprobemos que paso a paso la secuencia
extendida sigue siendo una demostracin):
1. (x k x Dem neg(p))
2. x(x k
x Dem neg(p))
Generalizacin
Axioma L4
3. x(x k
x Dem neg(p)) (z k
z Dem neg(p))
Generalizacin
z Dem neg(p))
es
demostrable.
Pero la afirmacin que hemos llamado (*)
dice que tambin es demostrable z(z k
z Dem neg(p)). Hay entonces un enunciado tal
que l y su negacin son ambos demostrables,
esto no es posible ya que la teora es consistente.
Hemos llegado a la contradiccin que
buscbamos, por lo que R, en consecuencia, no es
demostrable.
En consecuencia:
(m y m Dem neg(p)) z(z y
z Dem neg(p)) es demostrable.
Y, por modus ponens,
z(z y z Dem neg(p)) es demostrable.
Es decir, si agregamos a la teora la frmula
m y entonces z(z y z Dem neg(p)) es
demostrable. Y en la deduccin solamente hemos
usado la regla de modus ponens. Por el Teorema
de la Deduccin, vale entonces:
m y z(z y z Dem neg(p)) es
demostrable.
Como la teora es consistente, y por nuestra
hiptesis de absurdo estamos suponiendo que R
es demostrable, entonces R no es demostrable.
Por lo tanto, para todo n, el enunciado
(n Dem p) es verdadero y como en cada caso la
Demostrable, por
la Condicin 2
3. m y z(z y
z Dem neg(p))
Demostrable (se
prob antes)
4. y m (y Dem p)
Demostrable (se
prob antes)
aplicado a 1 y 5
2. EL TEOREMA DE CONSISTENCIA
Estamos ahora en condiciones de dar tambin
una prueba del segundo teorema fundamental de
Gdel.
TEOREMA DE CONSISTENCIA:
Si una teora es recursiva, contiene suficiente
aritmtica y es consistente entonces la
demostracin de su consistencia no puede ser
formalizada dentro de la propia teora. (En
otras palabras, una teora consistente y
recursiva que contenga suficiente aritmtica
no puede demostrar su propia consistencia).
Demostracin: Para probar este teorema
consideremos el mismo enunciado R que
construimos antes. Hemos probado que si R fuera
demostrable
entonces
z(z u
3. EJERCICIOS
La resolucin de algunos de los ejercicios
utiliza el Teorema de la Deduccin, que
P Q equivale a Q P.
Ejercicio 6.9: Verifique que si P (Q R) es
demostrable entonces Q (P R) es tambin
demostrable.
Resolucin: Agreguemos Q a la teora.
Entonces, como Q (P Q) es un axioma,
P Q es demostrable. Por otra parte,
(P (Q R)) ((P Q) (P R))
es un axioma. Como P (Q R) y P Q son
demostrables, por doble aplicacin de modus
ponens, P R es demostrable. Hemos visto as
que al agregar Q a la teora P R resulta
demostrable. Por el Teorema de la Deduccin,
Q (P R) es demostrable.
Ejercicio 6.10: Si el enunciado P(n) es
demostrable entonces el enunciado x(x = n
CAPTULO SIETE
HAY UNA
CONCATENACIN
EXPRESABLE EN LA
ARITMTICA
Qu ocurre si multiplicamos un
nmero natural por 10, 100 o
1.000?
Por
ejemplo,
si
multiplicamos 34 10 = 340, las
cifras de la unidad y de la decena
de 34, o sea 4 y 3, en el resultado
pasan a ser las cifras de la decena
y la centena, respectivamente.
SANTILLANA
Mi Manual, 6. grado
34500
66
calcula como:
xy = x 10L(y) + y
Ahora bien, la aparicin del dgito cero
provoca
muchos
inconvenientes.
La
concatenacin de nmeros es una operacin que
debe copiar a la concatenacin de los smbolos
de un lenguaje.
Una caracterstica de la concatenacin de
smbolos es su asociatividad: si s1, s2 y s3 son
secuencias de smbolos, entonces concatenar s1
con s2s3 es lo mismo que concatenar s1s2 con s3.
La misma caracterstica queremos para la
concatenacin de nmeros. Sin embargo la
asociatividad falla si se permite la aparicin del
dgito cero ya que concatenar 20 con 3 no es lo
mismo que concatenar 2 con 03 (en la primera
operacin el resultado es 203 y en la segunda es
23). Por este motivo en el captulo 5 definimos la
concatenacin solamente para dgitos distintos de
cero.
Podramos definir la concatenacin para
nmeros que usen nueve dgitos (excluyendo el
0). Sin embargo, para la demostracin de los
teoremas de Incompletitud es suficiente con usar
solamente dos dgitos, pues, como ya hemos
visto, cualquier expresin del lenguaje formal se
puede escribir usando solamente dos smbolos,
raya y punto.
En este captulo, para facilitar la
demostracin, optaremos por tomar como y a
los dgitos 1 y 2 respectivamente y probaremos
que la concatenacin es expresable para esta
eleccin en particular. Esto no implica una
prdida de generalidad, ya que los argumentos
que prueban los teoremas de Incompletitud slo
requieren
que
sea
expresable
alguna
concatenacin.
Al elegir raya y punto como los dgitos 1 y 2,
escribiremos los nmeros naturales en una base
que es diferente de las que habitualmente se
1
2
3
1
10
11
1
2
11
4
5
6
7
8
100
101
110
111
1000
12
21
22
111
112
9
10
11
1001
1010
1011
121
122
211
12
13
14
15
1100
1101
1110
1111
212
221
222
1111
+ 2k2 + + 2 + 1.
En consecuencia:
2k1 + 2k2 + + 2 + 1 u < 2k + 2k1 +
+2+1
Veamos ahora que la suma 2n + 2n1 + +
2 + 1 se calcula como 2n+1 1. En efecto, si
llamamos S a la suma 2n + 2n1 + + 2 + 1
tenemos que:
S = 2n + 2n1 + + 2 + 1
2 S = 2 (2n + 2n1 + + 2 + 1)
2 S = 2n+1 + 2n + + 22 + 2
2 S + 1 = 2n+1 + 2n + + 22 + 2 + 1
2 S + 1 = 2n+1 + S
2 S S = 2n+1 1
S = 2n+1 1
Entonces:
2k1 + 2k2 + + 2 + 1 u 2k + 2k1 +
+ 2 + 1,
2k1 u < 2k+1 1
El nmero 2k 1 es de la forma 2w 1 y es
menor o igual que u, el siguiente nmero de esa
forma es 2k+1 1, que no es menor o igual que u.
Luego, 2k 1 = 2L(u) 1 es el mayor de los
nmeros de la forma 2w 1 que es menor o igual
que u.
Si llamamos z al mayor de los nmeros de la
forma 2w 1 que es menor o igual que y,
entonces 2L(y) = z + 1. Tenemos, por lo tanto,
que la concatenacin en base 2 sin cero se calcula
como:
xy = x 2L(y) + y = x (z + 1) + y
donde z es el mayor de los nmeros de la forma
2w 1 que es menor o igual que y. Llegamos as
al teorema central de este captulo:
Teorema: La concatenacin en base 2 sin
cero es expresable en el lenguaje formal de la
aritmtica.
Demostracin: Para demostrar el teorema
basta con ver que z es el mayor de los nmeros
de la forma 2w 1 que es menor o igual que y
es traducible al lenguaje formal. En efecto,
(y = x z = 1) (y = 1 z = x))
La expresin x es potencia de 2 se traduce
entonces como:
x 1 u((u es divisor de x u es primo)
u = 2)
La expresin z es el mayor de los nmeros
de la forma 2w 1 que es menor o igual que y
equivale a la conjuncin de las siguientes
expresiones:
z es menor o igual que y;
z se obtiene restando 1 a una
potencia de 2;
z es mayor que cualquier otro nmero que
cumpla las dos condiciones anteriores.
Todas estas condiciones son expresables, por
lo que la definicin de la concatenacin en base 2
sin cero es traducible al lenguaje formal.
CAPTULO OCHO
TODA PROPIEDAD
RECURSIVA
ES EXPRESABLE CON LA
CONCATENACIN
2. V V 1, donde V es el nombre
de una variable. sta es la
instruccin disminuir e indica
que, si V 0, al valor de V se le
debe restar 1. Si V = 0, el valor de
V queda igual.
3. Si V 0 GOTO L, donde V es el
nombre de una variable y L es el
nombre de una etiqueta. sta es la
instruccin condicional e indica
que si V 0 entonces se debe
ejecutar la instruccin etiquetada
como L. Si V 0 no se hace nada y
se pasa a la instruccin siguiente.
El valor que tiene una variable en un
momento dado ser indicado con la misma letra
que la variable, pero escrita en minscula y
cursiva. As, por ejemplo, x ser el valor de la
variable X.
Si X 0 GOTO A
Es fcil verificar que si la entrada del
programa (a) es 0 entonces la salida es 1,
mientras que si la entrada es cualquier otro
nmero x 0 entonces la salida es ese mismo
nmero x.
Aunque este programa est perfectamente
bien definido, podramos intentar modificarlo de
modo tal que el valor de salida sea siempre igual
al valor de la entrada. Este objetivo puede
lograrse as:
(b) [A] Si X 0 GOTO B
ZZ+1
Si Z 0 GOTO L
[B] X X 1
YY+1
ZZ+1
Si Z 0 GOTO A
El programa (b) copia el valor de X en la
variable Y, cualquiera que sea el valor inicial de
X.
Observemos el efecto de las siguientes dos
instrucciones sucesivas de este programa:
ZZ+1
Si Z 0 GOTO L
La primera instruccin garantiza que el valor
de Z ser distinto de 0 y en consecuencia la
segunda nos deriva siempre a la instruccin L. El
resultado neto de ambas instrucciones es saltar
a la instruccin marcada con L. Esto justifica
resumir este par de instrucciones en una sola:
GOTO L
Ahora bien, cuando el programa (b) termina
GOTO C
[B] V' V' 1
VV+1
ZZ+1
GOTO A
[C] Si Z 0 GOTO D
GOTO E
[D] Z Z 1
V' V' + 1
GOTO C
Para ejemplificar la potencia de nuestro
lenguaje de programacin, escribiremos ahora
programas que realizan las operaciones de suma
y de multiplicacin.
El siguiente es un programa que calcula
X1 + X2:
(d)
Y X1
Z X2
[B] Si Z 0 GOTO A
GOTO E
[A] Z Z 1
YY+1
GOTO B
Z2 X2
[B] Si Z2 0 GOTO A
GOTO E
[A] Z2 Z2 1
Z1 X1 + Y
Y Z1
GOTO B
Por supuesto, Z1 X1 + Y no es una
instruccin de nuestro lenguaje sino un llamado
al programa (d), que es usado en este caso como
subrutina de (e). Dejamos como ejercicio la
comprobacin de que los programas (d) y (e) en
efecto permiten sumar y multiplicar.
Dado un programa P, llamaremos un estado
de P a una lista de ecuaciones de la forma V = m
donde V es una variable del programa y m es un
nmero natural. En un estado debe haber
exactamente una ecuacin por cada una de las
variables.
Supongamos que se est ejecutando el
programa y que o es alguno de los estados que
atraviesa. Nos gustara saber cul ser el estado
inmediato siguiente. Para ello necesitamos
conocer cul es la instruccin que est a punto de
2.
3.
a)
Si contiene la ecuacin V = 0,
entonces j = i + 1.
b)
R(0) =
R(1) =
R(2) =
R(3) =
Afirmacin: La funcin R es expresable en
el lenguaje de la concatenacin.
Demostremos la afirmacin. El par ordenado
(n, m), para nmeros naturales cualesquiera n y
m, se escribe en el lenguaje formal como
# # n # m # #. La sucesin formada por los pares
(n1, m1), (n2, m2), , (nk, mk) se escribe como
# # n 1 # m1 #### n 2 # m2 ## ## n k # mk # #.
Es fcil ver que Ser un par ordenado y Ser
una sucesin de pares son ambas expresables en
el lenguaje de la concatenacin. (Pensarlo!).
Consideremos ahora una sucesin finita de
pares de nmeros que cumpla estas dos
condiciones (que son ambas expresables):
estas
dos
2.
3.
y si contiene a n m entonces n y m
son nmeros de instantneas consecutivas.
Que un nmero a comience con b significa
que existe algn q tal que a = bq. Que un nmero
a finalice con b significa que existe algn p tal
que a = pb. Todas estas condiciones pueden
traducirse al lenguaje de la concatenacin, por lo
que Ser el nmero de un cmputo de P es
expresable.
Observemos ahora que En el programa P la
entrada x1, , xr tiene valor de salida 1
equivale a decir que existe el nmero de un
cmputo que comienza con:
R(l) R(e1) R(0) R(x1) R(xr)
R(0) R(0)
y que existen u1, , ur, wr, , wk tales que el
nmero finaliza con:
Fin
Nota: Nuestra demostracin de los teoremas
de Incompletitud podra ser objeto de la siguiente
crtica: es una demostracin que se basa en la
manera en que se escriben los nmeros, y no en
propiedades intrnsecas de stos. Este defecto
ser salvado en el prximo captulo, en el que
daremos una definicin ms amplia de la nocin
de concatenacin. All veremos que hay
concatenaciones intrnsecas, que no dependen de
la escritura, y que permiten desarrollar sin
cambio alguno las demostraciones que hemos
dado para los teoremas de Incompletitud.
La codificacin que Gdel defini en su
artculo de 1931 es diferente de la que hemos
definido en el captulo 5. Gdel le asigna a cada
smbolo del lenguaje un nmero impar (por
ejemplo, al smbolo 0 le asignara el nmero 1, al
smbolo S le asignara el 3, y as sucesivamente).
TERCERA PARTE
Incompletitud en un
contexto
general y abstracto
CAPTULO NUEVE
INCOMPLETITUD EN UN
CONTEXTO
GENERAL Y ABSTRACTO
Una demostracin intrnseca del Teorema de Gdel.
La concatenacin y el argumento de Gdel.
Conclusiones y preguntas abiertas. Ejercicios.
Pero si el mundo no es un
rompecabezas cuyas piezas sueltas
tenemos ante nosotros, sino una
sopa en la cual nadan al azar unos
fragmentos
que
slo
por
casualidad se congregan de vez en
cuando para formar un conjunto
coherente?
[]
Perfeccin,
completitud, belleza, no son ms
que una excepcin rara que slo
se presenta porque la cantidad de
fragmentos es inimaginable!
STANISLAW LEM
La investigacin
T(N)
entonces
axiomatizable:
no
Hay una
concatenacin
expresable en N
es
recursivamente
T(N) no es
recursivamente
axiomatizable
T(O) no es
recursivamente
axiomatizable
Hay una
concatenacin
expresable en O?
respuesta es s.
Esta respuesta afirmativa nos permitir
comparar dos argumentos diferentes que prueban
el Teorema de Gdel: uno de ellos es el que ya
hemos visto, basado en la paradoja del
mentiroso, el otro es un argumento alternativo
basado en la llamada paradoja de Berry (vanse
[Caicedo] y [Boolos]). Demostraremos que
ambos argumentos son equivalentes, en el
sentido de que ambos pueden extenderse a la
misma clase de objetos matemticos: aquellos en
los que hay una concatenacin expresable.
(El teorema principal de la primera seccin
es ya conocido, esencialmente es consecuencia
de [Quine]. Los resultados de las secciones
segunda y tercera son, hasta donde sabemos,
originales).
con
objetos
matemticos,
asumiremos
implcitamente que R siempre contiene la
relacin de igualdad. Llamaremos lenguaje del
objeto O (y notamos L(O)) al lenguaje de primer
orden que tenga los smbolos correspondientes
para designar las funciones, relaciones y
constantes de O.
Supondremos en todo lo que sigue que U es
numerable, es decir, que existe una
correspondencia uno a uno entre U y el conjunto
de los nmeros naturales (es decir, una
correspondencia que asocia cada elemento de U
con un nmero natural diferente, y viceversa).
Supondremos tambin que R es finito o
numerable. Por ejemplo, en el objeto N (tal como
hemos trabajado con l a lo largo de todo el
libro) el universo es el conjunto de los nmeros
naturales y R est formado por la constante 0, la
funcin sucesor y las operaciones de suma y
multiplicacin.
Si O es un objeto matemtico con lenguaje
de U.
As, en O s vale que todo elemento est
representado por un trmino sin variables.
Observemos adems que una frmula en L(O) es
tambin una frmula en L(O).
Vamos a definir qu significa que una
frmula sea verdadera en O.
Tal como hicimos para N en el captulo 3,
definimos primero qu significa que un
enunciado atmico sea verdadero. Los
enunciados atmicos de O son de la forma:
t1 = t2
donde t1 y t2 son trminos sin variables o
tambin:
P(t1, , tn)
donde P es uno cualquiera de los smbolos de
relacin de R.
Si el enunciado atmico es de la forma
[Chang y Keisler]).
En
[Wasserman]
se
exhibe
una
caracterizacin alternativa (en un lenguaje de
segundo orden) de la operacin de concatenacin,
que es equivalente a la que aqu presentamos.
Definicin. La concatenacin
expresable en O si:
1. Ser un elemento
expresable en O.
de
2. La
relacin
z = x y
expresable en O.
es
es
es
=1
= 2
= 3
y as sucesivamente, entonces concatenar rayas
equivale a sumar nmeros.
La teora de la concatenacin de un solo
tomo es equivalente a la teora del objeto
O = ({1, 2, 3,}; +, 1), la llamada aritmtica de
Presburger. Pero esta teora es recursivamente
axiomatizable [Presburger].
En cambio, si hay una concatenacin con al
menos dos tomos que sea expresable en O, y al
menos dos de esos tomos son definibles,
entonces podemos reproducir para T(O) el
razonamiento que prueba que T(N) no es
recursivamente axiomatizable. Tenemos as el
siguiente teorema:
Teorema 9.1: Si hay una concatenacin con
al menos dos tomos que es expresable en O,
Si u es un tomo en la escritura de x
entonces u = o u =
Si y estn representados por trminos sin
variables, entonces en la traduccin al lenguaje
formal de la expresin u = o u= los
smbolos y deben ser reemplazados por esos
trminos que los representan. Si y estn
definidos por las frmulas P y Q respectivamente
entonces se debe escribir x((u = x P(x))
(u = x Q(x))).
Basados en punto y raya definimos una
codificacin de Gdel en O anloga a la
numeracin de Gdel que definimos en el
captulo 5, con la nica diferencia de que punto y
raya ya no son nmeros naturales, sino elementos
del universo de O.
Para esto agregamos al lenguaje de O el
smbolo # (que sirve para representar sucesiones
de expresiones) y ordenamos todos los smbolos
segn el orden del diccionario o lexicogrfico. Al
21
22
21 31
21 32
22 31
22 32
21 31 51
1
2
11
12
21
22
111
denota
la
concatenacin usual de palabras,
que consiste en escribir la segunda
a continuacin de la primera.
Probaremos despus (ser una consecuencia
de la demostracin del teorema 9.2) que ni el
tomo a ni el tomo b son definibles en O. Por lo
tanto, la propiedad recursiva Ser el tomo a no
es expresable en O.
verdaderos en O) es recursiva.
decidible.
Sea V el conjunto expresable de O en el que
est definida una concatenacin .La teora del
objeto O1 = (V; ) es recursivamente equivalente
a la teora del objeto O2 = ({a, b}+; ), en el
sentido de que hay una correspondencia recursiva
y uno a uno que transforma cada enunciado
verdadero de L(O1) en un enunciado verdadero
de L(O2), y viceversa. (Esencialmente esto se
debe al hecho de que todas las concatenaciones
de dos tomos son isomorfas, tal como
explicamos en un comentario anterior).
Supongamos, por el absurdo, que T(O) es
decidible. Entonces existe un programa que
determina en una cantidad finita de pasos si una
frmula de L(O) es verdadera o falsa.
Sea P un enunciado cualquiera de
L({a, b}+; ). Lo traducimos a su equivalente en
L(V; ) que, en particular, es un enunciado de O.
<p
es
el
orden
restringido
a
los
nmeros primos, la
relacin usual menor
que,
pero
slo
tenemos derecho a
usarla para comparar
primos.
D es la relacin
Tienen la misma
cantidad de divisores
primos.
2. El objeto O = ({a, b}+; B, E, a, b),
donde:
{a, b}+ es el conjunto
de todas las secuencias
finitas de letras a y b.
La relacin B es ser
un prefijo de (es decir
estar al comienzo de,
por ejemplo, aabba es
un
prefijo
de
aabbaaaab).
La relacin E es ser
un sufijo de (es decir
estar al final de, por
ejemplo, aabba es un
sufijo de bbaabba).
2. LA CONCATENACIN Y EL
ARGUMENTO DE GDEL
Hemos visto que si existe en O una
concatenacin expresable (con la hiptesis
adicional de que al menos dos tomos sean
tercera y as sucesivamente.
A la primera sucesin de frmulas le
asignamos el 2, a la segunda le asignamos el 4 y
as sucesivamente.
No es difcil probar que esta asignacin es, en
efecto, una codificacin de Gdel para N.
Atencin: La definicin habitual de Ser
demostrable es innecesariamente limitada.
Como ya sabemos desde el captulo 1, la
definicin dice que una frmula es demostrable
si es la ltima frmula de una demostracin.
Necesitamos dar una definicin alternativa de
Ser demostrable que es equivalente a la
definicin habitual, pero que nos permite
considerar demostrable a una frmula cualquiera
que aparezca en una demostracin.
Diremos entonces a partir de ahora que una
frmula es demostrable si aparece en una
demostracin, no importa qu posicin ocupe
dentro de ella.
Intuitivamente, esta definicin ms laxa dice
que al probar un teorema no slo demostramos su
tesis, sino que probamos adems todas las
afirmaciones intermedias de la demostracin.
Esta idea se corresponde perfectamente con
la prctica matemtica. Por ejemplo el hecho de
que la propiedad x = a no es expresable en
O = ({a, b}+; ) no es consecuencia de la tesis
del teorema 9.2, sino de una afirmacin
intermedia de la demostracin.
Es fcil ver que ambas definiciones de
frmula demostrable son equivalentes: una
frmula es demostrable segn la definicin
habitual si y slo si es demostrable en este nuevo
sentido que definimos.
En efecto, es evidente que si una frmula es
demostrable en el sentido habitual entonces
tambin es demostrable en el sentido ms
amplio.
Recprocamente, si P es demostrable en el
sentido amplio entonces existe una demostracin
P1, , Pn tal que P aparece en ella, es decir,
P = Pk, con 1 k n. Entonces P1, , Pk es
tambin una demostracin y P es entonces
demostrable en el sentido habitual.
Adems puede probarse que:
Ser demostrable (en el sentido
ms amplio) es expresable en O
es equivalente a la conjuncin de:
Ser demostrable (en el sentido
habitual) es expresable en O
SF(x,y): x es el cdigo de una
sucesin finita de frmulas en la
que aparece la frmula de cdigo y
es expresable en O
(R P2) P2
((R P1) P1) P1
((R P1) P1) P2
y as sucesivamente. A estas frmulas las
llamaremos frmulas concatenables.
Observemos
que
hay
una
clara
correspondencia entre las frmulas concatenables
y los nmeros escritos en la base binaria sin cero
(que definimos en el captulo 7). Para establecer
la correspondencia consideramos en cada caso la
secuencia de los subndices de las frmulas Pi:
R P1
R P2
1
2
(R P1) P1
(R P1) P2
(R P2) P1
11
12
21
22
(R P2) P2
((R P1) P1) P1
111
z,
el
cdigo
de
una
Demostracin de la condicin 3. La
operacin que, dada una frmula concatenable A
y un contador B, da como resultado la frmula
A B, es expresable.
El conjunto de todas las frmulas del tipo
C D, con C concatenable y D contador, es
expresable porque es recursivo y no contiene
axiomas lgicos (sus frmulas no son
universalmente vlidas).
Sea H(x, y, z)definida por la conjuncin de:
x es el cdigo de una frmula
concatenable.
y es el cdigo de un contador.
z es el cdigo de una frmula del
tipo C D, con C concatenable y
D contador.
Existe u, el cdigo de una
demostracin que toma como
axiomas
a
las
frmulas
concatenables y a las frmulas del
tipo C D, en la que slo aparecen
x, y, z.
Si A es la frmula concatenable de cdigo x y
B es el contador de cdigo y entonces la tercera
condicin implica que B se obtiene por modus
ponens de A y de la frmula de cdigo z que es
del tipo C D. Esto slo es posible si la frmula
de cdigo z es A B. Por lo tanto, la funcin
deseada es expresable.
Dado que se cumplen las tres condiciones
indicadas en la observacin, el teorema queda
probado.
Atencin: El teorema 9.5 afirma que si
existe en O una codificacin de Gdel tal que
Ser demostrable es expresable, entonces existe
en O una concatenacin expresable. Esto no
3. CONCLUSIONES Y PREGUNTAS
ABIERTAS
concatenacin
2. Toda propiedad
expresable en N.
recursiva
es
recursivamente
concatenacin
2. Toda propiedad
expresable en O.
recursiva
es
recursivamente
4. EJERCICIOS
Qu,v) (Q Qab)
No es difcil ver que:
Cualquiera que sea Q de L(O'), el
enunciado d(Q)
es
siempre
verdadero.
Intuitivamente, esta afirmacin dice que si
es una frmula que es verdadera en la que u
y v representan tomos de la concatenacin,
entonces sigue siendo verdadera cuando u y v son
reemplazadas por los nombres de esos tomos
(ya sea que u sea reemplazada por a y v por b
viceversa).
Qu,v
(o bien H = A P2) y H F
entonces A est tambin en la
sucesin.
En la sucesin no hay frmulas
sucesoras de G. Es decir, ni
G P1, ni G P2 estn en la
sucesin.
En la sucesin no est la antecesora
de F (si es que existe). Es decir, si
F = B P1 (o bien F = B P2)
entonces B no est en la sucesin.
Ntese que, fijadas F y G, estas condiciones
no caracterizan una nica sucesin, pero si dos
sucesiones cumplen estas condiciones entonces
contienen exactamente las mismas frmulas y
slo difieren en el orden en que estn escritas o
en la cantidad de veces en que eventualmente
aparezcan repetidas.
Y as sucesivamente.
Con ms precisin, llamaremos sucesin
derivada de S, a cualquier sucesin que se
obtenga al agregar a cada frmula de S estos
contadores (y que es nica, salvo repeticiones o
el orden en que las frmulas se escriban).
Por ejemplo, si S est formada por:
(R P1) P1
((R P1) P1) P2
(((R P1) P1) P2) P1
Entonces una sucesin derivada de S est
formada por:
(R P1) P1) (R Q)
(((R P1) P1) P2) ((R Q) Q)
((((R P1) P1) P2) P1)
(((R Q) Q) Q)
(Cualquier otra sucesin derivada contiene
esas mismas tres frmulas, tal vez en otro orden
o tal vez con repeticiones).
Una sucesin derivada de S, que llamaremos
S', queda caracterizada (salvo orden y
repeticiones) por estas condiciones:
Toda frmula de S' es de la forma
A B, donde A es una frmula de
S y B es un contador.
F (R Q) est en S' y, excepto
sta, no hay en S' otra frmula del
tipo A (R Q) o del tipo
F B. (Es decir, el contador
R Q le corresponde a la frmula
F y a ninguna otra).
Si la frmula (A P1) (B Q),
respectivamente
la
frmula
respectivamente
(A P2)
entonces
(C Q) S'1
(B P2)
(C Q) S'2.
La sucesin S 1 contiene la informacin de los
tomos que forman G y la sucesin S 2 los copia a
la derecha de la frmula F. La ltima condicin
asegura que los tomos sean copiados en el orden
correcto. Todas las condiciones son expresables
en el lenguaje de O.
Finalmente, observemos que los tomos de la
concatenacin son g(R P1) y g(R P2), que
son cdigos de frmulas y en consecuencia, por
la definicin de codificacin de Gdel, son
definibles.
APNDICES
APNDICE I
EJEMPLOS DE TEORAS
COMPLETAS E
INCOMPLETAS
rectos
son
Observaciones:
AXIOMATIZACIONES DE UN OBJETO
MATEMTICO
(Prop. reflexiva)
(Prop. antisimtrica)
(Prop. transitiva)
(4) x y (x < y
y < x)
(Orden total)
(Densidad)
(Asociatividad)
(2) x + 0 = x
0+x=x
(Existencia de elemento
neutro)
(3) y(x + y = 0
y + x = 0)
(4) x + y = y + x
(5n) x 0 nx 0
(6n) y(ny = x)
(Existencia de
elemento neutro)
(3) y(x + y = 0
y + x = 0)
(Todo elemento
tiene inverso)
(4) x + y = y + x
(Conmutatividad)
(5) 1 x = x x 1 = x
(1 es una unidad
para el producto)
(6) x (y z) = (x y) z
(Asociatividad
de )
(7) x y = y x
(Conmutatividad
de )
(8) x (y + z) = (x y) +
(x z)
(Distributividad
de sobre +)
(9) x y = 0 x = 0
y=0
(10) 0 1
(11) x 0 y(y x = 1)
(12n) n1 0
(2) xy(y x)
(Conjunto vaco) Intuitivamente, existe un conjunto
(3) xyzu(u z u = x u = y)
(Pares) Intuitivamente, si x e y son conjuntos,
tambin es un conjunto {x, y}.
llamamos 2
{0, 1, 2}, un conjunto con tres elementos, que
llamamos 3
{0, 1, 2, 3}, que llamamos 4
etctera.
El conjunto {0, 1, 2, 3, 4,} satisface la condicin
del axioma: es no vaco, y para cada elemento n del
conjunto, hay otro (n + 1), tal que n + 1 pertenece al
conjunto y n pertenece a n + 1.
Este axioma postula la existencia de un conjunto
infinito actual, dado todo a la vez.
conjunto.
Observaciones:
1.
2.
3.
de primer orden.
(8) (y = xz + w w < x y = xq + r
r < x) w = r (Unicidad del resto)
sta es una teora para la aritmtica dada por
una cantidad finita de axiomas y que no es
recursivamente completable [Mendelson].
APNDICE II
HITOS EN LA HISTORIA
DEL
TEOREMA DE
INCOMPLETITUD
1. ARISTTELES Y EL INFINITO
Una cantidad es potencialmente infinita si es
siempre finita pero puede ser aumentada tanto
como se desee hasta superar cualquier cantidad
prefijada. En cambio, una cantidad es
actualmente infinita si ya es, de hecho, infinita.
La idea del infinito potencial implica un proceso
[Aristteles]):
La potencia y el acto, respecto del
infinito, del vaco y de todos los seres del
gnero se entienden de otra manera que
respecto de la mayora de los dems seres
tales como lo que se ve, lo que anda o lo
que es visto. En estos ltimos casos la
afirmacin de la existencia puede ser
verdadera, ya absolutamente, ya en tal
circunstancia dada. Visible se dice, o de
lo que es visto realmente, o de lo que
puede ser visto. Pero la potencia respecto
al infinito es de una naturaleza tal que el
acto jams puede realizarse, como no sea
por el pensamiento.
2. GEORG CANTOR
condiciones de afrontar.
En 1895, en Contribuciones a la
Fundamentacin de la Teora de los Nmeros
Transfinitos, vase [Cantor (1)], dice: Por un
agregado[22] entendemos cualquier reunin en
un todo M de objetos bien definidos m de nuestra
intuicin o nuestro pensamiento. Estos objetos
son llamados los elementos de M.
Al admitir la reunin ilimitada en un todo de
objetos cualesquiera de nuestra intuicin o
nuestro pensamiento Cantor introduce en la
matemtica el infinito actual, no sin la fuerte
oposicin de muchos de sus contemporneos.
Su descubrimiento de la contradiccin me
ha causado una gran sorpresa y, casi dira,
consternacin, pues sacude las bases
sobre las que he intentado edificar la
aritmtica. []
No slo mi fundamentacin de la
aritmtica, sino la posibilidad de
cualquier otra fundamentacin parece
desvanecerse.
5. DAVID HILBERT
Cuando el intuicionismo comienza a ganar
adeptos (entre ellos matemticos de primera
lnea como Henri Poincar), David Hilbert
(1862-1943) sale en defensa de la Teora de
Cantor. En 1925, en Acerca del Infinito, incluido
en [Hilbert (1)], escribe:
simples.[24]
Por
ltimo,
hemos
introducido tambin los enunciados
ideales cuya funcin consiste en preservar
la validez de las leyes usuales de la
lgica.
Ahora bien, en tanto que no expresan
afirmaciones finitistas, los enunciados
ideales, esto es, las frmulas, carecen de
todo significado, por lo que no podemos
aplicarles las operaciones lgicas de
manera concreta[25] como a los
enunciados finitistas. Se hace entonces
necesario someter a un proceso de
formalizacin tanto a las operaciones
lgicas como a las demostraciones
mismas.
En La Fundamentacin de la Teora
Elemental de Nmeros, de 1930, incluido en
[Hilbert (1)] leemos:
demostracin es un procedimiento
puramente externo de acuerdo con la
regla, a saber: la utilizacin del esquema
de inferencia y la sustitucin. Decimos,
finalmente, que una frmula es
demostrable cuando es o bien un axioma
o es la frmula final de una demostracin.
A las matemticas reales formalizadas de
la manera que acabamos de describir se
aade un elemento nuevo que podemos
considerar como una nueva matemtica,
una
metamatemtica,
que
resulta
necesaria para asegurar a aqulla, y en la
que, a diferencia de los principios
deductivos puramente formales de la
matemtica real, se recurre a la inferencia
concreta, pero nicamente con el carcter
no contradictorio de los axiomas.
[]
La ms importante de nuestras tareas
6. KURT GDEL
Como ya sabemos, Kurt Gdel (1906-1978)
demostr que el programa de Hilbert era
irrealizable. En [Smorynski] se relata el modo en
APNDICE III
extranjeros).
En 1923 ingres en la Universidad de Viena,
donde estudi matemtica, fsica y filosofa.
Aunque inicialmente pens en especializarse en
fsica terica, se decidi despus por la
matemtica.
Por aquella poca muchos de sus profesores
eran miembros del Crculo de Viena: un grupo de
matemticos, fsicos y filsofos que se reunan
peridicamente para debatir sobre la relacin
entre la ciencia terica y la realidad objetiva.
El grupo fue acercndose gradualmente a la
posicin conocida como positivismo lgico.
Gdel asisti a muchas reuniones del Crculo y,
aunque fue influido por sus ideas, dej claro que
no coincida del todo con ellas.
En 1929 complet su tesis doctoral. En ella
demostr el hoy llamado Teorema de
Completitud de Gdel. Este teorema se refiere a
la lgica de predicados, es decir, a las
afirmaciones, vlidas en todo contexto, que
1906:
1914:
1923:
Ingresa en la Universidad de
Viena. Durante ese perodo asiste
a las reuniones del Crculo de
Viena.
1929:
1930:
1931:
Se
publica
Sobre
las
proposiciones
formalmente
indecidibles de los Principia
Mathematica
y
sistemas
1934:
1939:
1940:
Se incorpora al Instituto de
Estudios Avanzados de Princeton.
Se publica La consistencia del
axioma de eleccin y de la
hiptesis
generalizada
del
continuo con los axiomas de la
teora de conjuntos.
1946:
Es
incorporado
de
modo
permanente al Instituto de
Estudios avanzados (hasta ese
momento su cargo deba ser
renovado anualmente).
1947:
Se publica Qu es el problema
del continuo de Cantor?, sobre
cuestiones filosficas relativas a
la (por entonces slo conjeturada)
indecidibilidad de la hiptesis del
continuo. Aqu Gdel expone con
claridad
su
adhesin
al
platonismo(filosofa que postula
la existencia real de los objetos
matemticos).
1948:
Adopta
la
estadounidense.
1949:
Se publica Un ejemplo de un
nuevo
tipo
de
soluciones
cosmolgicas a las ecuaciones
ciudadana
einstenianas
del
campo
gravitatorio y tambin Una
observacin sobre la relacin entre
la teora de la relatividad y la
filosofa idealista.
1950:
1951:
1978:
El 14 de enero muere
Princeton, Estados Unidos.
en
REFERENCIAS BIBLIOGRFICAS
ARISTTELES,
Metafsica,
Espasa-Calpe
Mexicana, Mxico D. F., 1960.
BERNAYS, PAUL,
The
Philosophy
of
Mathematics and Hilberts Proof Theory
(1930), Bernays Proyect: Text No. 9 (puede
verse online: www.phil.cmu.edu/projects/
bernays).
BES, A., y RICHARD D., Undecidable
Extensions of Skolem Arithmetic, The
Journal of Symbolic Logic, vol. 63 (2), 1998.
BOOLOS, G., A new proof of the Gdel
2001.
LACAN, JACQUES, El seminario, Libro 16: De
un Otro al otro, Paids, 2008.
LYOTARD, JEAN-FRANOIS, La condicin
posmoderna, Ctedra, Madrid, 2008.
MATIJASEVICH, YURI, Hilberts Tenth Problem,
The Mitt Press, Cambridge, 1993.
MAURIN, F., The Theory of Integer
Multiplication with Order Restricted to
Primes is Decidable, The Journal of
Symbolic Logic, vol. 62, 1997, n. 1, pp. 123130.
MENDELSON, E., Introduction to Mathematical
Logic, Chapman & Hall, 1997.
PRESBURGER, M., ber die Vollstndigkeit
eines gewissen Systems der Arithmetik
ganzer Zahlen, in welchem die Addition als
einzige Operation hervortritt, Comptes
Rendus du I Congrs de Mathmaticiens des
Pays Slaves, Varsovia, 92-101 (1929).
LECTURAS RECOMENDADAS
lgica e ingenio.
En 2009, junto a Guillermo Martnez, publica
Gdel (para todos).
Notas
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]