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.
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.
Los teoremas de incompletitud de Gödel son uno de los grandes avances de la lógica matemática.
Primer teorema
Cualquier teoría aritmética recursiva que sea consistente es incompleta.
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.
Consecuencias
La sentencia de Gödel G no es demostrable pero es cierta, pues afirma precisamente su propia indemostrabilidad.2
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.
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.
Segundo teorema
El segundo teorema de incompletitud muestra otro ejemplo explícito de una fórmula que ninguna teoría aritmética puede demostrar.
En toda teoría aritmética recursiva consistente T, la fórmula Consistente T no es un teorema.
La demostración del segundo teorema requiere traducir el primero a una fórmula.. 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,.
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.
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, como por ejemplo:
∃ , ⇒ , ¬ , |, =, x , y , z , ... , 0 , + , × , S
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 ,
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.
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 77n(s1)...n(sk), donde cada n(si) representa las cifras de un número tal que Sig n(si) es cierto
Expresabilidad y recursividad
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, 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] × x
La relación de orden x ≤ y, puede expresarse mediante: ∃z, z + x = y
La relación «x e y son primos entre sí» puede expresarse como: ∀z, z ≠ [1] ∧ ∃w, x = z × w ⇒ ¬∃u, y = z × u.
Demostración
Demostración
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.
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).
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]).