Teoremas de incompletitud de Gödel

En lógica matemática, los teoremas de incompletitud de Gödel son dos célebres teoremas demostrados por Kurt Gödel en 1930. Simplificando, el primer teorema afirma:

En cualquier formalización consistente de las matemáticas que sea lo bastante fuerte para definir el concepto de números naturales, se puede construir una afirmación que ni se puede demostrar ni se puede refutar dentro de ese sistema. Kurt Gödel

Este teorema es uno de los más famosos fuera de las matemáticas, y uno de los peor comprendidos. Es un teorema en lógica formal, y como tal es fácil malinterpretarlo. Hay multitud de afirmaciones que parecen similares a este primer teorema de incompletud de Gödel, pero que en realidad no son ciertas. Éstas se comentan en Malentendidos en torno a los teoremas de Gödel.

El segundo teorema de la incompletitud de Gödel, que se demuestra formalizando parte de la prueba del primer teorema dentro del propio sistema, afirma:

Ningún sistema consistente se puede usar para demostrarse a sí mismo. Kurt Gödel

Este resultado fue devastador para la aproximación filosófica a las matemáticas conocida como el programa de formalización Hilbert. David Hilbert propuso que la consistencia de los sistemas más complejos, tales como el análisis real, se podía probar en términos de sistemas más sencillos. Finalmente, la consistencia de todas las matemáticas se podría reducir a la aritmética básica. El segundo teorema de la incompletud de Gödel demuestra que la aritmética básica no se puede usar para demostrar su propia consistencia, y por lo tanto tampoco puede demostrar la consistencia de nada más fuerte.

Significado de los teoremas de Gödel

Los teoremas de Gödel son teoremas en lógica de primer orden, y deben entenderse en ese contexto. En lógica formal, tanto las afirmaciones matemáticas como las demostraciones se escriben en un lenguaje simbólico en el que se puede comprobar mecánicamente la validez de las pruebas. De este modo no puede haber ninguna duda de que un teorema se deduce de nuestra lista inicial de axiomas. En teoría, este tipo de pruebas se puede verificar con un ordenador; de hecho, hay programas que lo hacen. Para poder realizar este proceso se necesita saber cuáles son estos axiomas. Se puede partir de un conjunto finito de axiomas, como en la geometría euclídea, o más en general se puede permitir un número infinito de axiomas con el requisito de que dada una afirmación se pueda verificar mecánicamente si ésta es uno de los axiomas. Aunque pueda sonar extraño el uso de un número infinito de axiomas, esto es precisamente lo que se hace habitualmente con los números naturales, los axiomas de Peano.

El primer teorema de la incompletitud de Gödel demuestra que cualquier sistema que permita definir los números naturales es necesariamente incompleto: contiene afirmaciones que ni se pueden demostrar ni refutar.

La existencia de un sistema incompleto no es en sí particularmente sorprendente. Por ejemplo, si se elimina el postulado del paralelismo de la geometría euclídea se obtiene un sistema incompleto. Un sistema incompleto puede significar simplemente que no se han descubierto todos los axiomas necesarios.

Lo que mostró Gödel es que en la mayoría de los casos, como en la teoría de números o en análisis real, nunca se puede descubrir el conjunto completo de axiomas. Cada vez que se añada un nuevo axioma siempre habrá otro que quede fuera de alcance.

También se puede añadir un conjunto infinito de axiomas. Por ejemplo, todas las afirmaciones verdaderas sobre los números naturales, pero esa lista no será un conjunto recursivo. Dada una afirmación cualquiera, no habrá forma de saber si es un axioma en el sistema o no. Dada una prueba no habrá en general una manera de verificar que esa prueba es válida.

El teorema de Gödel tiene otra interpretación en el contexto de la informática. En lógica de primer orden, los teoremas son recursivamente enumerables: se puede construir un programa de ordenador que terminará por dar una demostración válida. Sin embargo, no cumplen la propiedad más fuerte de ser un conjunto recursivo: no se puede construir un programa que dada una afirmación cualquiera determine si ésta es cierta o no.

Muchos lógicos piensan que los teoremas de incompletud de Gödel asestaron un mazazo fatal al programa de formalización de Hilbert que apuntaba a un formalismo matemático universal. La postura aceptada generalmente es que fue el segundo teorema el que asestó este golpe. Algunos sin embargo piensan que fue el primero, e incluso hay quien piensa que ninguno de ellos lo hizo.

Ejemplos de afirmaciones indecidibles

La existencia de una afirmación indecidible dentro de un sistema formal no es en sí misma un fenómeno sorprendente.

El subsiguiente trabajo combinado de Gödel y Paul Cohen ha dado ejemplos concretos de afirmaciones indecidibles: tanto el axioma de elección como la hipótesis del continuo son indecidibles en la axiomatización estándar de teoría de conjuntos. Esos resultados no requieren del teorema de incompletitud.

En 1936, Alan Turing demostró que el problema de la parada (la cuestión de si una máquina de Turing parará al introducirle unos datos) es indecidible. Más tarde este resultado se generalizó en el campo de las funciones recursivas en el Teorema de Rice que demuestra que todos los problemas de decisión que no son triviales son indecidibles en un sistema que sea Turing-completo.

En 1973, se demostró que el problema de Whitehead en teoría de grupos es indecidible en la teoría estándar de grupos. En 1977, Kirby, Paris y Harringon demostraron que una afirmación en combinatoria, una versión del teorema de Ramsey, es indecidible en la axiomatización de la aritmética dada por los axiomas de Peano pero se puede demostrar cierta en el más amplio sistema de la teoría de conjuntos. El algoritmo de Kruskal, que tiene implicaciones en informática, también es indecidible a partir de los axiomas de Peano pero demostrable en teoría de conjuntos. Asimismo, el teorema de Goodstein es una afirmación relativamente simple sobre los números naturales que es indecidible en la aritmética de Peano.

Gregory Chaitin produjo afirmaciones indecidibles en teoría algorítmica de la información y de hecho demostró su propio teorema de la incompletud en ese contexto.

Uno de los primeros problemas de los que se sospechó que serían indecidibles fue el problema de equivalencia de enunciados sobre grupos, propuesto inicialmente por Max Dehn en 1911, el cual establece que existe un grupo representado de forma finita para el cual no existe algoritmo que decida si dos fórmulas que sólo hablan sobre propiedades de esos grupos son equivalentes. El carácter indecidible de este enunciado no fue demostrado sino hasta 1952.

Malentendidos en torno a los teoremas de Gödel

Puesto que el primer teorema de la incompletud de Gödel es tan famoso, ha dado origen a multitud de malentendidos. Aquí resumimos algunos:

1. El teorema no implica que todo sistema axiomático interesante sea incompleto. Por ejemplo, la geometría euclídea se puede axiomatizar de forma que sea un sistema completo. (De hecho, los axiomas originales de Euclides son casi una axiomatización completa. Los axiomas que faltan expresan propiedades que parecen tan obvias que fue necesaria la aparición de la idea de la prueba formal hasta que se echaron en falta). Sin embargo hasta en un sistema completo como el de la geometría habrá construcciones imposibles (trisección del ángulo, cuadratura del círculo).
2. El teorema sólo se aplica a sistemas que permitan definir los números naturales como un conjunto. No basta con que el sistema contenga los números naturales. Además debe ser capaz de expresar el concepto "$x$ es un número natural" usando los axiomas y la lógica de primer orden. Hay multitud de sistemas que contienen a los números naturales y son completos. Por ejemplo, tanto los números reales como los números complejos tienen axiomatizaciones completas.

Discusión e implicaciones

Los resultados de incompletud afectan a la filosofía de las matemáticas, particularmente a los puntos de vista tales como el formalismo, que usa la lógica formal para definir sus principios. Se puede parafrasear el primer teorema diciendo "nunca se podrá encontrar un sistema axiomático que sea capaz de demostrar todas las verdades matemáticas y ninguna falsedad."

Por otra parte, desde una perspectiva estrictamente formalista esta paráfrasis se consideraría sin significado porque presupone que la «verdad» y «falsedad» matemáticas están bien definidas en un sentido absoluto, en lugar de ser relativas a cada sistema formal

La siguiente reformulación del segundo teorema es todavía más inquietante para los fundamentos de las matemáticas:

Si se puede demostrar que un sistema axiomático es consistente a partir de sí mismo, entonces es inconsistente.

Por tanto, para establecer la consistencia de un sistema $S$ se necesita utilizar otro sistema $T$, pero una prueba en $T$ no es totalmente convincente a menos que la consistencia de $T$ ya se haya probado sin emplear $S$. La consistencia de los axiomas de Peano para los números naturales por ejemplo se puede demostrar en la teoría de conjuntos, pero no en la teoría de los números naturales por sí sola. Esto proporciona una respuesta negativa al problema número dos de la famosa lista de cuestiones abiertas importantes en matemáticas de David Hilbert (llamada problemas de Hilbert).

En principio, los teoremas de Gödel todavía dejan alguna esperanza: podría ser posible producir un algoritmo general que para una afirmación dada determine si es indecidible o no, permitiendo a los matemáticos evitar completamente los problemas indecidibles. Sin embargo, la respuesta negativa al Entscheidungsproblem demuestra que no existe tal algoritmo.

Es de notar que los teoremas de Gödel sólo son aplicables a sistemas axiomáticos suficientemente fuertes. Este término significa que la teoría contiene la suficiente aritmética para llevar a cabo las instrucciones de codificación requeridas por la prueba del primer teorema de incompletud. Esencialmente, todo lo que se exige son algunos hechos básicos sobre la adición y la multiplicación tal y como por ejemplo se formalizan en la aritmética Q de Robinson. Hay sistemas axiomáticos incluso más débiles que son consistentes y completos, por ejemplo la aritmética de Presburger que demuestra todas las afirmaciones de primer orden ciertas aplicando sólo la suma.

El sistema axiomático puede consistir en un número infinito de axiomas (tal y como hace la aritmética de primer orden de Peano), pero para poder aplicarse el teorema de Gödel debe haber un algoritmo efectivo que sea capaz a verificar la corrección de las pruebas. Por ejemplo, el conjunto de todas las declaraciones de primer orden que son ciertas en el modelo estándar de los números naturales es completo. El teorema de Gödel no se puede aplicar porque no hay ningún procedimiento efectivo que decide si una cierta declaración es un axioma. De hecho, que esto sea así es una consecuencia del primer teorema de incompletud de Gödel.

Otro ejemplo de una especificación de una teoría en la que el primer teorema de Gödel no es aplicable se puede construir de la siguiente manera: ordenemos todas las posibles declaraciones sobre los números naturales primero por su longitud y luego en orden lexicográfico; comencemos con un sistema axiomático inicialmente igual a los axiomas de Peano, repasemos la lista de declaraciones una a una, y, si la declaración actual no se puede demostrar ni refutar a partir del actual sistema de axiomas, entonces añadámosla a la lista. Esto crea un sistema que es completo, consistente y suficientemente potente, pero no recursivamente enumerable.

El propio Gödel sólo demostró una versión de los teoremas arriba expuestos que es técnicamente un poco más débil; la primera demostración de las versiones descritas arriba fue dada por J. Barkley Rosser en 1936.

En esencia, la prueba del primer teorema consiste en construir una declaración $p$ dentro de un sistema formal axiomático al que se le puede dar la siguiente interpretación meta matemática:

$p=$ «Esta declaración no se puede probar.»

Como tal, puede verse como una versión moderna de la paradoja del mentiroso. Al contrario de la declaración del mentiroso, $p$ no se refiere directamente a sí mismo; la interpretación de arriba sólo se puede "ver" desde fuera del sistema formal.

En un trabajo publicado en 1957 en Journal of Symbolic Logic, Raymond Smullyan mostró que los resultados de incompletitud de Gödel pueden obtenerse para sistemas mucho más elementales que los considerados por Gödel. Smullyan también ha reivindicado las pruebas más simples con el mismo alcance, basadas en los trabajos de Alfred Tarski sobre el concepto de verdad en los sistemas formales. Más simples, pero no menos perturbadoras filosóficamente. Smullyan no ha plasmado sus reflexiones sobre incompletitud sólo en obras técnicas; también han inspirado célebres libros de divulgación como ¿Cómo se llama este libro?.

Si el sistema axiomático es consistente, la prueba de Gödel muestra que $p$ (y su negación) no se pueden demostrar en el sistema. Por tanto $p$ es cierto ($p$ afirma no ser demostrable y no lo es) y, sin embargo, no se puede probar formalmente en el sistema. Fíjese que añadir $p$ a los axiomas del sistema no resolvería el problema: habría otra sentencia de Gödel para la teoría ampliada.

Roger Penrose afirma que esta (presunta) diferencia entre lo que se puede probar mecánicamente y lo que los humanos pueden ver como cierto muestra que la inteligencia humana no es mecánica en su naturaleza. También JR Lucas ha atendido esta reivindicación en Mentes, Máquinas y Gödel (en inglés).

Esta perspectiva no está ampliamente aceptada, porque tal y como lo plantea Marvin Minsky, la inteligencia humana es capaz de errar y de comprender declaraciones que son en realidad inconsistentes o falsas. Sin embargo, Minsky ha informado de que Kurt Gödel le dijo a él en persona que él creía que los seres humanos tienen una forma intuitiva, no solamente computacional, de llegar a la verdad y por tanto su teorema no limita lo que puede llegar a ser sabido como cierto por los humanos.

Véanse Refutaciones a la interpretación de Penrose en los Enlaces en Inglés de la sección Enlaces externos y referencias

La posición de que el teorema muestra que los humanos tienen una habilidad que transciende la lógica formal también se puede criticar de la siguiente manera: No sabemos si la sentencia $p$ es cierta o no, porque no sabemos (ni podemos saber) si el sistema es consistente. De modo que en realidad no sabemos ninguna verdad que esté fuera del sistema. Todo lo que sabemos es lo siguiente:

O $p$ es indemostrable dentro del sistema, o el sistema es inconsistente.

Esta declaración es fácilmente demostrable dentro del sistema.

Otra implicación es que el trabajo de Gödel motivó a Alan Turing (1912-1954) a estudiar qué funciones eran susceptibles de poder ser calculadas y cuáles no. Para ello se sirvió de su Máquina de Turing, una máquina de propósito general mediante la que formalizó las funciones y procedimientos de cálculo. Demostrando que existían funciones que no son posibles de calcular mediante la Máquina de Turing. El paradigma de este conjunto de funciones lo representa la función que establece "si dada una Máquina de Turing, ésta produce un resultado o, por el contrario, se queda calculando indefinidamente". Esta función, conocida con el nombre de Problema de parada (Halting Problem), será pieza fundamental para demostrar la incomputabilidad de ciertas funciones.

Esbozo de prueba para el primer teorema

El principal problema en ensamblar la idea de demostración arriba mencionada es el siguiente: para construir una declaración $p$ que sea equivalente a «$p$ no se puede demostrar», $p$ tendría que de alguna manera contener una referencia a $p$ que pudiese dar lugar a una regresión infinita. Describiremos abajo el ingenioso truco de Gödel, que más tarde sería utilizado por Alan Turing para resolver el Entscheidungsproblem.

Para empezar, toda fórmula o declaración que se puede formular en nuestro sistema obtiene un identificador único, llamado su número de Gödel. Esto se hace de una manera tal que es fácil convertir mecánicamente entre fórmulas y números de Gödel. Dado que nuestro sistema es lo bastante fuerte para razonar sobre números, ahora también es posible razonar sobre fórmulas.

Una fórmula $F(x)$ que contiene exactamente una variable libre $x$ se llama una forma declarativa. Tan pronto como $x$ se reemplaza por un número específico, la declaración se transforma en una declaración bona fides, y es o bien demostrable en el sistema o no. Las formas declarativas no son declaraciones y por tanto no se pueden probar o refutar. Sin embargo, cada forma declarativa $F(x)$ tiene un número de Gödel que denotaremos como $G(F)$. La selección de la variable libre elegida en la forma $F(x)$ no es relevante para la asignación del número de Gödel $G(F)$.

Mediante el análisis cuidadoso de los axiomas y reglas del sistema, se puede escribir una forma declarativa $P(x)$ que encarna la idea de $x$ es el número de Gödel de una declaración que puede demostrarse en nuestro sistema. Formalmente: $P(x)$ se puede probar si $x$ es el número de Gödel de una declaración demostrable, y su negación ${\bar {P}}(x)$ se puede probar si no lo es. (Aunque esto es adecuado para este esbozo de prueba, técnicamente no es completamente exacto. Vea el artículo de Gödel para este problema y el artículo de Rosser para la resolución. La palabra clave es omega-consistencia).

Ahora viene el truco: una forma declarativa $F(x)$ se denomina auto-indemostrable si la forma $F$, aplicada a su propio número de Gödel, no es demostrable. Este concepto se puede definir formalmente, y se puede construir una forma declarativa $SU(z)$ cuya interpretación es que z es el número de Gödel de una forma declarativa auto-indemostrable. Formalmente, $SU(z)$ se define como: $z=G(F)$ para alguna forma particular $F(x)$, e $y$ es el número de Gödel de la declaración $F(G(F))$, y ${\bar {P}}(y)$. Ahora la declaración deseada $p$, que fue mencionada previamente, se puede definir como:

$p=SU(G(SU))$.

Intuitivamente, cuando nos preguntamos si $p$ es cierto, preguntamos «¿Es la propiedad de ser auto-indemostrable ella misma auto-indemostrable?.» Esto es reminiscente de la paradoja del barbero sobre un barbero que afeita a todas aquellas personas del pueblo que no se afeitan a sí mismas: ¿se afeita él a sí mismo?

Ahora asumiremos que nuestro sistema axiomático es consistente.

Si $p$ fuese demostrable, entonces $SU(G(SU))$ sería cierto, y por la definición de $SU$, $z=G(SU)$ sería el número de Gödel de una forma declarativa auto-indemostrable. Por tanto, $SU$ sería auto-indemostrable, lo que por definición de ese término implica que $SU(G(SU))$ no es demostrable, pero ese era nuestro $p$: $pnoesdemostrable$. Esta contradicción muestra que $p$ no puede ser demostrable.

Si la negación de $p=SU(G(SU))$ fuese probable, entonces por definición de $SU$ esto significaría que $z=G(SU)$ no es el número de Gödel de una forma auto-indemostrable, lo que implica que $SU$ no es auto-indemostrable. Por definición de auto-indemostrable, concluimos que $SU(G(SU))$ es demostrable, y por tanto $p$ es demostrable. De nuevo una contradicción. Esto deja manifiesto que tampoco la negación de $p$ puede ser demostrable.

De modo que la afirmación $p$ ni se puede probar ni refutar en nuestro sistema.

Esbozo de prueba del segundo teorema

Sea $p$ la sentencia indecidible construida previamente, y asumamos que la consistencia del sistema se puede probar dentro del propio sistema. Hemos visto arriba que si el sistema es consistente, entonces $p$ no es demostrable. La prueba de esta implicación se puede formalizar en el propio sistema, y por tanto la afirmación «$p$ no es demostrable», o «no $P(p)$» se puede demostrar en el sistema.

Pero esta última declaración es equivalente a $p$ mismo (y esta equivalencia se puede demostrar en el sistema), de modo que $p$ se puede demostrar en el sistema. Esta contradicción pone de manifiesto que el sistema debe ser inconsistente.

Véase también

• Consistencia lógica
• Autorreferencia
• Logicismo
• Mentes, Máquinas y Gödel
• Teorema de Löb
• Teorema de completitud de Gödel

Enlaces externos y referencias

Raymond Smullyan,Gödel's Incompleteness Theorems, Oxford University Press, 1992 ISBN 0-19-504672-2

Enlaces en inglés.

• Kurt Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik, 38 (1931), pp. 173-198.

Traducido al castellano en: Kurt Gödel: Obras completas. Jesús Mosterín y otros (Trad.) Alianza Editorial, Madrid (1981). ISBN 84-206-2286-9

• B. Rosser: Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic, 1 (1936), N1, pp. 87-91
• Kārlis Podnieks: Around Goedel's Theorem, http://www.ltn.lv/~podnieks/gt.html
• Hofstadter, Douglas R. 1979: Gödel, Escher, Bach: un Eterno y Grácil Bucle. TusQuets editores, tercera edición (1989), Barcelona. ISBN 84-7223-459-2
• Ernest Nagel, James Roy Newman, Douglas R. Hofstadter: Gödel's Proof, edición revisada (2002). ISBN 0-8147-5816-9.
• Hilbert's second problem
• Norbert Domeisen, Logik der Antinomien. Bern etc.: Peter Lang. 142 S. 1990. (ISBN 3-261-04214-1), Zentralblatt MATH

• Refutaciones a la interpretación de Penrose:
  • Is Mathematical Insight Algorithmic?
  • How Subtle is Gödel's Theorem
  • Why Gödel's Theorem Cannot Refute Computationalism
  • Human and Machine Understanding of Mathematics

Enlaces en castellano

Ignacio Jané, La obra de Gödel en lógica matemática y teoría de conjuntos Una introducción sintética e histórica que respeta los conceptos originales, evitando malentendidos.

Reseña en castellano de Torkel Frazen, Gödel's theorem : an incomplete guide to its use and abuse. El libro de Franzen, de 2005, está siendo muy citado como obra de interés para introducir al verdadero sentido de los teoremas de Gödel y prevenir frente a su aplicación injustificada en campos no matemáticos.

• Guillermo Martinez (escritor) , Seix Barral, Gödel para todos , 1ºedición, 2009, ISBN 978-950-731-605-0