TEOREMA DE GODEL

Teoremas de incompletitud de Gödel:

Los teoremas de incompletitud de Gödel son dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1931. Ambos están relacionados con la existencia de proposiciones indecidibles en ciertas teorías aritméticas.

 

 

El primer teorema 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 enunciados que no pueden probarse ni refutarse a partir de ellos. En particular, la conclusión del teorema se aplica siempre que la teoría aritmética en cuestión sea recursiva, esto es, una teoría en la que el proceso de deducción pueda llevarse a cabo mediante un algoritmo.

 

La prueba del teorema es totalmente explícita y 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 el sistema de axiomas en cuestión es consistente, no es posible demostrarlo mediante dichos axiomas.

 

Los teoremas de incompletitud de Gödel son uno de los grandes avances de la lógica matemática, y supusieron —según la mayoría de la comunidad matemática— una respuesta negativa al segundo problema de Hilbert.

Los teoremas de incompletitud de Gödel establecen ciertas limitaciones sobre lo que es posible demostrar mediante un razonamiento matemático. Para hablar con precisión sobre qué «puede demostrarse» o no, se estudia un modelo matemático denominado teoría formal. Una teoría formal consta de una serie de signos y un conjunto de reglas para manipularlos y combinarlos. Mediante estas reglas se pueden distinguir ciertas colecciones de signos como fórmulas, y ciertas sucesiones de fórmulas como demostraciones. Los teoremas de una cierta teoría son entonces todas las fórmulas que puedan demostrarse a partir de una cierta colección inicial de fórmulas que se asuman como axiomas.

 

A una teoría formal se le pueden adjudicar ciertas propiedades en función de lo que sea capaz de demostrar.

Una teoría consistente no contiene contradicciones, es decir, no es posible demostrar a la vez una fórmula y su contraria. Una teoría que no sea consistente no tiene utilidad: debido al principio de explosión, a partir de una contradicción pueden demostrarse todas sus fórmulas, y no sirve para modelizar razonamientos matemáticos.

Una teoría completa «responde cualquier pregunta», en el sentido de que para cada una de sus fórmulas o bien es demostrable, o bien existe una demostración de su contraria (es refutable). Una teoría completa es óptima, y se corresponde con la intuición sobre la verdad lógica: al igual que toda sentencia debe ser verdadera o falsa, en una teoría completa toda fórmula es demostrable o refutable.

 

Sin embargo, el primer teorema de incompletitud establece que, bajo ciertas hipótesis, una teoría formal no puede tener ambas propiedades a la vez. La primera de ellas es que sea una teoría aritmética, es decir, que sus símbolos sirvan para describir los números naturales y sus operaciones y relaciones; y que sea capaz de demostrar algunas propiedades básicas sobre ellos. La segunda hipótesis es que sea una teoría recursiva, lo cual significa que las reglas para manipular sus signos y fórmulas en las demostraciones han de poder ejecutarse mediante un algoritmo: una serie precisa de pasos sin ambigüedad que pueda llevarse a cabo en un tiempo finito, e incluso implementarse mediante un programa informático.

Primer teorema:

La demostración de este teorema pasa por construir una cierta fórmula, la «sentencia de Gödel» G, que no puede ser probada ni refutada en T: ni G ni ¬G (la negación de G) son teoremas de T. Se dice entonces que G y ¬G son indecidibles o independientes en T.

 

Para llegar a esta, Gödel desarrolló un método para codificar signos y fórmulas mediante números, llamado numeración de Gödel. Usando esta numeración, es posible traducir las propiedades de una teoría formal T, tales como «estos signos constituyen una fórmula» o «estas fórmulas no son una demostración en T», a propiedades aritméticas de dichos números. En particular, la sentencia de Gödel G es una fórmula aritmética cuyo significado es «no existe una demostración de G en la teoría T», o en otras palabras, «no soy demostrable en la teoría T».

 

Consecuencias:

 

La sentencia de Gödel G no es demostrable pero es cierta, pues afirma precisamente su propia indemostrabilidad. Esto significa que ninguna teoría aritmética en las condiciones del teorema es capaz de demostrar todos los enunciados verdaderos de la aritmética.1

 

Además, aunque ¬G sea falsa (por afirmar lo contrario que G) no es refutable (puesto G es indemostrable). Esta sentencia puede tomarse como axioma si se desea y esto no produce una contradicción. La teoría resultante contiene muchos de los enunciados verdaderos sobre los números naturales y algunos falsos, empezando por ¬G. Los objetos descritos por una teoría así forman un modelo no estándar de la aritmética.

 

Tomando G (o su contraria) como axioma se obtiene una nueva teoría T' en la que G (o su contraria) es demostrable automáticamente. Sin embargo esto no invalida el teorema, puesto que G afirma su indemostrabilidad relativa a la teoría T. La nueva teoría T' es también incompleta: puede encontrarse una nueva sentencia independiente G', que afirma «no soy demostrable en T'».

 

En definitiva, en 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; o bien no son aritméticas, y no incluyen las propiedades básicas necesarias de los números naturales. Por ejemplo, en la demostración del teorema de completitud semántica se utilizan teorías consistentes y completas que no son recursivas. Por otro lado, la aritmética de Presburger es una colección de axiomas sobre los números naturales que omite varias de sus propiedades, hasta el punto de que una teoría basada en ellos puede ser consistente y completa.

Segundo teorema:

El segundo teorema de incompletitud muestra otro ejemplo explícito de una fórmula que ninguna teoría aritmética puede demostrar, además de G. De nuevo, usando la numeración de Gödel, puede encontrarse una fórmula, denotada Consis T, cuyo significado es «no puede encontrarse una contradicción en T», o en otras palabras, «T es consistente».

La demostración del segundo teorema requiere traducir el primero a una fórmula. El primer teorema afirma, entre otras cosas, que si T es consistente, entonces G no es demostrable. La fórmula que afirma la consistencia de T es Consis T, mientras que la fórmula que afirma la indemostrabilidad de G es la propia G. La fórmula que traduce el primer teorema (una parte de él) es Consis T ⇒ G, donde «⇒» significa implicación. Gödel demostró que esta fórmula es un teorema, y que por lo tanto Consis T no es un teorema: si lo fuera, de las reglas básicas de T como teoría formal se deduciría que G es demostrable, en contradicción con el enunciado del primer teorema de incompletitud.

Consecuencias:

El segundo teorema de incompletitud limita las posibilidades de demostrar la consistencia de una teoría formal T, puesto que no puede hacerse utilizando únicamente la propia T. Además, si se encuentra una teoría más fuerte T' en la que Consis T pueda demostrarse, la propia consistencia de T' no podrá demostrarse en T' ni tampoco en T. Por ello, el segundo teorema se considera una respuesta negativa al llamado programa de Hilbert, que proponía demostrar la corrección de los razonamientos matemáticos basados en objetos infinitos usando tan solo razonamientos basados en objetos finitos, menos potentes que los primeros.

La demostración de los teoremas de incompletitud se basa en tres conceptos:

1.La numeración de Gödel, que permite traducir las teorías formales a operaciones de aritmética pura.

2.La potencia expresiva de las teorías formales aritméticas, cuyas expresiones recogen dichas operaciones.

3.El lema diagonal, que permite que las fórmulas sean autorreferentes.

 

El enunciado original debido a Gödel, cuya demostración se esboza en esta sección, es más débil que el presentado arriba, ya que en lugar de la consistencia de la teoría T se exige una propiedad más fuerte, la ω-consistencia.

Una teoría aritmética es ω-inconsistente si, para alguno de sus teoremas formales de la forma ∃x, φ(x), puede refutarse cualquier caso particular, esto es, puede probarse ¬φ([n]), para cada numeral [n]. Una teoría que no es ω-inconsistente se dice ω-consistente.

(Los numerales [n] son los símbolos que utilice el lenguaje de la teoría para especificar los números naturales concretos. En el ejemplo de la aritmética de Peano en la sección siguiente, los numerales son los símbolos dados por: [0] ≡ 0, [1] ≡ S0, [2] ≡ SS0, etc.) La ω-consistencia implica la consistencia (pero no al revés). El enunciado «fuerte», en el que sólo se requiere la consistencia de la teoría fue probado por J. B. Rosser mediante un método muy similar.

 

Numeración de Gödel

 

Artículo principal: Numeración de Gödel

 

La numeración de Gödel es una herramienta que permite relacionar las teorías formales con la aritmética. El lenguaje de una teoría formal de primer orden está compuesto por una cantidad —a lo sumo— numerable de signos, como por ejemplo:

∃ , ⇒ , ¬ , |, =, x , y , z , ... , 0 , + , × , S

en el caso del lenguaje de la aritmética de Peano, donde además de los símbolos lógicos y las variables, aparecen algunos símbolos adicionales para la arimética (donde S es el símbolo para denotar «el número siguiente a»). También el conjunto de todas las cadenas (sucesiones finitas de signos) es numerable, así como el conjunto de las sucesiones finitas de cadenas.

 

Una numeración de Gödel es una asignación de un único número natural para cada elemento de cada uno de estos tres conjuntos: signos, cadenas de signos y sucesiones de cadenas.

Una posible codificación para los signos, cadenas y sucesiones de cadenas es la siguiente. Para los signos se adopta: «∃» → 10 , «⇒» → 11 , «¬» → 12 , «|» → 13 , «=» → 14 , «0» → 15 ,«S» → 16 , «+» → 17 , «×» → 18 , «x» → 20 , «y» → 2000 , «z» → 200000 , ...

Dada una cadena de signos, se adopta el criterio de «apilar» los números de Gödel de sus signos, con un 77 inicial para indicar que se trata de una cadena:

«x + [5] = 0» se torna en: 77-20-17-16-16-16-16-16-15-14-15, es decir, en 7720171616161616151415

Para una sucesión de cadenas de signos, puede adoptarse un convenio similar, con un 88 inicial, para indicar que se trata de una sucesión:

La sucesión «0 = 1, y + 1 = 0» se convierte en: 88-77-15-14-16-15-77-2000-17-16-15-14-15, es decir en: 8877151416157720001716151415.

 

Puesto que la manipulación de estos signos, cadenas y sucesiones puede traducirse en manipulación de unos ciertos números, tanto la sintaxis que distingue las cadenas de signos «con sentido» —las fórmulas− como el cálculo deductivo que distingue las sucesiones de cadenas «que demuestran algo» —las demostraciones— se ven traducidas a operaciones aritméticas. Es decir, existen una serie de relaciones y funciones aritméticas que se corresponden con las reglas sintácticas y del cálculo deductivo, como por ejemplo:

Sig x : x es (el número de Gödel de) un signoCad x : x es (el número de Gödel de) una cadena (de signos)(Se omite «el número de Gödel de» en adelante)Suc x : x es una sucesión (de cadenas)Form x : la cadena x es una fórmulaAx x : la fórmula x es un axiomaCons(x, y, z): «x es una fórmula consecuencia inmediata de las fórmulas y y z»Dem(x, y): «la sucesión x es una demostración de la fórmula y»

La forma precisa de estas funciones y relaciones es laboriosa y depende del criterio que se haya escogido para efectuar la numeración de Gödel. En particular la relación Ax x ha de construirse teniendo en cuenta un cierto conjunto de axiomas concreto, luego la relación Dem hace referencia a una teoría concreta que no se ha especificado.

Ejemplo:

Es sencillo entender ahora cómo deben definirse algunas de estas relaciones según la numeración de Gödel mostrada antes: Sig x ≡ x está entre 10 y 18 (ambos inclusive), o es de la forma 20·100i (con i > 1)Cad x ≡ En base 10, x es de la forma 88n(s1)...n(sk), donde cada n(si) representa las cifras de un número tal que Sig n(si) es ciertoSuc x ≡ En base 10, x es de la forma 77n(π1)...π(sk) donde cada n(πi) representa las cifras de un número tal que Cad n(πi) es cierto.

 

Mediante la numeración de Gödel, es posible «traducir» los signos y reglas de una teoría formal T en números y operaciones aritméticas. Es posible ir más allá, ya que T es una teoría aritmética y se pueden «recodificar» las mencionadas operaciones mediante el lenguaje formal de T, al igual que se puede hacer con otras funciones y relaciones aritméticas como por ejemplo:

La función «multiplicar por 2» está representada por la fórmula: y = [2] × xLa relación de orden x ≤ y, puede expresarse mediante: ∃z, z + x = yLa relación «x e y son primos entre sí» puede expresarse como: ∀z, z ≠ [1] ∧ ∃w, x = z × w ⇒ ¬∃u, y = z × u.

Cada una de estas relaciones es expresada por su fórmula correspondiente, en el sentido de que si dos números están relacionados, puede demostrarse la expresión formal correspondiente; y cuando no lo están, puede refutarse.Por ejemplo:

Para cada entero n, se tiene que si n es par puede probarse la expresión formal ∃x, [n] = [2] × x; y si es impar, puede refutarse dicha fórmula.Para cada par de enteros m y n, si se tiene m ≤ n puede demostrarse la fórmula ∃z, z + [m] = [n]; cuando m > n, puede refutarse dicha expresión.

Que las relaciones presentadas en la sección anterior —como Dem— sean expresables, implica que una teoría formal aritmética es lo suficientemente potente como para «hablar» de las características de una teoría formal arbitraria y, en particular, de sí misma.

 

Probar que todas estas relaciones y funciones son expresables es sencillo si son recursivas, es decir, si pueden calcularse o verificarse mediante un algoritmo, ya que puede demostrarse que toda relación recursiva es expresable en una teoría aritmética. Las teorías formales para las que esto es posible —asignar los números de Gödel de manera que distinguir los signos, cadenas, sucesiones, fórmulas, consecuencias y axiomas, puede llevarse a cabo con un algoritmo— son las llamadas teorías recursivas, y por ello esta característica se asume como hipótesis en los teoremas de incompletitud.

Para construir la sentencia autorreferente G ha de idearse una manera para que una fórmula hable de las propiedades de su número de Gödel correspondiente. Esto ha de hacerse de manera indirecta, ya que dada una fórmula φ con número de Gödel n, otra fórmula que «hable» de φ mediante el numeral [n] en general tendrá un número de Gödel mayor que n, y por tanto no puede ser la propia φ. Esto se consigue mediante el llamado lema diagonal.

En una teoría aritmética recursiva, dada una fórmula φ(x) existe una sentencia ψ con número de Gödel n tal que puede demostrarse ψ ⇔ φ([n]).

 

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.

 

KURT GODEL

 

 TEOREMA DE GODEL