Wednesday, July 16, 2014

Teoremas de incompletud de Gödel (Bases, explicación y definiciones)

Gödel fue un gran matemático, murió de inanición después de que su esposa muriera quien le cocinaba y probaba su comida antes que él,  Gödel tenía un grado de paranoia excesiva por envenenamiento, él trabajó con Albert Einstein y descubrió soluciones paradójicas en ecuaciones de relatividad especial, por lo que supongo que su paranoia podría ser producto de haber estado involucrado indirectamente en la bomba atómica, no lo sé... , él tal vez es el lógico más importante en toda la historia, gracias a él tenemos fundamentos para poder demostrar la veracidad de alguna proposición en matemáticas dadas las reglas del juego, es decir el practicamente fundó la teoría metamátemica de lo que gobierna a las matemáticas como las conocemos, de los tres resultados más importantes que Gödel obtuvo por ahí de 1930 el que más ha sido objeto de curiosidad, es sólamente el teorema de incompletud, pero éste en general creo que no está bien entendido y creo que yo caía en esto también hace algunos años, yo creía que lo comprendía.

De hecho hay dos teoremas de incompletud y en general cuando la gente habla del "teorema de incompletud" casi siempre se refiere al primero de estos.

Nosotros hoy profundizaremos en esto y en las definiciones que nos llevarán a comprenderlo un poco, espero ser bastante explícito, para ser más formal omitiré el uso de algunos símbolos en matemáticas para no confundir el lenguaje formal que es importante en esto, es decir omitiré la teoría de conjuntos como usualmente la usamos y trataré de expresar todo con la menor cantidad de símbolos.

Es como el principio de incertidumbre de Heisenberg en general se piensa como que existen límites absolutos relacionados con lo que puede ser sabido/medido sobre un fenómeno.

Por otro lado, se dice que los teoremas de Gödel nos dicen que existen verdades matemáticas que jamás podrán ser probadas.

Esto nos lleva a filosofías postmodernistas a veces y a gente que entonces le da fuerza a la idea de apoyar el escepticismo sobre lo que es la verdad... "Nada puede ser completamente sabido realmente"

Y bueno, existe un libro de esos extraños llamado "Bibliografía del cristianismo y las matemáticas" (sí es en serio) donde se puede ver un ejemplo donde los religiosos usan como herramienta principal el teorema de Gödel para afirmar que si en matemáticas hay cosas que no se pueden demostrar también las hay en la religión, y les encanta el teorema de incompletud ya que "implica" la existencia de dios ya que él es el único que puede decidir todas las verdades, que por cierto, también podría interesarles una entrada anterior en mi blog donde Gödel construye un sistema axiomático "mínimo" necesario para que se pueda demostrar la existencia de dios, aquí se las dejo, la intenté demostrar con las palabras más sencillas y contiene una mini intro a lógica modal.

Empecemos un poco ya con esto, vamos a tratar de comprender, como he dicho en posts anteriores, no me considero experto en muchas cosas, incluido esto... así que si notan un error, me harán un gran favor al corregirme.


El primer teorema de incompletud de Gödel de manera burda y débil dice lo siguiente, después lo puliremos.


Teorema 1 de incompletud débil:  (Kurt Gödel)
En un sistema formal suficientemente fuerte existen proposiciones aritméticas verdaderas que no pueden ser demostradas dentro de ese sistema



Ejemplo de enunciado que no se puede demostrar en la teoría de conjuntos (hipótesis del continuo)

Está demostrado que no se puede demostrar que no existe un cardinal infinito "intermedio" entre $latex \aleph_0$ y $latex 2^{\aleph_0}$

Es decir no se puede demostrar que no existe un conjunto estrictamente más grande que $latex \mathbb{N}$ (los números naturales, enteros positivos) y estrictamente más chico que $latex \mathbb{R}$ (Todos los números reales, es decir enteros, cocientes de enteros e irracionales como $latex \pi,e,\phi$ et cétera...)

Esto anterior se puede agregar a los axiomas de los números reales junto con el sistema axiomático ZFC y sería consistente sí y sólo si ZFC es consistente, pero al final veremos la complicación, y veremos qué es eso de consistente y los sistemas axiomáticos.

Si te interesa profundizar más en esto puedes ver un post anterior aquí sobre los infinitos, cardinalidad, axioma de elección y axiomas de ZF (Zermelo-Fraenkel).


Vamos a tratar de comprender el  teorema de Gödel versión débil a través de definiciones y ejemplos, comencemos...

Lenguajes formales.

Necesitamos entender lo que es un sistema formal , pero primero necesitamos saber lo que es un lenguaje formal $latex \mathbb{L}$. Para esto necesitamos definir una lista de símbolos, y definir qué secuencias de símbolos son expresiones válidas en el lenguaje

Ahora, cuando se habla de aritmética , significa lo que podemos hacer con los números, es decir no sólo lo que te enseñan en el kinder sobre los números, sino más bien en términos de teoría de números, en el lenguaje formal de la aritmética tenemos un símbolo para el $latex 1$, también para sumar $latex +$, multiplicar $latex \times$ o letras incluso $latex x,y$ que actúan como variables, símbolos de igualdad $latex =$ y relaciones de orden como "menor que" < o "mayor que" >.


También menos frecuente tenemos partículas lógicas como "Y" $latex (\wedge)$ , "O"  $latex (\vee)$, "implica" $latex (\Rightarrow)$, "NO" $latex (\neg)$ y "sí y sólo si" $latex (\Leftrightarrow)$.


También vamos a tener cuantificadores que son "para todo $latex n$" $latex (\forall n)$ así como "existe una $latex n$" $latex (\exists n)$. 

También habrán paréntesis para evitar ambiguedad en las expresiones,  por ejemplo, ya definido nuestro lenguaje, usémoslo para decir algo.


$latex 1< m\wedge \neg(\exists n)(\exists k)(1<n<m \wedge n\times k=m)$

En español:

"$latex m$ es un número mayor que $latex 1$ y no hay $latex n$ ni $latex k$ con $latex n$ menor que $latex m$ cumpliendo que $latex m=n\times k$"


Eso que acabamos de definir es un número primo $latex (m)$ (un número entero positivo que no tiene factores mayores que $latex 1$), por ejemplo el $latex 7,19$ o $latex 101$.


Ahora, esos símbolos que nos denotan lo que es un número primo en el lenguaje de la aritmética podemos llamarlo fórmula , nos va a servir como un test lógico y vamos a ponerla en función de $latex m$ y le llamamos $latex P(m)$ (P por primo) la cual si $latex m$ es primo se cumple la definición y es verdadera y falsaen caso contrario.



Como sabrán... los números primos son muy importantes en la aritmética, hace 2300 años Euclides en su libro Elementos probó que que los números primos son infinitos, y esto en nuestro lenguaje formal se puede decir así:


$latex \forall n \exists m (n< m \wedge P(m))$

Y en español es:

"Para todo número $latex n$ existe un $latex m$ tal que $latex m$ es más grande que $latex n$ y $latex P(m)$ es verdadero (Es decir m cumple la fórmula de definición de número primo)"

Más chafa sería que para todo número $latex n$ que se te ocurra, el que sea... siempre podrás encontrar un número más grande que éste que sea primo.


¿Ven el poder de los lenguajes formales? , podemos decir mucho con pocos símbolos.


Otro ejemplo para que quede claro es el concepto de primo gemelo los cuales son los números naturales $latex n$ tal que $latex n+2$ también es primo, nadie sabe si existen una infinidad de estos ya que no hay una manera de construirlos, ejemplos de estos es el $latex 3$ (ya que el $latex 5$ también es primo), incluso el $latex 5$ (porque el $latex 7$ también es primo), pero el $latex 7$ no funciona ya que $latex 7+2=9=3^2$  pero el $latex 11$ sí lo es porque el $latex 13$ es primo.


Si sí existen una infinidad de números primos gemelos, diríamos en nuestro lenguaje:

$latex \forall n\exists m (n< m \wedge P(m) \wedge P(m+2))$

Es decir... para todo $latex n$ que se nos ocurra podemos encontrar un número $latex m$ mayor que $latex n$ que es un primo gemelo.

Esa expresión en el lenguaje de la aritmética NADIE sabe si es verdadera... así como la conjetura fuerte de Goldbach (La débil ya fue resuelta por Helfgott hace unos meses) que dice que

Conjetura (Goldbach):
Todo número par mayor que 4 es la suma de 2 números primos impares

Si demostramos algún día la conjetura de Goldbach podremos decir que en $latex \mathbb{L}$ existe el siguiente objeto (proposición):


$latex \forall n>4\wedge n=2k (\exists a>2\wedge P(a))(\exists b>2\wedge P(b))(n=a+b)$

Mucho de esto se ataca con el lenguaje de los números complejos que usas en cálculo y análisis como por ejemplo la conjetura de Riemann.


Sistema formal

Ya tienes tu lenguaje formal $latex \mathbb{L}$ ahora vamos a especificar un sistema formal $latex \mathbb S$  en $latex \mathbb{L}$ definiendo que proposiciones $latex \mathcal{A}$ de $latex \mathbb{L}$ son axiomas y qué relaciones entre las proposiciones son reglas de inferencia..


Vamos a dar algunas definiciones súper importantes para poder comprender el trabajod e Gödel al menos de manera superficial.

El axioma lo entendemos como una proposición verdadera por sí misma, y de ésta inferir otras proposiciones, es decir son como los bloques de nuestro sistema, no se pueden demostrar y de éstas lograremos construir otras proposiciones, algunos dicen que son fórmulas del lenguaje $latex \mathbb{L}$ que son evidentes pero yo no coincido NADA con eso, la palabra evidente aquí es muy ambigua... busca los axiomas de la geometría y demuestra que no se puede deducir uno de otro... no es tan evidente.

Es decir , una proposición que se puede deducir de axiomas NO es un axioma, el axioma es lo más elemental y que todo lo del sistema debe de cumplir.


Una inferencia es lo que hacemos diario para poder relacionar dos situaciones y saber si son equivalentes o no, y en nuestro caso si tenemos dos proposiciones $latex \mathcal{A},\mathcal{B}$ del lenguaje $latex \mathbb{L}$ las reglas de inferencia nos permitirán trazar una linea lógica entre $latex \mathcal{A}$ y $latex \mathcal{B}$ para saber si son equivalentes o alguna implica la otra, es decir si $latex \mathcal{A}\Rightarrow \mathcal{B}$ o $latex \mathcal{B}\Rightarrow \mathcal{A}$ o $latex \mathcal{A} \Leftrightarrow \mathcal{B}$ como ejemplo:

(Lo decapitarán $latex \Rightarrow$ Morirá)

pero... también tenemos que:

$latex \neg$(Morirá $latex \Rightarrow$ Lo decapitarán)

Es decir , si te decapitan es verdadero que vas a morir, pero NO siempre sucede que si vas a morir (todos vamos a morir) es porque te van a decapitar, el cómo estamos pensando esto desde el sentido de la naturaleza humana es lo que es una regla de inferencia.

Es decir tenemos como axioma en la vida que los seres humanos son finitos cronológicamente, entonces podemos en base a eso definir una proposición, una equivalencia.

naces $latex \Leftrightarrow$ mueres

Es decir, si naces mueres, y si mueres es porque naciste

Entonces un sistema formal debemos definir los axiomas en el lenguaje $latex \mathbb{L}$ y nuestras reglas de inferencia para poder encontrar relaciones entre las fórmulas/proposiciones de $latex \mathbb{L}$ , se pide también que se pueda computar si una proposición es un axioma o una combinación de implicaciones lógicas deducidas de las reglas de inferencias que vienen de los axiomas.


Ahora, una demostración  en $latex \mathbb{S}$ es una sucesión finita de proposiciones, que cada una de éstas es un axioma o algo obtenido de proposiciones anteriores en la lista de la sucesión aplicando alguna de las reglas de inferencia.


Decimos que una proposición $latex \mathcal A$ es demostrable en $latex \mathbb{S}$ si existe una demostración en $latex \mathbb{S}$ que termina en $latex \mathcal{A}$.

Ahora, también decimos que $latex \mathbb{S}$ es consistente si no hay proposiciones $latex \mathcal{A}$ en $latex \mathbb{L}$ tal que ambas $latex \mathcal{A}$ y $latex \neg \mathcal{A}$ son demostrables en $latex \mathbb{S}$.

Decimos que $latex \mathbb{S}$ es formalmente completo para $latex \mathbb{L}$ si toda proposición $latex \mathcal{A}$ de $latex \mathbb{L}$ se puede demostrar siempre $latex \mathcal{A}$ o $latex \neg \mathcal{A}$ (sólo alguna se puede demostrar, aquí son los problemas con el español, en inglés si está pensado bien esto con la palabra "or" o "nor").

Gödel como diría esto en sus papers es que:

$latex \mathbb{S}$ es formalmente completo si toda proposición de $latex \mathbb{L}$ es decidible en $latex \mathbb{S}$.

Si $latex \mathbb{S}$ no es completo entonces decimos que existen $latex \mathbb{L}$-proposiciones indecidibles en $latex \mathbb{S}$.


Ahora, decimos que el sistema $latex \mathbb{S}$ es verdadero completo para $latex \mathbb{L}$ si toda proposición verdadera de $latex \mathbb{L}$ es demostrable en $latex \mathbb{S}$ .
Es decir si $latex \mathbb{S}$ es consistente (es decir que puedes demostrar la proposición $latex \mathbb{A}$ o su negación (sólo una) y también es verdadero completo para $latex \mathbb{L}$ entonces es formalmente completo ya que toda proposición $latex \mathcal{A}$ de $latex \mathbb{L}$ es o verdadera o falsa, es decir su negación es verdadera.

Pero $latex \mathbb{S}$ podría ser consistente y formalmente completo pero no necesariamente verdadero completo ya que podrías probar proposiciones falsas, esto es unac onsecuencia del teorema de Gödel. Es más fuerte probar que $latex \mathbb{S}$ no es formalmente completo que el hecho de ser verdadero completo, esto es lo que Gödel hizo inicialmente.

Ya con esto podemos entender lo que dice el primer teorema de Gödel excepto por un detalle.

Recordemos lo que dice el primer teorema de Gödel sin pulir y débil, ya pronto enunciaremos el teorema como él mismo lo pensó.

Teorema débil:  (Kurt Gödel), Recapitulando



En un sistema formal suficientemente fuerte existen proposiciones aritméticas verdaderas que no pueden ser demostradas dentro de ese sistema


No sabemos exactamente significa "suficientemente fuerte" 

Usualmente el decir que un sistema formal es suficientemente fuerte es que incluye el sistema PA, es decir la aritmética de Peano, los cuales son reglas sobre la adición, multiplicación, igualdad y relación de orden (menor que), pero más allá de eso, los axiomas de peano conllevan a algo más fuerte que es lo que se pide en "suficientemente fuerte" que es el principio de inducción matemática en $latex \mathbb{S}$ que expresado en $latex \mathbb{L}$ dice lo siguiente para un proposición $latex \mathcal{P}$:


$latex \mathcal{P}(1)\wedge (\forall n)(\mathcal{P}(n) \Rightarrow \mathcal{P}(n+1)) \Rightarrow (\forall n)\mathcal{P}(n)$


Esto en teoría de números es muy importante ya que nos permite definir un razonamiento para demostrar una infinidad de proposiciones, es decir que dependan de un parámetro $latex n$ que es una variable que toma una infinidad de valores enteros.

Esto en español esa proposición de $latex \mathbb{L}$ dice:

Si $latex 1$ cumple la propiedad $latex \mathcal{P}$ Y si todos los $latex n$ tienen la propiedad $latex \mathcal{P}$ (es decir $latex \mathbb{P}$ es verdadero) implican que $latex n+1$ también tenga la propiedad $latex \mathcal{P}$ entonces podemos concluir que todos los números tienen la propiedad $latex \mathcal{P}$

Es decir, los matemáticos no se van a poner a demostrar caso por caso porque da flojera y porque es imposible demostrar una infinidad de casos, y la propiedad inductiva en los números naturales nos dice que podemos usar una especie de efecto dominó en las propiedades de los números naturales que nos permiten poder generalizar la veracidad de un resultado... eso de manera informal es el principio de inducción y es lo que Gödel pide en que $latex \mathbb{S}$ sea suficientemente fuerte , es decir que contenga la aritmética de Peano la cual trae consigo el principio de inducción.

Los axiomas de Peano son explícitamente estas 5 reglas que con éstas son suficientes para construir toda la aritmética (de hecho la más importante es la función sucesor de un número natural que construye la suma y de ahí todo lo demás:

Axiomas de Peano (de wikipedia)

a) El 1 es un número natural.1 está en $latex \mathbb{N}$, el conjunto de los números naturales.
b) Todo número natural n tiene un sucesor n* (este axioma es usado para definir posteriormente la suma).
c) El 1 no es el sucesor de algún número natural.
d) Si hay dos números naturales n y m con el mismo sucesor, entonces n y m son el mismo número natural.
e) Si el 1 pertenece a un conjunto K de n naturales, y dado un elemento cualquiera k, el sucesor k* también pertenece al conjunto K, entonces todos los números naturales pertenecen a ese conjunto K. Este último axioma es el principio de inducción matemática.


Aquí está ya el teorema después de todo el background que hemos visto:

Primer teorema de incompetud de Gödel:
Si $latex \mathbb{S}$ es un sistema formal tal que:

i) El lenguaje $latex \mathbb{L}$ de $latex \mathbb{S}$ contiene el lenguaje de la aritmética 
ii) $latex \mathbb{S}$ incluye los axiomas de Peano
iii) $latex \mathbb{S}$ es consistente

Entonces existe una proposición $latex \mathcal{A}$ en $latex \mathbb{L}$ que es verdadera pero no puede ser demostrada en $latex \mathbb{S}$


La demostración es complicada pero a grosso modo a cada símbolo del lenguaje $latex \mathbb{L}$ de $latex \mathbb{S}$ le asoció un número primo y a cada expresión $latex \mathcal{E}$ de $latex \mathbb{L}$ usando los números asociados a sus símbolos le asoció el producto de los símbolos de $latex \mathcal{E}$ a estos les llamamos número de Gödel para la expresión $latex \mathcal{E}$.

Ahora, como son sucesiones finitas por definición están bien definidos los números de Gödel, y cada expresión de $latex \mathbb{L}$ tiene un número de Gödel .

Las demostraciones en $latex \mathbb{S}$ serán sucesiones finitas de proposiciones, por lo que a éstas demostraciones también se les puede asociar un número de Gödel, entonces el demostró la siguiente propiedad:


n es el número de una demostración $latex \mathcal{A}$ en $latex \mathbb{S}$

y bueno esto se escribe como:

$latex \Delta_{\mathbb{S}}(n,\mathcal{A})$

Y es expresado en el lenguaje de la aritmética, por lo que la proposición

$latex (\exists n) \Delta_{\mathbb{S}}(n,\mathcal{A})$

la cual escribimos como

$latex \Lambda_{\mathbb{S}}(\mathcal{A})$

Nos dice que $latex \mathcal{A}$ es demostrable de $latex \mathbb{S}$ o sea que si es verdadera es demostrable en la aritmética de Peano, y si $latex \mathcal{A}$ no es demostrable en $latex \mathbb{S}$ escribimos $latex \neg \Lambda_{\mathbb{S}}(\mathcal{A})$


Finalmente , Gödel usó una adaptación de lo que se le llama el método de la diagonal para construir una proposición específica (una cadena de números), llámale $latex \mathcal{D}$ tal que los axiomas de Peano demuestran

$latex \mathcal{D} \Leftrightarrow \neg \Lambda_{\mathbb{S}}(\mathcal{D})$

Y culmina demostrando que:

* Si $latex \mathbb{S}$ es consistente entonces $latex \mathcal{D}$ es no demostrable con $latex \mathbb{S}$

Y eso termina la demostración del teorema.


Para terminar este post les dejo el segundo teorema de incompletud

Segundo teorema de incompetud de Gödel:
Si $latex \mathbb{S}$ es un sistema formal tal que:

i) El lenguaje $latex \mathbb{L}$ de $latex \mathbb{S}$ contiene el lenguaje de la aritmética 
ii) $latex \mathbb{S}$ incluye los axiomas de Peano
iii) $latex \mathbb{S}$ es consistente

Entonces la consistencia de $latex \mathbb{S}$ y $latex \Lambda_{\mathbb{S}}(\mathcal{A}\wedge \neg \mathcal{A})$ es NO demostrable en $latex \mathbb{S}$



No profundizaré ahora en esta parte, tal vez en otro post que requiere más maquinaria.

Espero les haya servido de algo, este teorema es de los grandes descubrientos en los artefactos que gobiernan a las matemáticas






Kurt Friedrich Gödel,  Abril 28, 1906 - Enero 14, 1978


Eduardo Ruiz Duarte (beck)
twitter: @toorandom



1 comment:

Manuel G. said...

Interesante, vi parte de ello en mis clases de logica en la universidad, y sobre los lenguajes formales, lo use para programar un compilador .

long long time ago