Teorema de Incompletitud

Teoremas de Incompletitud
Información sobre la plantilla
Kurt Gödel.jpg
Concepto:dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1930. Ambos están relacionados con la existencia de proposiciones indecidibles en ciertas teorías aritméticas.

Teoremas de Incompletitud. afirma que, bajo ciertas condiciones, ninguna teoría matemática formal capaz de describir los números naturales y la aritmética con suficiente expresividad, es a la vez consistente y completa. Es decir, si los axiomas de dicha teoría no se contradicen entre sí, entonces existen sentencias que no pueden probarse ni refutarse. Las teorías aritméticas para las que el teorema es válido son básicamente aquellas en las que la deducción de teoremas puede realizarse mediante un algoritmo.

La prueba del teorema es totalmente explícita: en ella se construye una fórmula, denotada habitualmente G en honor a Gödel, para la que dada una demostración de la misma, puede construirse una refutación, y viceversa. Sin embargo, la interpretación natural de dicha sentencia en términos de números naturales es verdadera. El segundo teorema de incompletitud es un caso particular del primero: afirma que una de las sentencias indecidibles de dicha teoría es aquella que "afirma" la consistencia de la misma. Es decir, que si es sistema en cuestión es consistente, no es posible probarlo dentro del propio sistema.

Enunciado de los teoremas

Contexto

Los teoremas de incompletitud se formulan en el contexto de una teoría formal de primer orden. Una teoría de primer orden no es más que un modelo simplificado del razonamiento matemático, formado por dos elementos:

  • Un lenguaje formal, que consta de un conjunto de signos, y de una sintaxis, que determina qué cadenas de signos son fórmulas bien formadas.
  • Un cálculo deductivo, formado por las reglas de inferencia, que definen cuando, de una serie de formulas dadas, una de ellas es «consecuencia» del resto; y por los axiomas, un cierto conjunto de fórmulas (que puede ser infinito).

Con estos elementos se estudia el concepto de demostración: los teoremas son aquellas fórmulas que se obtienen de una cadena de fórmulas que, o bien son axiomas, o bien son consecuencia de fórmulas anteriores.

La consistencia de una teoría es un requisito básico para que sea útil, ya que según el principio de explosión, una teoría inconsistente demuestra cualquier fórmula. La completitud es una característica "deseable", que permitiría que una teoría tuviera una "respuesta" para cada "pregunta" que pueda formularse en su lenguaje. El primer teorema de incompletitud establece que, bajo ciertas hipótesis, una teoría formal no puede tener ambas características.

La primera de estas hipótesis es que la teoría sea aritmética. Una teoría aritmética es una teoría formal que incluye signos capaces de describir los números naturales (como por ejemplo: «+», «×» ó «0»), de modo que bien sus axiomas o bien sus teoremas contengan los llamados axiomas de Peano, que son los enunciados básicos de la aritmética.

La segunda hipótesis es que la teoría sea recursiva, lo cual significa básicamente que el procedimiento para distinguir

  • las fórmulas bien formadas de las que no lo son,
  • si una fórmula es consecuencia de otras o no,
  • si una fórmula dada es un axioma o no, es un algoritmo, y puede ser llevado a cabo sin ambigüedad en un tiempo finito.

Preliminares

Conceptos que ayudaran a una mejor comprensión del teorema. En primer lugar debe saberse qué es una paradoja. Una paradoja es una proposición que se contradice a sí misma, una proposición incoherente. Un buen ejemplo de paradoja es la famosa frase de Sócrates "Sólo sé que no sé nada". Obviamente, si no sabe nada, ya sabe algo, luego la proposición se contradice a sí misma. La contradicción de esta paradoja surge en el momento en que Sócrates hace referencia a si mismo. El teorema de Gödel tiene mucho que ver con proposiciones que hacen referencia a si mismas.

Otra paradoja bastante antigua es la conocida como "paradoja de Epiménides o del mentiroso" que decía "Los cretenses, siempre embusteros". Como Epiménides era cretense podemos traducir la afirmación así: "Siempre miento. Nunca digo la verdad". ¿Qué se puede inferir de esta paradoja? Si Epiménides siempre miente, dicha afirmación sería falsa, por lo tanto, no siempre miente y siempre dice la verdad. Pero si dice la verdad, la afirmación resultaría ser cierta, por lo tanto, siempre miente y nunca dice la verdad. Y así podríamos continuar hasta el infinito, sin llegar a nada concreto. De nuevo, la autorreferencia produce una paradoja.

Una variante de la paradoja de Epiménides es la siguiente: supongamos que nos encontramos con Epiménides y nos dice: "Esta aseveración es falsa". ¿Dice la verdad o miente? Nuevamente la autorreferencia produce una paradoja. Siempre nos encontramos con la autorreferencia. Pensemos más detenidamente en este caso y démosle otro aspecto usando lenguaje matemático. Digamos que:

B = [Esta aseveración no es verdad] = [B es falsa]

La pregunta es, ¿B es falsa o cierta? Son las dos únicas opciones. Vamos a analizarlas y ver que situaciones plantean. Supongamos que B es cierta. Si B es cierta, la aseveración "B es falsa" es verdadera. Vaya, nos encontramos ante una contradicción. ¿Qué tal si probamos con la otra opción? Vamos a suponer ahora que B es falsa. Si esto es así, nos encontramos con que la aseveración "B es falsa" no es verdad, luego podríamos decir que "B es cierta", pero ¿no habíamos dicho que B era falsa? Una nueva contradicción.


Esta paradoja será muy útil para Gödel, quien sustituye la palabra "verdad" por "demostrable". Gödel crea la proposición G, donde:

G = [Esta aseveración no es demostrable] = [G es indemostrable]

Gödel nos dice que puede que G sea verdad, pero que no lo demostraremos nunca. Nos encontramos ante el hecho de que el hecho de que una proposición sea verdadera tiene más peso que el hecho de que sea demostrable.


Otra curiosa paradoja es la siguiente:

La siguiente oración es falsa. 
La oración anterior es verdadera. 

Dejamos al lector el trabajo de encontrar la incoherencia, pero no podemos dejar de señalar que nuevamente el fenómeno de la autorreferencia provoca la paradoja. En este caso particular cada proposición hace referencia a la otra, con lo que se crea un "bucle infinito". Otro caso parecido es el conocido dibujo de M. C. Escher, "Manos que dibujan". Si el lector quisiera saber más sobre estos "eternos y gráciles bucles", le recomendamos el libro "Gödel, Escher, Bach. Un eterno y grácil bucle" de Douglas R. Hofstadter.

Primer teorema

La demostración de este teorema pasa por construir una cierta fórmula, la "sentencia de Gödel" G y demostrar que no puede ser probada ni refutada en T, es decir, es independiente o indecidible. Para ello, dado que en una teoría recursiva toda demostración es un procedimiento algorítmico, Gödel desarrolló un método para codificar fórmulas y demostraciones mediante números y operaciones sobre los mismos, llamado numeración de Gödel. Una vez hecho esto, la sentencia G es aquella que afirma «no existe un número x con la propiedad P», donde la propiedad P, al ser examinada a la luz de esta equivalencia entre números y fórmulas, significa «ser la demostración (en la teoría T) de G». Por lo tanto, la sentencia G afirma «no soy demostrable en la teoría T». (Véase el razonamiento detallado más abajo).

El hecho de que G no sea demostrable implica que es cierta —pues afirma su propia indemostrabilidad—, en la interpretación natural en que las variables de la teoría se interpretan como los números naturales. Esto significa que ninguna teoría aritmética en las condiciones del teorema puede demostrar todos los enunciados verdaderos de la aritmética. Además el hecho de que ¬G tampoco sea demostrable significa que si se toma como axioma, la teoría resultante T' = T + ¬G es también consistente, a pesar de que ¬G es falsa en su interpretación natural. Toda teoría de primer orden consistente tiene un modelo, esto es, un conjunto de objetos matemáticos para los que los teoremas de T son afirmaciones verdaderas; y un modelo de T' es a su vez un modelo de T (puesto todos los teoremas de T lo son de T'). Este hecho indica entonces la existencia de modelos no estándar de la aritmética: cualesquiera que sean los objetos que describe la teoría T', verifican todos los teoremas aritméticos, pero no son los números naturales (para los que ¬G es falsa). En otras palabras, el primer teorema de incompletitud asegura que las teorías de primer orden no pueden caracterizar totalmente los objetos que describen.

Nótese que tomar G (o su contraria) como axioma da lugar a una nueva teoría T' en la que G (o su contraria) es trivialmente demostrable. Sin embargo esto no invalida el teorema, puesto que G (o su contraria) hablan de «demostrabilidad en T». T' es también incompleta: puede escribirse una nueva sentencia G' que afirma «no soy demostrable en T'». En definitiva, para una teoría formal que sea consistente y completa debe fallar alguna de las hipótesis: o bien no es recursiva y no hay un algoritmo para distinguir los axiomas del resto de fórmulas, como es el caso de las extensiones consistentes que se construyen en el teorema de completitud de Gödel; o bien no son aritméticas, en el sentido de que no describen una porción lo suficientemente grande de los números naturales y sus axiomas, como la aritmética de Presburger.

Segundo teorema

El enunciado del segundo teorema hace referencia a una fórmula, Consis T, que puede construirse en cualquier teoría T (ver más abajo), y que afirma que la teoría T es consistente. La sentencia Consis T expresa sencillamente, utilizando de nuevo la "equivalencia" entre demostraciones y operaciones numéricas, «no existe una demostración de 0 = 1» (la ausencia de demostración para alguna fórmula es equivalente la consistencia de la teoría, debido al principio de explosión). Entonces se tiene:

Para demostrar que Consis T no es un teorema, se ha de utilizar una vez más la numeración de Gödel y la capacidad expresiva de las teorías aritméticas para convertir el primer teorema de incompletitud en el teorema formal Consis T ⇒ ¬∃x P(x), donde P es la propiedad mencionada anteriormente de «ser una demostración de G». Puesto que G afirma su propia indemostrabilidad, este teorema formal es equivalente a Consis T ⇒ G, por lo que si Consis T fuera demostrable, por pura deducción formal G también lo sería, lo cual es imposible si T es consistente (según el primer teorema de incompletitud).

El segundo teorema de incompletitud impone serias limitaciones a la hora de demostrar la consistencia de una teoría formal T: nunca podrá hacerse utilizando únicamente la propia T. Si se utiliza una extensión T' en la que Consis T pueda demostrarse, la propia consistencia de T' no podrá demostrarse ni en T ni en T'.

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 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.

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.

Malos entendidos 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 malos entendidos. Aquí resumimos algunos:

  • 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.

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.

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. 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.

Demostración del primer teorema

Sea una teoría formal aritmética y recursiva T ω-consistente. Sea la fórmula ¬∃z, DEM(z, x), donde DEM es la fórmula que expresa la relación numérica Dem —relativa a la teoría formal T—. Por el lema de diagonalización existe una sentencia G con número de Gödel g, para la que se demuestra G ⇔ ¬∃z, DEM(z, [g]), es decir, que afirma «ningún número codifica una demostración (en T) de la fórmula representada por g», o de otro modo, «no soy demostrable (en T)». La negación de esta sentencia, ¬G, es equivalente a ∃z, DEM(z, [g]), o «mi negación es demostrable (en T)».

Supóngase entonces que G puede demostrarse. Entonces existe un número n que cumple Dem(n, g), y en T puede probarse entonces DEM([n], [g]), lo cual implica formalmente ¬G; y esto es imposible si T es consistente. Por tanto no existe una demostración de G, y se cumple ¬Dem(n, g) para todos los números n, lo cual resulta en un número infinito de teoremas formales ¬DEM([n], [g]) para cada numeral [n]. Como T es ω-consistente, no puede ocurrir entonces que ∃x, DEM(x, [g]) sea un teorema, por lo que ¬G es indemostrable, y T es indecidible.

Demostración del segundo teorema

La demostración del segundo teorema de incompletitud requiere de un hecho técnico que Gödel originalmente no probó. Sea una teoría T en las condiciones anteriores y sea la fórmula Consis T ≡ ¬∃z, DEM(z, [k]), donde k es el número de Gödel de la sentencia 0 = 1. Consis T afirma que la teoría T es consistente (pues deja algo sin demostrar). La versión formal (de la primera parte) del primer teorema de incompletitud puede expresarse como Consis T ⇒ ¬∃y, DEM(y, [g]) y esto es equivalente precisamente a Consis T ⇒ G. De modo que, de poder probar formalmente esta sentencia, Consis T sería indemostrable puesto que se tendría entonces una demostración de G, en contradicción con el primer teorema.

El hecho técnico que se necesita es precisamente una prueba de que la demostración del primer teorema de incompletitud puede "traducirse" en una demostración formal de la sentencia Consis T ⇒ ¬∃y, DEM(y, [g]). Esto es posible en toda teoría aritmética recursiva, ya que verifican unas ciertas condiciones de demostrabilidad.

Bibliografía

  • Barwise, Jon (1989) (en inglés). Handbook of mathematical logic. Elsevier. ISBN 9780444863881.
  • Boolos, George; Burgess, John P.; Jeffrey, Richard C. (2007) (en inglés). Computability and logic. Cambridge University Press. ISBN 9780521701464..
  • Hofstadter, Douglas R. (1989). Gödel, Escher, Bach. Tusquets editores. ISBN 84-7223-459-2.
  • Hofstadter, Douglas R.; Nagel, Ernest; Newman, James Roy (2002) (en inglés). Gödel's Proof. NYU Press. ISBN 0-8147-5816-9.
  • Ivorra, Carlos, Lógica y teoría de conjuntos, consultado el 27-07-2011.
  • Martínez, Guillermo (2009). Gödel para todos. Seix Barral. ISBN978-950-731-605-0.Smullyan, Raymond (1992) (en inglés). Gödel's Incompleteness Theorems. Oxford University Press. ISBN 0-19-504672-2.

Fuentes