godel y la incompletud de las matemáticas

9
GÖDEL Y LA INCOMPLETITUD DE LAS MATEMÁTICAS El logro de Gödel en la lógica moderna es singular y monumental - más que monumental, es una señal que permanecerá visible lejos en el espacio y en el tiempo. John von Neumann 1 Kurt Gödel en 1939 El presente artículo pretende dar a conocer al lector quién fue Kurt Gödel y qué dice su famoso resultado acerca de la incompletitud de las matemáticas a través de los pasos básicos de la demostración de éste. Para poder alcanzar el objetivo he considerado necesario comprender el enunciado del teorema de completud 2 . Por tanto, en primer lugar se explica este otro resultado de Gödel, aunque sin entrar en la justificación de tal. 1 ¿Quién fue Kurt Gödel? Kurt Gödel ha sido sin lugar a dudas uno de los grandes matemáticos del s. XX. Nació el 28 de abril de 1906 en Brno, ciudad de la actual República Checa, en el seno de una familia de ascendencia austríaca. Ya de pequeño destacó en su trayectoria escolar 3 . En 1924 Gödel marchó de su país natal a Austria para inscribirse en la universidad de Viena. Fue para cursar física, pero poco a poco su interés se orientó hacia las matemáticas en pos de una mayor exactitud. Finalmente se licenció en matemáticas centrándose en el campo de la lógica, campo en el que encontró la precisión que anhelaba. A lo largo de su vida siempre buscó la exactitud. Esto explica la poca cantidad de artículos que publicó en vida. Fue una persona que sólo publicó aquello que fue capaz de justificar con claridad abrumadora, incluso para convencer a los más escépticos 4 . En 1929 se doctoró presentando el teorema de completud de la lógica de primer orden. Dos años después la irrupción de su teorema de incompletitud provocó una auténtica revolución que acabó con el Programa formalista de Hilbert. El resultado fue aceptado desde el primer momento, la exquisita claridad de su exposición fue tal que nadie dudó de la prueba dada. Un poco más tarde, en el año 1938, justificó la consistencia relativa del axioma de elección y de la hipótesis del continuo. 1 Estas palabras fueron pronunciadas por von Neumann con motivo de la entrega a Gödel del premio Einstein en 1951. Tal cual dice [Wan, pág. 179] están recogidas en New York Times, 15 de marzo de 1951, pág. 31. 2 Dependiendo de la literatura castellana que uno consulta se encuentra con el término completud o con el término completitud. La elección del término aquí hecha ha sido totalmente arbitraria. 3 Durante esa etapa sólo en una ocasión recibió una calificación por debajo de la máxima, y curiosamente fue en matemáticas. 4 Esta parece ser la causa por la que publicó tan poco sobre su concepción de la filosofía de la matemática, lugar en el que se consideraba totalmente platónico.

Upload: antonela-fiocchi

Post on 17-Sep-2015

8 views

Category:

Documents


1 download

DESCRIPTION

Godel y La Incompletud de Las Matemáticas.

TRANSCRIPT

  • GDEL Y LA INCOMPLETITUD DE LAS MATEMTICAS

    El logro de Gdel en la lgica moderna es singular y monumental - ms que monumental, es una seal que permanecer visible lejos en el espacio y en el tiempo.

    John von Neumann1Kurt Gdel en 1939

    El presente artculo pretende dar a conocer al lector quin fue Kurt Gdel y qu dice su famoso resultado acerca de la incompletitud de las matemticas a travs de los pasos bsicos de la demostracin de ste. Para poder alcanzar el objetivo he considerado necesario comprender el enunciado del teorema de completud2. Por tanto, en primer lugar se explica este otro resultado de Gdel, aunque sin entrar en la justificacin de tal.

    1 Quin fue Kurt Gdel?

    Kurt Gdel ha sido sin lugar a dudas uno de los grandes matemticos del s. XX. Naci el 28 de abril de 1906 en Brno, ciudad de la actual Repblica Checa, en el seno de una familia de ascendencia austraca. Ya de pequeo destac en su trayectoria escolar3. En 1924 Gdel march de su pas natal a Austria para inscribirse en la universidad de Viena. Fue para cursar fsica, pero poco a poco su inters se orient hacia las matemticas en pos de una mayor exactitud. Finalmente se licenci en matemticas centrndose en el campo de la lgica, campo en el que encontr la precisin que anhelaba. A lo largo de su vida siempre busc la exactitud. Esto explica la poca cantidad de artculos que public en vida. Fue una persona que slo public aquello que fue capaz de justificar con claridad abrumadora, incluso para convencer a los ms escpticos4.En 1929 se doctor presentando el teorema de completud de la lgica de primer orden. Dos aos despus la irrupcin de su teorema de incompletitud provoc una autntica revolucin que acab con el Programa formalista de Hilbert. El resultado fue aceptado desde el primer momento, la exquisita claridad de su exposicin fue tal que nadie dud de la prueba dada. Un poco ms tarde, en el ao 1938, justific la consistencia relativa del axioma de eleccin y de la hiptesis del continuo.1 Estas palabras fueron pronunciadas por von Neumann con motivo de la entrega a Gdel del premio Einstein en 1951. Tal cual dice [Wan, pg. 179] estn recogidas en New York Times, 15 de marzo de 1951, pg. 31.2 Dependiendo de la literatura castellana que uno consulta se encuentra con el trmino completud o con el trmino completitud. La eleccin del trmino aqu hecha ha sido totalmente arbitraria.3 Durante esa etapa slo en una ocasin recibi una calificacin por debajo de la mxima, y curiosamente fue en matemticas.4 Esta parece ser la causa por la que public tan poco sobre su concepcin de la filosofa de la matemtica, lugar en el que se consideraba totalmente platnico.

  • Los tres resultados anteriores constituyen los logros ms famosos de Gdel en el terreno de la lgica matemtica, no los nicos. Se puede decir, por tanto, que su poca ms productiva fue la dcada de los aos 30. Durante este tiempo Gdel estuvo ejerciendo de profesor de la universidad de Viena, aunque viaj en varias ocasiones al I.A.S.5 de Princeton. En el ao 1938 se cas con Adele Nimbursky, con quien convivi hasta su muerte.La pareja se traslad definitivamente a Princeton en 1940, donde l se dedic al I.A.S. All estuvo junto a grandes figuras de este siglo como Einstein, v. Neumann, Veblen, etc. Uno de los mejores amigos de Gdel fue Einstein. Juntos compartieron gran cantidad de paseos y conversaciones. Fueron dos genios de carcter muy diferente: mientras que Einstein fue una persona afable a la que gust convivir con la fama, Gdel fue una persona solitaria, huraa e hipocondraca. Poco a poco parece ser que Gdel comenz a interesarse por la filosofa, tanto filosofa de la fsica6 como de la matemtica, dejando un poco de lado la lgica matemtica7. Finalmente muri el 14 de enero de 1978 por inanicin, se negaba a comer convencido de que la comida estaba envenenada.

    Gdel acompaado por un fsico derenombre llamado Einstein en 1954

    2 La completud de la lgica de primer orden

    Este resultado de Gdel corresponde a su tesis doctoral, publicada en 1930 bajo el ttulo La suficiencia de los axiomas del clculo lgico de primer orden8. En breves palabras este resultado suele describirse como que todo lo que es verdad es demostrable. Para poder comprender9 lo que se quiere decir con las palabras anteriores es necesario adentrarse un poco dentro de los dominios de la lgica.

    En la lgica de primer orden las frmulas se construyen a partir de dos tipos de smbolos. Hay unos smbolos comunes que son:, , , , , , =, ( y ). A parte de estos smbolos comunes a todo lenguaje de primer orden tambin se dispone de smbolos concretos dependiendo de lo que se quiera hablar. Hay, por tanto, muchos lenguajes de primer orden. Mientras que los smbolos comunes tienen una interpretacin intuitiva y unvoca, los otros smbolos se pueden interpretar de formas muy diferentes.Supngase que se quiere hacer teora de grupos, entonces a los smbolos comunes es interesante aadirles los smbolos siguientes (notacin aditiva): + y 0. En este caso, algunos ejemplos de frmulas seran los siguientes:

    (G1) xyz ( (x+y)+z = x+(y+z) )(G2) x ( x+0 = x ) x ( 0+x = x )(G3) x y ( x+y = 0 ) x y ( y+x = 0 )(G4) xy ( x+y = y+x )(G5) x+y = z

    5 Instituto de Estudios Avanzados.6 Seguramente animado por sus charlas con Einstein.7 Tal vez esta sea la explicacin de los pocos resultados matemticos que consigui mientras estuvo en Princeton.8 Su tesis doctoral es de una concisin legendaria, caba en 11 pginas. Se puede encontrar una traduccin castellana en [Mos, pg. 23].9 Y tambin para evitar malinterpretaciones del enunciado, sobretodo hay que ir con sumo cuidado de cara a las conclusiones de carcter filosfico que se pretendan extraer.

  • Se observa que G5 tiene una diferencia esencial con respecto a las otras frmulas. Si se considera una interpretacin de los smbolos no comunes (es decir, una estructura matemtica concreta) se observa que en G5 uno no puede afirmar si la frmula es verdadera o no (depende de como se interpreten las variables x, y, z), mientras que en las otras frmulas s que se puede10. Se llama sentencias a las frmulas que dada una estructura se puede afirmar si son verdaderas o falsas (como G1-G4). Para estudiar el concepto de verdad, en el fondo, lo nico que presenta inters son las sentencias, no las frmulas en general. Para referirse a las sentencias se emplean los smbolos , , (letras griegas). En cambio, para referirse a las frmulas que no son sentencias se emplean tambin letras griegas pero indicando entre parntesis cuales son las variables que falta interpretar; as pues, la frmula G5 se denotara por (x,y,z)11. Es decir, las frmulas que no son sentencias se denotan en general por (x0, x1, , xk) con k0.

    Supngase que dentro de un lenguaje concreto de primer orden fijamos un conjunto de sentencias . Se dice que una sentencia es consecuencia de si toda estructura que verifica todas las sentencias de automticamente verifica . En tal caso se usa la notacin . Y se dice que se dispone de una demostracin formal de a partir de cuando se tiene una sucesin finita de sentencias tal que cada sentencia de la sucesin es una sentencia de o bien se ha obtenido a partir de sentencias anteriores de la sucesin aplicando las leyes de la lgica12. Esto se denota .

    Ahora ya estamos en condiciones de comentar el teorema de completud. Este resultado afirma que es consecuencia de si y slo si es demostrable formalmente a partir de , es decir, que si y slo si . Es evidente que las leyes de la lgica haban sido elegidas para permitir concluir que todo lo que se puede demostrar formalmente a partir de un conjunto de sentencias tambin es consecuencia de . El mrito de Gdel fue justificar que slo se necesitaban esas leyes lgicas para obtener todo lo que es consecuencia. Es decir, Gdel fue capaz de ver que no se escapa ninguna consecuencia usando simplemente esas leyes.

    3 La incompletitud de las matemticas

    Este resultado es, sin lugar a dudas, el ms famoso de los resultados de Gdel. Tambin se le conoce con los nombres de primer teorema de Gdel, teorema de incompletitud o teorema de Gdel. Fue publicado por Gdel en 1931 bajo el ttulo Sobre sentencias formalmente indecidibles de Principia Mathematica y sistemas afines13. Este artculo es sin ningn gnero de dudas, a pesar de ocupar slo unas 25 pginas, el ms revolucio-nario de toda la lgica del s. XX

    10 Se puede pensar por ejemplo en los N con la interpretacin estndar de los smbolos no comunes.11 Entonces por la frmula (x,0,z) se entiende la frmula x+0 = z. Anlogamente se puede hablar de (0,0,z), de (0,0,0), etc.12 Para conocer cuales son exactamente las leyes de la lgica con las que se juega se puede consultar cualquier manual de lgica, por ejemplo [Men]. Lo importante es que se trata de leyes concretas. No slo sabemos que existen sino que estn dadas, son unas leyes perfectamente conocidas y esencialmente se trata de un nmero finito.13 Se puede encontrar una traduccin castellana en [Mos, pg. 53].

  • 3.1 Qu dice el teorema de Gdel?

    En primer lugar intentaremos situarnos en el contexto histrico en el que irrumpi el teorema de Gdel. Desde comienzos del s. XX las matemticas estaban sufriendo un proceso de formalizacin para garantizar que estaban libres de toda contradiccin14. Este intento de formalizacin se ha conocido como el Programa de Hilbert, y esencialmente constaba de dos puntos. En primer lugar haba que encontrar una axiomtica completa15 para poder demostrar todas las verdades matemticas y slo stas. Y una vez encontrados estos axiomas slo quedara justificar que eran consistentes, es decir, que a partir de ellos no se podra deducir jams una contradiccin16. Por aquel entonces todo el mundo era muy optimista de cara al xito del Programa. Incluso pareca que el teorema de completud de Gdel era un granito de arena ms para completar el Programa. Pero he aqu que Gdel en 1931 hundi el Programa de Hilbert de un plumazo.

    Para cargarse el Programa, Gdel no necesit fijarse en todas las matemticas, l simplemente puso sus ojos sobre la aritmtica17. Con la aritmtica intent llevar a cabo el Programa de Hilbert y comprob que es imposible. Gdel consider el lenguaje de primer orden con los smbolos +, , S y 0. Es evidente que en este lenguaje se puede estudiar la aritmtica pensando el smbolo S como el asociado a una funcin monaria que nos da el siguiente de un nmero natural. Dentro de ese lenguaje consideramos los siguientes axiomas (la formalizacin en primer orden de los axiomas de Peano):

    (P1) x ( 0 = Sx )(P2) xy ( Sx = Sy x = y )(P3) x ( x+0 = x )(P4) x ( x+Sy = S(x+y) )(P5) x ( x0 = 0 )(P6) x ( xSy = xy+x )(P7) Para cada frmula no sentencia (x) consideramos la sentencia ( (0) x ( (x) (Sx) ) ) x (x)

    Es evidente que cualquier conjunto de axiomas candidato para la aritmtica debe incluir los axiomas de Peano, pero a priori puede ser que se necesiten ms axiomas.Gdel se dio cuenta de que el conjunto de axiomas que buscaba deba cumplir otra condicin ms. Es trivial que si consideramos el conjunto {sentencias verdaderas en N con la interpretacin estndar de los smbolos no comunes} podremos demostrar a partir de l todas las sentencias verdaderas de la aritmtica y slo stas; pero esto no nos interesa, no tenemos ninguna idea efectiva de quin es ese conjunto. Por tanto, Gdel exigi la existencia de un algoritmo que en un nmero finito de pasos permita saber si una sentencia es de o no. Es decir, el conjunto de sentencias que buscaba para axiomatizar la aritmtica deba ser computable. As pues, la demostracin del teorema

    14 Se pretenda ahorrar al futuro casos como el ocasionado por la entonces reciente paradoja de Russell.15 Un conjunto de axiomas se dice que es completo si dada cualquier sentencia se verifica que o que . El hecho de exigir que la axiomtica fuera completa recaa en la idea de que todo problema matemtico es resoluble, es decir, que toda afirmacin matemtica es verdadera o falsa. Si no es completo entonces no es posible responder a todas las preguntas que se puedan formular en ese lenguaje.16 Esto se pretenda hacer analizando simplemente los smbolos que aparecen en los axiomas, por mtodos finitarios. No se poda recurrir a matemticas de tipo superior puesto que an no se saba que estuvieran libres de contradiccin.17 La parte de las matemticas que versa sobre los nmeros naturales con su interpretacin estndar.

  • de Gdel le llev a dar la primera nocin formal de computabilidad, de existencia de un algoritmo18.Ahora ya estamos en condiciones de dar el enunciado que Gdel demostr.

    Teorema de Gdel Para cualquier conjunto computable y consistente de sentencias que incluya las sentencias P1,,P7 ocurre que existe una sentencia tal que a partir de no se puede demostrar formalmente ni ni . Se dice que es una sentencia indecidible.

    Si se interpreta este teorema a travs del teorema de completud se obtiene que hay estructuras matemticas que verifican {} y tambin estructuras matemticas que verifican {}. Con anterioridad a Gdel, el lgico noruego Thoralf Skolem ya haba visto que haba estructuras diferentes a la estndar de los N que cumplen los axiomas de Peano. El mrito de Gdel radic en ver que no slo haba estructuras diferentes, sino que adems cumplan sentencias diferentes. Adems, Gdel fue capaz de mostrar que el problema que aparece es insalvable, no se puede solucionar aadiendo las sentencias indecidibles a los axiomas19. Es decir, si ahora se considera {} como nuevo conjunto de axiomas se siguen teniendo sentencias indecidibles en virtud del mismo teorema. Y anlogamente si consideramos {}. En resumen, el decantarse por o por como nuevo axioma no depende de motivos lgicos. La intuicin siempre jugar un papel fundamental en la tarea matemtica.Por tanto, si se acepta la existencia de los objetos matemticos con independencia de nuestra mente (si se acepta el Cielo Platnico) uno se encuentra con el problema de que la verdad aritmtica no es axiomatizable puesto que en el Cielo deber cumplirse o . Y como la aritmtica es una parte de la matemtica (la ms simple de todas) se concluye que la verdad matemtica no es axiomatizable. Es decir, no se puede alcanzar la verdad matemtica a travs del concepto de demostracin formal. En virtud de esto ltimo suele decirse que no toda verdad matemtica es demostrable, y que por ende las matemticas son incompletas. As pues la tarea matemtica siempre depender en ltima instancia de la intuicin, no es mecanizable. La verdad matemtica est ms all de los axiomas y las leyes de la lgica. La verdad est ah fuera.As pues, este teorema permite concluir que no se puede encontrar una axiomtica completa de la aritmtica, es decir, da la irrealizabilidad del Programa de Hilbert para la aritmtica. Y de ah no es difcil20 concluir que tambin supone el fracaso del Programa para toda la matemtica.

    3.2 Cmo se las apa Gdel para demostrar su teorema?

    A continuacin vamos a seguir el mtodo seguido por Gdel para justificar su famoso teorema. El teorema de Gdel, tal cual se dice en [Hof], es como una perla en una ostra.

    18 Gdel mismo no us el concepto de computable. l hablaba de conjuntos recursivos, ver [Men]. Fue el ingls Turing quien en 1936 dio la primera definicin formal de computabilidad. En ese artculo Turing justific que su nocin de computabilidad coincida con la de recursividad empleada por Gdel. De cara al presente artculo, para no entretenerme con temas ms tcnicos, he considerado ms adecuado hablar de computabilidad puesto que todo el mundo tiene la idea intuitiva de algoritmo.19 El xito de Gdel radica en el ver que es insalvable puesto que la existencia de sentencias indecidibles no es sorprendente en s misma. Todo matemtico sabe que existen grupos abelianos y grupos no abelianos, es decir, que la sentencia G4 es indecidible a partir del conjunto {G1, G2, G3}.20 Pero no es trivial.

  • Su secreto no se percibe escrutando la perla, sino el aparato demostrativo oculto en la ostra que la aloja.La clave de la prueba se encuentra en la autorrecursin. A modo de ejemplo se puede pensar en el lenguaje ordinario. En cierta forma se puede pensar el lenguaje ordinario como un sistema formal que tiene una serie de axiomas (palabras) y una serie de leyes (reglas gramaticales) que nos permiten construir sentencias (frases). Las frases pueden ser calificadas de verdaderas o falsas: Jos colabora en Aleph, Aleph tiene tapas blandas, El lenguaje ordinario es recursivo, permite construir frases relativas a otras frases. De las dos frases citadas antes entre comillas ambas son ciertas. Esta frase tambin se puede calificar de verdadera o falsa. Se suele llamar metalenguaje a un lenguaje que es capaz de producir declaraciones sobre otro. As pues el lenguaje ordinario es metalenguaje de l mismo. En cuanto un lenguaje posee esta capacidad automticamente aparecen problemas. Considrese por ejemplo la afirmacin: Esta frase es falsa. Es evidente que no se puede ver la certeza o falsedad de dicha afirmacin. La frase anterior da lugar a una paradoja.Lo que Gdel hizo fue repetir el argumento anterior en la aritmtica en lugar del lenguaje ordinario. Gdel encontr un mtodo que permite a la aritmtica hacer declaraciones sobre ella misma. Y una vez encontrado ese mtodo todo lo que tuvo que hacer es construir la sentencia que afirma de ella misma que es indemostrable.

    Cmo puede la aritmtica hacer declaraciones sobre ella misma? El mtodo que us Gdel se conoce hoy da con el nombre de gdelizacin. La idea recae en asociar a cada frmula un nmero natural [] conocido como el nmero de Gdel de 21. A cada smbolo se le asocia un nmero natural.

    0 3 , 17 x0 31S 5 19 x1 33+ 7 21 x2 35 9 23 x3 37= 11 25 x4 39( 13 27 etc.22

    ) 15 29Esta codificacin de smbolos permite codificar cualquier sucesin formada por ellos. La expresin x0 x1 se codifica por la sucesin 19 31 33 9 21. Anlogamente, la sentencia x0 ( +(x0,0) = x0 ) se codifica por la sucesin 19 31 13 7 13 31 17 3 15 11 31 15. Ahora la clave est en usar la sucesin de los nmeros primos para codificar toda la sucesin en un slo nmero. As pues, la primera expresin queda codificada por el nmero 219331539791121, y la segunda por 21933151377111313311717193 2315291131313715. En virtud de que la factorizacin en primos es nica se obtiene que dado un nmero natural se puede recuperar la expresin que codifica, si es que codifica alguna. Hasta ahora hemos asociado nmeros de Gdel a las sucesiones de smbolos (incluidas las frmulas). Ahora toca el turno de asociar nmeros de Gdel a las demostraciones formales. Conviene recordar que por definicin una demostracin formal es una

    21 En la prctica se hace algo ms general, se asocia un nmero a cada sucesin de smbolos, no slo a las frmulas.22 Por qu tomar nmeros impares para los smbolos? Porque entonces es sencillo, una vez conocido el mtodo de gdelizacin, justificar que los nmeros naturales que codifican smbolos, sucesiones de smbolos y demostraciones son tres conjuntos disjuntos. Si se usaran nmeros consecutivos (incluyendo a los pares) para codificar los smbolos, la afirmacin anterior no sera cierto.

  • sucesin de frmulas 1, 2, , n que cumple ciertas condiciones. sta quedar codificada por el nmero 2[1]3[2]5[3]De entre las sucesiones de smbolos que se pueden encontrar, Gdel distingui unas especiales que le permitan reproducir los nmeros naturales. A estas expresiones se les llama numerales. Cmo se definen? El numeral de 0 es la expresin 0. El numeral de 1 es la expresin S(0). El numeral del 2 es la expresin S(S(0)). Y as sucesivamente. En general el numeral de n se denota a travs del smbolo n .Una relacin numrica es un subconjunto de Nk con kN. Una relacin numrica se dice que es computable si existe un algoritmo que dada cualquier tupla permite averiguar en un nmero finito de pasos si la tupla es de la relacin o no.Ahora ya podemos enunciar el lema que utiliz Gdel para poder realizar declaraciones de la aritmtica sobre ella misma.

    Lema 1 Sea R una relacin (k+1)-aria computable y sea un conjunto de sentencias que incluya a P1,,P7. Entonces existe una frmula (x0, x1, , xk) que cumple:

    i) Si (n0, n1, , nk)R entonces ( n0 , n1 , , nk )23.ii) Si (n0, n1, , nk)R entonces ( n0 , n1 , , nk ).

    Llegado este punto a Gdel slo le quedaba encontrar la relacin computable adecuada para poder construir la sentencia que dijera No soy demostrable. Se definen las siguientes relaciones (se supone que es un conjunto de sentencias):

    F = { kN: k es nmero de Gdel de una frmula }Sent = { kN: k es nmero de Gdel de una sentencia }Num = { kN: k es nmero de Gdel de un numeral }D = { (k,m,n)N3: m es nmero de Gdel de una frmula (x0), k es nmero de

    Gdel de la sentencia ( n ) }.G = { kN: k es nmero de Gdel de una sentencia de }Dem = { (k,m)N2: k es nmero de Gdel de una demostracin formal a partir de

    de la sentencia de nmero de Gdel n }R = { (t,m,n)N3: m es nmero de Gdel de una frmula (x0), t es nmero de

    Gdel de una demostracin a partir de de la sentencia ( n ) } = = { (t,m,n)N3: existe k tal que (k,m,n)D y (t,k)Dem }

    Y ahora es muy fcil justificar el siguiente resultado.

    Lema 2 Se cumplen las siguientes afirmaciones: i) Las relaciones F, Sent, Num y D son todas ellas computables.ii) Si es un conjunto de sentencias tal que G es computable (esto suele

    abreviarse diciendo que es computable) entonces las relaciones Dem y R son computables.

    23 Por ( n0 , n1 , , nk ) se hace referencia a la frmula que resulta de sustituir en la frmula (x0, x1, , xk) la variable x0 por n0 , la variable x1 por n1 , etc.

    Es 23 estenmero?

    SI

    NOo

    NO

    SIEntrada de n

    Entrada de n*

  • Este algoritmo muestra que Num es computable

    Con esos dos lemas Gdel ya fue capaz de construir la sentencia que dice No soy demostrable. Supngase que se tiene un conjunto cumpliendo las hiptesis del teorema de Gdel. Entonces por el lema 2 se obtiene que R es una relacin computable. As pues, por el lema 1 existe una frmula (x0, x1, x2) que cumplir las dos condiciones all expuestas para la relacin R. Sea g el nmero de Gdel de la frmula x1 (x1, x0, x0). Ahora definimos la sentencia como x1 (x1, g , g ). Ahora slo queda comprobar que es una sentencia indecidible. Por definicin se tiene que (t,g,g)R si y slo si t es el nmero de Gdel de una demostracin formal de a partir de . As pues, la sentencia en el metalenguaje nos viene a decir que no existe demostracin de la frmula , es decir, viene a decir No soy demostrable. En resumen, esta frmula reproduce la paradoja del lenguaje ordinario antes comentada.

    Comprobacin de que no se puede demostrar a partir de :Supngase que s se puede demostrar . Sea h nmero de Gdel de una demostracin formal de a partir de . Entonces, (h,g,g)R. Como consecuencia del lema 1 se tiene que ( h , g , g ). Por tanto x1 (x1, g , g ), de donde es inmediato afirmar que . As pues, se puede demostrar a partir de tanto como . Y esto es un absurdo con la suposicin que es consistente.

    Comprobacin de que no se puede demostrar a partir de :Supngase que s se puede demostrar . Entonces aprovechando que es consistente se tiene que no se puede demostrar a partir de . Por tanto, para todo nmero natural h se cumple que (h,g,g)R. Consecuentemente, a partir del lema 1, para todo nmero natural h se tiene que ( h , g , g ). De ah se sigue24 que x1 (x1, g , g ) es mentira, es decir, que no se puede demostrar a partir de . Y eso es un absurdo con la hiptesis de partida.

    3.3 Qu conclusiones filosficas se pueden extraer?

    El teorema de Gdel da pie a cantidad de ideas filosficas tanto sobre la matemtica como sobre el concepto de verdad. Aqu no voy a entrar en ellas, dejar que el lector

    24 Para poder dar este paso no es suficiente suponer que es consistente. Gdel necesit suponer que es -consistente, lo cual quiere decir que dada cualquier frmula (x) tal que para todo nmero natural n se cumple ( n ) entonces es falso que x (x). El teorema de Gdel deberamos haberlo formulado cambiando la hiptesis es consistente por la de es -consistente. Sin ese cambio la justificacin del teorema dada por Gdel no sera correcta. De hecho Gdel enunci su teorema imponiendo la hiptesis de ser -consistente. He optado por enunciarlo de esa otra manera por dos razones: a)ahorrarme introducir el concepto de -consistencia, b)Barkley Rosser, en 1936, vio que la prueba de Gdel retocada un poco permita demostrar el resultado que yo he enunciado como teorema de Gdel. El retoque introducido por Rosser consista en considerar otra sentencia, la cual tiene un carcter bastante menos intuitivo que la utilizada por Gdel.

    Factoriza, examinalos exponentes.Son 5 y 13 los dos primeros y 15 elltimo?

    Derrotado. n no es el nmero de Gdel de un numeral.

    Elimina s, (, y ), y vuelve a codificar lo que queda como n*

  • reflexione personalmente25. Por ltimo, para acabar, simplemente quiero comentar una consecuencia que suele pasar desapercibida. Se trata de una consecuencia religiosa26. Si se define religin como un sistema de ideas que contiene enunciados indemostrables entonces lo que Gdel nos ha mostrado es que la matemtica no es slo una religin, sino que es la nica religin que puede demostrar por s misma que lo es.

    FLIX BOU MOLINER

    Quiero agradecer a los editores la invitacin que me brindaron para escribir estas pginas. Y tambin quiero agradecer los comentarios realizados al manuscrito original por Josep Maria Font, scar Ledesma y Ventura Verd. A todos ellos gracias.

    Bibliografa

    Para escribir la parte biogrfica de Gdel he consultado bsicamente [Da1], [Da2], [Reg] y [Wan]. Las fuentes usadas a propsito del teorema de Gdel han sido principalmente [Cro] y [Men], y en menor medida [Da1], [Nag], [Pla], [Re1], [Re2].Las obras sealadas con asterisco son aquellas que requieren una familiaridad con el aparato matemtico de la lgica, mientras que el resto son principalmente de carcter divulgativo.

    [Bar] John D. Barrow. Por qu el mundo es matemtico?. Grijalbo Mondadori, 1997.[Cro] J. N. Crossley. Qu es la lgica matemtica?. Tecnos, 19882.[Da1] John W. Dawson, Jr. Gdel y los lmites de la lgica. Investigacin y Ciencia

    275 (agosto 1999), 58-63.[Da2] John W. Dawson, Jr. Kurt Gdel in Sharper Focus. The mathematical

    intelligencer vol. 6, no. 4 (1984), 9-17.[Hof] Douglas R. Hofstadter. Gdel, Escher, Bach, un eterno y grcil bucle. Tusquets,

    1987.[Men]*Elliott Mendelson. Introduction to mathematical logic. Wadsworth &

    Brooks/Cole, 19873. [Mos]*Jess Mostern. Kurt Gdel: Obras completas. Alianza, 19892.[Nag] Ernest Nagel y James R. Newman. El teorema de Gdel. Tecnos, 19942.[Pla] *Josep Pla i Carrera. Kurt Gdel: dos teoremes i una metodologa. Actes II

    Congrs Catal de Lgica Matemtica (1983), 15-21.[Re1] Javier Redal. Esto no es el ttulo. Nueva Dimensin revista de ciencia ficcin y

    fantasa 135 (junio 1981), 96-99.[Re2] Javier Redal. Es el ttulo de este artculo es el ttulo de este artculo. Nueva

    Dimensin revista de ciencia ficcin y fantasa 135 (junio 1981), 119-138.[Reg] Ed Regis. Quin ocup el despacho de Einstein?. Anagrama, 1992, 64-91.[Rod] Francisco Rodrguez Consuegra. Kurt Gdel. Ensayos inditos. Biblioteca

    Mondadori 42, 1994.[Wan] Hao Wang. Reflexiones sobre Kurt Gdel. Alianza Universidad, 1987.

    25 El lector interesado en cuestiones filosficas encontrar interesantes los libros [Rod] y [Wan].26 Aparece en [Bar, pg. 77].