La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Gödel en una cáscara de nuez: Segundo Teorema de Incompletitud, y Teorema de Completitud

Posted by Carlos en marzo 29, 2007

Cuando empezamos a recorrer los resultados de Gödel y mencionamos el contexto histórico mereció especial atención el programa formalista de Hilbert. Hay que recordar que el objetivo de Hilbert era definir un sistema formal completo y consistente, dentro del cual poder razonar de manera mecánica sobre cualquier noción matemática. El primer teorema de incompletitud que vimos hace unos días asestó un golpe letal a esta pretensión: en cualquier sistema formal consistente lo suficientemente complejo como para englobar a la aritmética de Peano hay afirmaciones lógicas que son indemostrables e irrefutables. Dando por perdida pues la completitud, nos podemos aferrar a la consistencia: si somos capaces de probar que nuestro sistema es consistente, tendremos al menos una garantía de la solidez de las demostraciones que hagamos dentro de él. Aquí es donde entra el segundo teorema de incompletitud para rematar definitivamente las aspiraciones de Hilbert.

El segundo teorema de incompletitud de Gödel surge casi como un corolario del primero, aunque su trascendencia es sin embargo muy grande. Recordemos que el primer teorema de incompletitud afirmaba que había una fórmula G (realmente la fórmula G depende del sistema S, por lo que deberíamos emplear la notación GS, pero mantendremos la G por simplificar), tal que ni G ni ~G eran demostrables dentro del sistema si éste era consistente. Siguiendo con la notación que empleamos:

{\rm Cons}(S) \Rightarrow \left[\sim\exists x D(x,g(G))\right]\wedge \left[\sim\exists x D(x,g(\sim G))\right]

Recordemos también que G se define como:

G \equiv \sim\exists x D(x,g(G))

por lo que es fácil ver que si tenemos una demostración de la consistencia del sistema, tenemos también una demostración de la indemostrabilidad de G, y por la propia definición de G esto significa que hemos demostrado G. Dado que sabemos que tal demostración nos lleva a la inconsistencia, hemos de concluir que nuestra suposición de partida -la existencia de una demostración de consistencia- es falsa. No podemos por lo tanto demostrar la consistencia del sistema dentro del mismo.

Aunque en su momento los teoremas de incompletitud supusieron un gran impacto, y de hecho acabaron con las ambiciones formalistas de Hilbert, vistos con retrospectiva son la consecuencia evidente de la metodología que se pretendía seguir, basada en la manipulación mecánica de símbolos y fórmulas mediante unos ciertos procedimientos bien definidos. Esto se puede apreciar más claramente si nos fijamos en un resultado anterior del propio Gödel que -quizás para complicar la cosa- se ha venido a denominar el teorema de completitud de Gödel. Este teorema captura muy bien la pretensión de Hilbert, y explica por qué ésta no es posible (o al menos se puede extraer una interpretación a posteriori del porqué).

La clave del teorema de completitud de Gödel es la idea de modelo. Básicamente, cuando definimos el sistema formal especificamos una sintaxis para expresar las fórmulas, así como unos ciertos axiomas y reglas de inferencia. Lo que tenemos ahí es una mera descripción sintáctica, que una vez dotada de una interpretación semántica, da lugar a un modelo del sistema. Por ejemplo, podemos considerar un sistema definido sobre la base de un conjunto de objetos X, y una operación interna binaria que es asociativa, conmutativa, tiene elemento neutro, y cada elemento de X tiene un inverso. Como puede apreciarse, lo que estamos definiendo aquí es un grupo abeliano. Podemos ahora dar una interpretación del conjunto X y de la operación binaria, por ejemplo, los números enteros y la suma, o los reales (menos el 0) y la multiplicación. Si demostramos algo sin hacer uso de una interpretación concreta, entonces eso debera ser cierto para todas las interpretaciones (o modelos) posibles. Decimos entonces que ese algo es universalmente válido para ese sistema.

El teorema de completitud de Gödel afirma que toda fórmula universalmente válida es demostrable. Esto puede comprobarse como sigue: supongamos que tenemos un sistema S y que hay una fórmula F que es universalmente válida para él pero que no es demostrable en él. Podemos construir ahora un sistema S’ en el que incluimos ~F como axioma, lo cual no nos ocasiona contradicción sintáctica ya que F no es demostrable. Según el teorema de existencia de modelos de Henkin, si un sistema es consistente, entonces tiene un modelo M. En dicho modelo será cierto ~F (que es un axioma) y F (que era universalmente válido en S, del que M es también modelo). Llegamos a una contradicción, luego F ha de ser demostrable.

A la luz de lo anterior, puede verse claramente que si algo es universalmente válido debe ser demostrable, y por lo tanto si algo no es demostrable es porque no es universalmente válido. No debe entonces sorprendernos que un sistema consistente sea incompleto: hay formulas que serán ciertas en unos modelos y falsas en otros, por lo que no podemos esperar demostrarlas o refutarlas abstrayéndonos de su interpretación. Esto que puede parecer evidente ahora, no lo era tanto en la época de Gödel (el trabajo de Henkin es de hecho muy posterior al de Gödel).

La noción de validez universal es el eslabón que nos va a permitir enlazar el trabajo de Gödel con la idea de computabilidad. No es la única conexión, pero sí es el enlace histórico que nos lleva por ejemplo al trabajo de Turing. Ésa será la próxima parada.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Anuncios

6 comentarios to “Gödel en una cáscara de nuez: Segundo Teorema de Incompletitud, y Teorema de Completitud”

  1. Pues sí, el gran paso que dió Gödel al hacer tal afirmación (y demostrarla), cambió para siempre el curso de las matemáticas, pero llevándolas por el buen camino por supuesto, muy bueno el artículo, lo esperaba con ganas desde el anterior ^^, y ahora me has dejado con las ganas de leer sobre Turing, el responsable de la clase NP y de las máquinas no deterministas :D, un saludo.

  2. Carlos said

    Gracias J. La próxima parada es Turing y la no-computabilidad, y aún nos quedará un buen trecho después 😉 .

  3. Yo voy a encargar un libro biográfico de Alan Turing mañana, ahora me estoy leyendo uno de Fermat y otro de Euler, la colección es esta:

    http://www.nivola.com/matensuspersonajes.htm

    El de Turing es el numero 24, que no aparece ahí, espero que esté bien, se titula: “Turing, del primer ordenador a la inteligencia artificial” ^^, un saludo.

  4. luis said

    hola alguien me podria ayudar con el tema sobre “MECANISMO DEDUCTIVO PARA Q”,espero que me puedan ayudar.

  5. […] nos los explica muy bien aquí Gödel en una cáscara de nuez: Primer Teorema de Incompletitud y Gödel en una cáscara de nuez: Segundo Teorema de Incompletitud, y Teorema de Completitud). ¿Te resulta muy técnico el trabajo de Carlos? Un resumen breve. El teorema de incompletitud de […]

  6. […] nos los explica muy bien aquí Gödel en una cáscara de nuez: Primer Teorema de Incompletitud y Gödel en una cáscara de nuez: Segundo Teorema de Incompletitud, y Teorema de Completitud). ¿Te resulta muy técnico el trabajo de Carlos? Un resumen breve. El teorema de incompletitud de […]

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: