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 1930. 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 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.^[1]

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 en cuestión es consistente, no es posible probarlo dentro del propio sistema.

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.^[1]

Contenido 1 Enunciado de los teoremas 1.1 Contexto 1.2 Primer teorema 1.3 Segundo teorema 2 Ejemplos de afirmaciones indecidibles 3 Malos entendidos en torno a los teoremas de Gödel 4 Discusión e implicaciones 5 Demostración de los teoremas 5.1 Numeración de Gödel 5.2 Representabilidad. Recursividad 5.3 Diagonalización 5.4 Demostración del primer teorema 5.5 Demostración del segundo teorema 6 Véase también 7 Referencias 8 Bibliografía 9 Enlaces externos

Enunciado de los teoremas

Contexto

Los teoremas de incompletitud se formulan en el contexto de una teoría formal de primer orden.^[2] 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 fórmulas 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.

Las teorías formales T tienen una serie de rasgos en función de lo que son capaces de demostrar:

T es consistente si es imposible demostrar una fórmula φ y también su negación ¬φ. T es completa si dada cualquier fórmula φ, existe una demostración de φ o de ¬φ.

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.^[3]

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

1. las fórmulas bien formadas de las que no lo son,
2. si una fórmula es consecuencia de otras o no,
3. 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.

Primer teorema

El enunciado del primer teorema reza:

Primer teorema de incompletitud de Gödel Toda teoría aritmética recursiva que sea consistente es incompleta

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 son teoremas de 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.^[1]

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. Esto demuestra la existencia de modelos no estándar de la aritmética: los objetos que describe T' no son los números naturales (ya que paraellos ¬G es falsa), pero cumplen todos los teoremas aritméticos (que son también teoremas de T').^[4] En otras palabras, el primer teorema de incompletitud asegura que estas teorías de primer orden no pueden caracterizar totalmente los objetos que describen.^[5]

Tomando G (o su contraria) como axioma se obtiene 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;^[6] 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.^[7]

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:

Segundo teorema de incompletitud de Gödel En toda teoría aritmética recursiva que sea consistente, Consis T no es un teorema.

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

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:

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 incompletitud 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 John R. Lucas se ha ocupado de está cuestión en Mentes, Máquinas y Gödel.^[8]

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.

Demostración de los teoremas

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 aritméticas, cuyas fórmulas 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). Sin embargo existe una demostración de la versión "fuerte", que sólo exige la consistencia de la teoría, debida a J. B. Rosser.

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.

La 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 y sucesiones). Además, de este modo se pueden codificar las fórmulas y demostraciones, mediante ciertas relaciones y funciones puramente aritméticas (que "hablan de números") equivalentes a los conceptos de la teoría formal: sólo es necesario traducir la sintáxis y las reglas de demostración a operaciones aritméticas. Esta traducción o codificación tiene asociada entonces una serie de relaciones aritméticas tales como:

Sig x : «x es (el número de Gödel de) de un signo»

Cad x : «x es (el número de Gödel de) 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órmula»

Ax x : «la fórmula x es un axioma»

Cons(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 complicada y depende del criterio escogido para efectuar esta numeración. (Nótese en particular que la relación Ax x ha de construirse teniendo en cuenta un cierto conjunto de axiomas concreto, luego Dem hace refencia a una teoría concreta que no se ha especificado).

Ejemplo

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 Es sencillo entender ahora cómo deben definirse algunas de las relaciones mencionadas antes: Sig x ≡ x está entre 10 y 18 (ambos inclusive), o es de la forma 20·100i 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 cierto Suc 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

Representabilidad. Recursividad

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

La función «multiplicar por 2» está representada por: y = [2] × x

La relación de orden x ≤ y, puede expresarse como: ∃z, z + x = y

La relación «x e y son primos entre sí» puede expresarse como: ∀z, ¬x = z × y ∧ ¬y = z × x

Cada una de estas relaciones es expresada por su fórmula correspondiente, en el sentido de que dos números están relacionados si y sólo si puede demostrarse el correspondiente teorema formal.^[9] Por ejemplo:

m ≤ n si y sólo si puede demostrarse el teorema formal ∃z, z + [m] = [n]

Que las relaciones presentadas en la sección anterior —como Dem— sean representables, 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.

Diagonalización

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

En definitiva, dada una propiedad cualquiera φ(x) existe una sentencia ψ que afirma «mi número de Gödel cumple la propiedad φ».

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.

Véase también

• Consistencia lógica
• Autorreferencia
• Logicismo
• Teorema de Löb
• Teorema de completitud de Gödel

Referencias

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. .
• Domeisen, Norbert (1990). Peter Lang. ed (en alemán). Zentralblatt MATH Logik der Antinomien. ISBN 3-261-04214-1. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?first=1&maxdocs=3&type=html&an=0724.03003&format=complete Zentralblatt MATH. 
• Gödel, Kurt (1931). «Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I» (en alemán). Monatshefte für Mathematik und Physik 38:  pp. 173-198. doi:10.1007/BF01700692. 

Traducido al castellano en:

•     (1981). Jesús Mosterín. ed. Obras completas. Alianza Editorial. ISBN 84-206-2286-9. 
•     (2006). Sobre proposiciones formalmente indecidibles de los Principia Mathematica y sistemas afines. KRK Ediciones. ISBN 978-84-96476-95-0. 
• 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, http://www.uv.es/ivorra/Libros/Logica.pdf, consultado el 27-07-2011 .
• Martínez, Guillermo (2009). Gödel para todos. Seix Barral. ISBN 978-950-731-605-0. 
• Rosser, B. (1936). «Extensions of some theorems of Gödel and Church». Journal of Symbolic Logic 1 (3):  pp. 87-91. http://www.jstor.org/stable/2269028. 
• Smullyan, Raymond (1992) (en inglés). Gödel's Incompleteness Theorems. Oxford University Press. ISBN 0-19-504672-2. 

Enlaces externos

• 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
• 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.
• Kārlis Podnieks: Around Goedel's Theorem, http://www.ltn.lv/~podnieks/gt.html
• Hilbert's second problem