Teorema de Gödel: Incompletitud de Sistemas Formales

Teorema de incompletitud de Gödel explicado: por qué las matemáticas formales tienen límites

En 1931, Kurt Gödel demostró límites fundamentales en cualquier sistema formal de aritmética lo suficientemente potente. Sus teoremas de incompletitud mostraron que es imposible construir un sistema consistente capaz de demostrar todas las afirmaciones verdaderas sobre los números naturales. Este descubrimiento acabó con el sueño de una formalización completa de las matemáticas.

La tendencia unificadora en ciencia y matemáticas

A principios del siglo XX, la ciencia mostraba una fuerte tendencia a la unificación. Newton unificó la gravedad terrestre con la mecánica celeste. Maxwell redujo electricidad, magnetismo y luz a un único campo electromagnético. Darwin explicó la diversidad de la vida mediante la selección natural.

Los matemáticos buscaron una síntesis similar: deducir aritmética, geometría y análisis a partir de un único conjunto de axiomas. Frege propuso definir los números mediante teoría de conjuntos:

• 0 = ∅ (el conjunto vacío)
• 1 = {∅}
• 2 = {∅, {∅}}

El sucesor de un número n se definía como la unión de todos los números anteriores, lo que permitía formalizar por completo la aritmética. Pero la paradoja de Russell derrumbó el sistema: sus axiomas implicaban una contradicción — la famosa «colección de todos los conjuntos que no se contienen a sí mismos».

La crisis fundacional y el programa de Hilbert

La paradoja de Russell desencadenó una crisis fundacional en las matemáticas. David Hilbert respondió con un ambicioso programa de formalización que exigía tres propiedades para cualquier sistema axiomático:

• Completitud (K): El sistema demuestra toda afirmación verdadera sobre aritmética.
• Consistencia (K): El sistema nunca demuestra afirmaciones falsas.
• Decidibilidad: Existe un algoritmo que determina si una afirmación dada es demostrable o no.

Hilbert insistió en que estas propiedades debían probarse metamatemáticamente — usando razonamiento finito y concreto sobre el propio sistema.

Principia Mathematica de Russell y Whitehead

Bertrand Russell y Alfred North Whitehead escribieron Principia Mathematica (PM), un sistema lógico axiomático lo suficientemente potente para reconstruir toda la matemática. Construyeron la aritmética desde cero, llegando incluso a dedicar más de 300 páginas para demostrar que 1 + 1 = 2.

Para analizar PM, Gödel simplificó su sintaxis en un lenguaje tipo PM-Lisp:

| Símbolo | Significado | Ejemplo |

|---------|-------------|---------|

| 0 | cero | 0 |

| next | sucesor | (next 0) |

| + | suma | (+ 0 (next 0)) |

| | multiplicación | ( 0 (next 0)) |

| = | igualdad | (= 0 (* 0 (next 0))) |

Operadores lógicos:

| Símbolo | Significado | Ejemplo |

|---------|-------------|---------|

| not | negación | (not (= 0 1)) |

| or | disyunción | (or (= 0 1) (not (= 0 1))) |

| when | implicación | (when 0 (or 0 1)) |

| there-is | cuantificador existencial | (there-is x (= 4 (* x 2))) |

Los axiomas de PM incluían tautologías como:

• (when (or p p) p)
• (when p (or p q))
• Conmutatividad y asociatividad de la disyunción
• La regla del silogismo

A partir de ellos, se derivaron paso a paso la igualdad y la aritmética.

Numeración de Gödel: codificar la sintaxis como números

Gödel aplicó una codificación al estilo de Cantor para asignar a cada fórmula un número natural único. Cada símbolo recibió un número de Gödel distinto basado en primos:

| Símbolo | Número de Gödel |

|---------|-----------------|

| ( | 1 |

| ) | 3 |

| 0 | 5 |

| next | 7 |

| + | 9 |

| * | 11 |

| = | 13 |

| not | 15 |

| or | 17 |

| when | 19 |

| there-is | 21 |

| a, b, c, … | 2, 4, 6, … |

La fórmula (there-is a (= (next 0) a)) se convierte en una secuencia de tokens; su número de Gödel se calcula como G = 2^g₁ × 3^g₂ × 5^g₃ × …, donde cada gᵢ es el número de Gödel del i-ésimo token. Esto establece una correspondencia biunívoca perfecta entre fórmulas y números naturales.

Lo crucial es que la aritmética de PM-Lisp es expresable dentro de sí misma: longitud de fórmulas, sustitución y demostrabilidad se reducen a funciones recursivas primitivas — lo que hace posible la autorreferencia.

Autorreferencia y el teorema de incompletitud

Gödel construyó una fórmula G que afirma su propia indemostrabilidad: ∃p Proof(p, ⌜G⌝) — «No existe una demostración con número p de mí».

Mediante el lema diagonal (un teorema del punto fijo):

G ≡ ¬Provable(⌜G⌝)

Teorema 1: Si PM es consistente, entonces G es verdadera pero indemostrable dentro de PM.

Teorema 2: Si PM es consistente, entonces Con(PM) (la afirmación que afirma la consistencia de PM) es indemostrable dentro de PM.

Conclusiones clave:

• Todo sistema que interprete la aritmética de Peano es incompleto.
• La consistencia de un sistema no puede demostrarse dentro del propio sistema.
• Los números naturales codifican sintaxis — lo que permite la autorreferencia.
• El programa de Hilbert es fundamentalmente inalcanzable.
• Verdad y demostrabilidad no son equivalentes.

Consecuencias para la informática

El teorema de Gödel es lógicamente equivalente al problema de la parada de Turing. Los sistemas formales tienen «puntos ciegos» inherentes. En programación, esto se manifiesta como:

• Funciones no computables (por ejemplo, una hipotética «oráculo de parada»).
• Bombas lógicas integradas en herramientas de verificación.
• Límites estrictos en la verificación formal de software.

Los asistentes actuales de prueba (Coq, Lean) reconocen explícitamente la incompletitud — confían en axiomas confiables en lugar de reclamar certeza absoluta.

— Editorial Team