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 esto, es que supongo que su paranoia podría ser producto de haber estado involucrado indirectamente en la bomba atómica, no lo sé. En mi opinión Gödel, es el lógico más importante en toda la historia, descubrió (¿inventó?) un resultado muy fuera de lo estándar, que en mi opinión es muy profundo y en mi perspectiva toca los límites entre la matemática y la filosofía analítica. Esto le hizo ganarse su doctorado con una tésis de doce páginas "Über die Vollständigkeit der Axiome des logischen
Funktionenkalkül" por la universidad de Viena (click
aquí).
En general, gracias a él tenemos fundamentos para poder demostrar la veracidad de alguna proposición en matemáticas dadas las reglas del juego (axiomas). Es decir él practicamente fundó la teoría metamátematica 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. el más profundo. En mi opinión, este resultado no está bien entendido por las personas que "creen entenderlo", yo caía en este subconjunto hace algunos años, hasta que decidí estudiarlo formalmente
De hecho hay dos teoremas de incompletud y en general cuando la gente habla de el "
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.
El teorema de incompletud de Gödel, es como el
principio de incertidumbre de Heisenberg, en general se piensa que "existen límites absolutos relacionados con lo que puede ser sabido y medido sobre un fenómeno". Análogamente 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 ideas que apoyan el escepticismo sobre lo que es la verdad...
"Nada puede ser completamente sabido realmente"
Un ejemplo absurdo de esto anterior es que existe un libro extraño llamado
"Bibliografía el 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 e infieren que también las hay en la religión. 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.
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 introducción a lógica modal.
Empecemos un poco ya con estos teoremas de Gödel. 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 infinito 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...).
Si no te queda claro esta idea no-intuitiva de que hay infinitos más grandes que otros, imagina que no existe una función que pueda relacionar biyectivamente a los números naturales con los números reales los cuales son muchos más.
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 para ello, 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 $latex \mathbb{L}$ .
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 $latex \mathbb{L}$ tenemos un símbolo para el $latex 1$, también para sumar $latex +$, multiplicar $latex \times$. Más aún, tenemos letras $latex x,y$ que actúan como variables, así como símbolos de igualdad $latex =$ y
relaciones de orden como
"menor que" < o
"mayor que" >.
Menos frecuente, también 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 hay
cuantificadores como:
"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,101$ o $latex 31337$
.
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. Estas fórmulas nos van a servir como un
test lógico, que en este caso es una fórmula en función de $latex m$, llamémosla $latex P(m)$. Esta fórmula nos da como resultados "verdadero" o "falso" dependiendo si $latex m$ es primo o no.
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. Esto en nuestro lenguaje formal se puede decir así:
$latex \forall n \exists m (n< m \wedge P(m))$
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 son 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, la formula:
$latex \forall n\exists m (n< m \wedge P(m) \wedge P(m+2))$
Es verdadera.
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)
.
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:
$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 definir un
sistema formal $latex \mathbb S$ en $latex \mathbb{L}$. Esto es definiendo qué proposiciones $latex \mathcal{A}$ de $latex \mathbb{L}$ son
axiomas, y qué relaciones entre las proposiciones son
reglas de inferencia..
Aquí dije en negritas dos conceptos, "axiomas" y "reglas de inferencia", procedo s definirlos.
Un
axioma lo entendemos como una proposición
verdadera por sí misma en $latex \mathbb{L}$, 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. Por ejemplo, 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. Por ejemplo en $latex \mathbb{L}$, un axioma es $latex x < y\wedge y< z \Rightarrow x < z$.
Una
inferencia es lo que hacemos diario para poder relacionar dos situaciones y saber si son equivalentes o no. 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}$, y así 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.
Más aún. tenemos como axioma en la vida que los seres humanos son finitos cronológicamente. Entonces, podemos con base en eso definir una proposición, una equivalencia.
naces $latex \Leftrightarrow$ mueres
Es decir, si naces mueres, y si mueres es porque naciste,
Entonces, en 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 una proposición obtenida de axiomas anteriores conectadas lógicamente por reglas de inferencia. Te puedes imaginar una "gráfica" (o grafo), donde cada vértice es una proposición o teorema de cierto sistema axiomático. Las aristas (dirigidas) entre dos vértices existirán si existe una relación lógica (implicación) entre ellas obtenida con las reglas de inferencia (el razonamiento básico estipulado en tu sistema formal).
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 una de ellas!).
Gödel diría esto equivalentemente en su tesis como:
$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 \matcal{A}$ o su negación (sólo una)) y también es
verdadero completo para $latex \mathbb{L}$, entonces es
formalmente completo. Esto es
ya que toda proposición $latex \mathcal{A}$ de $latex \mathbb{L}$ es o verdadera o falsa (si es falsa, tenemos que su negación es verdadera, por lo que existirá ésta en $latex \mathbb{L}$).
Pero $latex \mathbb{S}$ podría ser consistente y
formalmente completo pero no necesariamente
verdadero completo.
Con estos conceptos, ya 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 qué significa
"suficientemente fuerte"
El decir que un sistema formal es suficientemente fuerte, significa que incluye el sistema PA, es decir la
aritmética de Peano. Éste PA, 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", esto es el
principio de inducción matemática en $latex \mathbb{S}$. Expresado en $latex \mathbb{L}$, dice lo siguiente para un proposición $latex \mathcal{P}$ en $latex \mathbb{L}$:
$latex \mathcal{P}(1)\wedge (\forall n)(\mathcal{P}(n) \Rightarrow \mathcal{P}(n+1)) \Rightarrow (\forall n)\mathcal{P}(n)$
Esta fórmula de $latex \mathbb{L}$ en español 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 \mathcal{P}(n)$ es verdadero) e implican que $latex n+1$ también tiene la propiedad $latex \mathcal{P}$, entonces podemos concluir que todos los números tienen la propiedad $latex \mathcal{P}$.
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.
Es decir, los matemáticos no nos vamos a poner a demostrar caso por caso porque da flojera y porque es imposible demostrar una infinidad de casos. 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, permitiéndonos 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 exista en $latex \mathbb{S}$ para ser considerado éste
suficientemente fuerte. En otras palabras, que el sistema formal 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 en la aritmética:
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 natural. Adicionalmente a cada expresión $latex \mathcal{E}$ de $latex \mathbb{L}$ usando los números asociados a sus símbolos le asoció el número natural obtenido de la concatenación de los símbolos que componen $latex \mathcal{E}$, cada uno separado por cero. Él usa el 0 porque no usa ése dígito al asociar naturales a su lenguaje formal $latex \mathbb{L}$.
A estos números les llamamos
números de Gödel para la expresión $latex \mathcal{E}$.
Ahora, como las fórmulas en $latex \mathbb{L}$ son sucesiones finitas por definición, los números de Gödel están bien definidos, 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 conectadas por una implicación, por lo que a éstas demostraciones también se les puede asociar un número de Gödel, (concatenación de los números de Gödel de cada proposición con un 0 separándolas), entonces él definió la siguiente propiedad:
n es el número de Gödel de una demostración $latex \mathcal{A}$ en $latex \mathbb{S}$
como:
$latex \Delta_{\mathbb{S}}(n,\mathcal{A})$
La cual es expresada en el lenguaje de la aritmética $latex \mathbb{L}$ como la proposición
$latex (\exists n) \Delta_{\mathbb{S}}(n,\mathcal{A})$
la cual escribimos como fórmula:
$latex \Lambda_{\mathbb{S}}(\mathcal{A})$
Ésta 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})$ (la cual será verdadera).
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})$
Es decir que hay un número de Gödel sin demostración asociada.
Ésta $latex \mathcal{D}$ es construida con base en una proposición que es autoreferenciada. Con más tiempo en el futuro lo compartiré aquí con detalle.
Gödel 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
