Teoremas de incompletitud de Gödel

Kurt Gödel a los 19 años de edad, cinco años antes de la demostración de los teoremas.

Los 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, es a la vez consistente y completa. Es decir, si los axiomas de dicha teoría no se contradicen entre sí, entonces existen enunciados que no pueden probarse ni refutarse a partir de ellos. En particular, la conclusión del teorema se aplica siempre que la teoría aritmética en cuestión sea recursiva, esto es, una teoría en la que el proceso de deducción pueda llevarse a cabo mediante un algoritmo.

La prueba del teorema es totalmente explícita y 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 de axiomas en cuestión es consistente, no es posible demostrarlo mediante dichos axiomas.

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]

Contexto

Los teoremas de incompletitud de Gödel establecen ciertas limitaciones sobre lo que es posible demostrar mediante un razonamiento matemático. Para hablar con precisión sobre qué «puede demostrarse» o no, se estudia un modelo matemático denominado teoría formal. Una teoría formal consta de una serie de signos y un conjunto de reglas para manipularlos y combinarlos. Mediante estas reglas se pueden distinguir ciertas colecciones de signos como fórmulas, y ciertas sucesiones de fórmulas como demostraciones. Los teoremas de una cierta teoría son entonces todas las fórmulas que puedan demostrarse a partir de una cierta colección inicial de fórmulas que se asuman como axiomas.

A una teoría formal se le pueden adjudicar ciertas propiedades en función de lo que sea capaz de demostrar.

  • Una teoría consistente no contiene contradicciones, es decir, no es posible demostrar a la vez una fórmula y su contraria. Una teoría que no sea consistente no tiene utilidad: debido al principio de explosión, a partir de una contradicción pueden demostrarse todas sus fórmulas, y no sirve para modelizar razonamientos matemáticos.
  • Una teoría completa «responde cualquier pregunta», en el sentido de que para cada una de sus fórmulas o bien es demostrable, o bien existe una demostración de su contraria (es refutable). Una teoría completa es óptima, y se corresponde con la intuición sobre la verdad lógica: al igual que toda sentencia debe ser verdadera o falsa, en una teoría completa toda fórmula es demostrable o refutable.

Sin embargo, el primer teorema de incompletitud establece que, bajo ciertas hipótesis, una teoría formal no puede tener ambas propiedades a la vez. La primera de ellas es que sea una teoría aritmética, es decir, que sus símbolos sirvan para describir los números naturales y sus operaciones y relaciones; y que sea capaz de demostrar algunas propiedades básicas sobre ellos. La segunda hipótesis es que sea una teoría recursiva, lo cual significa que las reglas para manipular sus signos y fórmulas en las demostraciones han de poder ejecutarse mediante un algoritmo: una serie precisa de pasos sin ambigüedad que pueda llevarse a cabo en un tiempo finito, e incluso implementarse mediante un programa informático.

Other Languages