Teorema de Godel

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 consuficiente expresividad, es a la vez consistente y completa. Es decir, si los axiomasde 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 cabomediante 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 casoparticular 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 comunidadmatemática— una respuesta negativa al segundo problema de Hilbert.1
Índice
  [ocultar] 
1 Contexto
2 Primer teorema
2.1 Consecuencias
3 Segundo teorema
3.1 Consecuencias
4 Enunciados indecidibles
5 Malentendidos en torno a los teoremas de Gödel
6 Discusión e implicaciones
7 Demostración de los teoremas
7.1 Numeración de Gödel
7.2 Expresabilidad. Recursividad
7.3 Diagonalización7.4 Demostración del primer teorema
7.5 Demostración del segundo teorema
8 Véase también
9 Referencias
10 Bibliografía
11 Enlaces externos
Contexto[editar]
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 de que «puede demostrarse» o no, se estudia un modelo matemático denominado teoríaformal. 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órmulasque 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 todassus 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 ofalsa, 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 losnúmeros naturales y sus operaciones y relaciones; y que sea capaz de...