EPÓNIMOS

 Para el lenguaje de programación, véase Gödel (lenguaje de programación).

Kurt Friedrich Gödel
Kurt Friedrich Gödel en 1925
Información personal
Nacimiento	28 de abril de 1906 Brünn (Brno)  Imperio austrohúngaro
Fallecimiento	14 de enero de 1978 Princeton,  Estados Unidos
Causa de muerte	Inanición
Sepultura	Cementerio de Princeton
Residencia	Austria, Estados Unidos
Nacionalidad	Checoslovaca (1918-1929), austríaca (desde 1929) y estadounidense (desde 1948)
Religión	Cristianismo
Lengua materna	Alemán
Familia
Padres	Rudolf Gödel Marianne Gödel
Cónyuge	Adele Porkert
Educación
Educado en	Universidad de Viena
Tesis doctoral	Über die Vollständigkeit des Logikkalküls (1929)
Supervisor doctoral	Hans Hahn
Información profesional
Área	matemáticas, filosofía
Conocido por	Teorema de incompletitud de Gödel
Empleador	Instituto de Estudios Avanzados de Princeton
Obras notables	teoremas de incompletitud de Gödel teorema de completitud de Gödel numeración de Gödel Teoría de conjuntos de Von Neumann-Bernays-Gödel métrica de Gödel universo constructible Demostración ontológica de Gödel Función beta de Gödel Primer teorema de la incompletitud de Gödel
Miembro de	Real Sociedad de Londres Academia Estadounidense de las Artes y las Ciencias Academia de Ciencias de Francia Academia Nacional de Ciencias de los Estados Unidos Sociedad Filosófica Estadounidense (desde 1961)
Distinciones	Premio Albert Einstein (1951)
Firma
[editar datos en Wikidata]

Kurt Friedrich Gödel ([ˈkʊʁt ˈɡøːdəl]; Brünn, Imperio austrohúngaro, actual República Checa, 28 de abril de 1906-Princeton, Estados Unidos; 14 de enero de 1978), conocido como Kurt Gödel, fue un lógico, matemático y filósofo austríaco.^[1]

Se le considera uno de los lógicos más importantes de todos los tiempos. Su trabajo ha tenido un impacto inmenso en el pensamiento científico y filosófico del siglo XX. Al igual que otros pensadores —como Gottlob Frege, Bertrand Russell, A. N. Whitehead y David Hilbert—, Gödel intentó emplear la lógica y la teoría de conjuntos para comprender los fundamentos de la matemática.

Se le conoce sobre todo por sus dos teoremas de la incompletitud, publicados en 1931, un año después de finalizar su doctorado en la Universidad de Viena. El más célebre establece que para todo sistema axiomático recursivo autoconsistente lo suficientemente poderoso como para describir la aritmética de los números naturales (la aritmética de Peano), existen proposiciones verdaderas sobre los naturales que no pueden demostrarse a partir de los axiomas. Para demostrar este teorema, desarrolló una técnica denominada ahora numeración de Gödel, que codifica expresiones formales como números naturales.

También demostró que la hipótesis del continuo no puede refutarse desde los axiomas aceptados de la teoría de conjuntos, si dichos axiomas son consistentes. Realizó importantes contribuciones a la teoría de la demostración al esclarecer las conexiones entre la lógica clásica, la lógica intuicionista y la lógica modal.

Vida

Infancia

Kurt Friedrich Gödel nació el 28 de abril de 1906 en Brünn, la capital de la Moravia austrohúngara (actualmente Brno, República Checa) en una familia acomodada de etnia germana. Su padre, Rudolf August Gödel, era un hombre de negocios y administrador de una fábrica de textiles. Su madre, Marianne Gödel (nacida Handschuh), una mujer educada y culta, que permaneció cercana a Gödel durante toda su vida, tal como puede observarse en la extensa correspondencia entre ambos.^[2] En el momento de su nacimiento, la mayoría de la población de su ciudad era de habla alemana^[3] y este era el idioma de sus padres.^[4]

Gödel, que hablaba muy poco el checo, se convirtió automáticamente en checoslovaco a la edad de 12 años, tras la caída del Imperio austrohúngaro al final de la Primera Guerra Mundial. Posteriormente le contó a su biógrafo John W. Dawson que durante ese tiempo se sentía como un «exiliado austríaco en Checoslovaquia» (ein Österreicher im Exil in der Tschechoslowakei). Decidió convertirse en ciudadano austríaco a los 23 años. Cuando la Alemania nazi anexionó Austria, Gödel se convirtió automáticamente en ciudadano alemán, a los 32 años. Después de la Segunda Guerra Mundial, a los 42 años, se convirtió en ciudadano estadounidense.

Su familia llamaba al joven Kurt Herr Warum (Sr. Por qué), debido a su insaciable curiosidad. La única excepción a una infancia sin incidentes fue que a partir de los cuatro años sufrió quebrantos de salud y fiebres reumáticas. Se recuperó completamente, pero toda su vida quedó convencido de que su corazón había sufrido un daño permanente.

Asistió a la escuela primaria y secundaria en idioma alemán en Brno, de la que se graduó con honores en 1923 y sobresalió en matemáticas, idiomas y religión. En el transcurso de su adolescencia estudió, entre otras materias, la Teoría de los colores de Goethe, críticas de Isaac Newton y la obra de Immanuel Kant.

Estudios en Viena

A los 18 años, Kurt se reunió con su hermano mayor Rudolf (nacido en 1902) e ingresó en la Universidad de Viena. Entonces ya dominaba las matemáticas a nivel universitario. Aunque al principio pretendió estudiar física teórica, también asistió a cursos de filosofía impartidos por Heinrich Gomperz y de matemáticas. Durante este período adoptó ideas del empirismo matemático, leyó los Metaphysische Anfangsgründe der Naturwissenschaft (Fundamentos metafísicos de la ciencia natural) de Kant. Aunque él mismo no fue un positivista lógico, participó en reuniones del Círculo de Viena con Moritz Schlick, Hans Hahn y Rudolf Carnap, siendo estos dos últimos de quienes aprendió lógica. Después estudió también la teoría de los números. Asistió a un seminario dirigido por Schlick, en que se estudiaba el libro Introducción a la lógica matemática de Bertrand Russell, lo que le motivó a interesarse por la lógica matemática.

Su asistencia a una conferencia de Hilbert sobre la completud y la consistencia de los sistemas matemáticos pudo decidir el curso de su vida. En 1928, Hilbert y Wilhelm Ackermann publicaron los Grundzüge der theoretischen Logik (Principios de lógica teórica), una introducción a la lógica de primer orden en la cual se planteaba el problema de la completitud: «¿Son suficientes los axiomas de un sistema formal para derivar cada una de las proposiciones verdaderas en todos los modelos del sistema?». Este fue el tema elegido por Gödel para su disertación doctoral. En 1929, a los 23 años, completó su disertación bajo la supervisión de Hans Hahn, en la cual Gödel estableció la completud del cálculo de predicados de primer orden (este resultado se conoce ahora como el teorema de completitud de Gödel). El doctorado se le concedió en 1930. Su tesis, junto a trabajo adicional, fue publicada por la Academia de Ciencias de Viena.^[5]

Obra en Viena

En 1931 Gödel publicó sus célebres teoremas de la incompletud en Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados). En dicho artículo demostró que para todo sistema axiomático computable que sea lo suficientemente poderoso como para describir la aritmética de los números naturales (p. ej. los axiomas de Peano (o ZFC), entonces:

1. Si el sistema es coherente no puede ser completo. (A esto generalmente se le conoce como el teorema de la incompletitud).
2. La consistencia de los axiomas no puede demostrarse en el interior del sistema.

Estos teoremas finalizaron medio siglo de intentos académicos (comenzando con el trabajo de Frege y culminando en los Principia Mathematica y en el formalismo de Hilbert) por encontrar un conjunto de axiomas suficiente para toda la matemática. El teorema de la incompletud implica también que no toda la matemática es computable.

La idea básica del teorema de la incompletud es bastante simple. Esencialmente, Gödel construyó una fórmula que asegura ser no-demostrable para cierto sistema formal. Si fuera demostrable sería falsa, lo cual contradice el hecho de que en un sistema consistente las proposiciones demostrables son siempre verdaderas. De modo que siempre habrá por lo menos una proposición verdadera pero no demostrable. Esto es, para todo conjunto de axiomas de la aritmética construible por el hombre existe una fórmula que se obtiene de la aritmética pero es indemostrable en ese sistema. Sin embargo, para precisar esto Gödel necesitaba resolver varias cuestiones técnicas, tales como proposiciones de codificación y el concepto mismo de demostrabilidad en la teoría de los números naturales. Esto último lo realizó mediante un proceso denominado numeración de Gödel.

En su ensayo de dos páginas Zum intuitionistischen Aussagenkalkül (1932) Gödel refutó la “valuabilidad” finita de la lógica intuicionista. En la demostración empleó implícitamente lo que después se conoció como la lógica intermedia de Gödel–Dummett (o Gödel fuzzy logic).

Gödel recibió su habilitación en la Universidad de Viena en 1932, y en 1933 se convirtió en Privatdozent (permiso para enseñar y examinar de forma independiente en la universidad). La ascensión de Hitler en Alemania en 1933 afectó poco a Gödel en Viena, ya que tenía poco interés en la política. Sin embargo, en 1936 se vio muy afectado por el asesinato de Moritz Schlick (cuyo seminario había despertado su interés por la lógica) a manos del estudiante Hans Nelböck, quien declaró que mató a Schlick «por difundir ideas antimetafísicas que minan la moral y la cohesión de la vida».^[6] Este incidente le provocó un colapso nervioso y su primera crisis de paranoia. Dos años después, tras el Anschluss, el asesino fue liberado y se declaró nazi.^[6]

Visitas a los Estados Unidos

En 1933, Gödel viajó por primera vez a los Estados Unidos donde conoció a Albert Einstein, con quien estrechó lazos de amistad. Presentó una conferencia en la reunión anual de la Sociedad Norteamericana de Matemáticas. En el transcurso de ese año, Gödel también desarrolló ideas sobre la computabilidad y la función recursiva, e impartió una conferencia sobre dichas funciones y sobre el concepto de verdad. Posteriormente, este trabajo se desarrolló en la teoría de los números, empleando la numeración de Gödel.

En 1934, Gödel impartió una serie de conferencias en el Instituto de Estudios Avanzados (IEA) en Princeton, titulada Sobre las proposiciones indecidibles de los sistemas matemáticos formales. Stephen Kleene, quien acababa de finalizar su doctorado en Princeton, tomó notas de esta conferencia, que se publicaron posteriormente.

Gödel visitaría nuevamente el IEA en otoño de 1935, pero los viajes y el intenso trabajo lo habían extenuado. El año siguiente convaleció recuperándose de una depresión. No regresó a la docencia hasta 1937. Durante ese tiempo, se dedicó a probar la consistencia del axioma de elección y a la hipótesis del continuo, trabajo que continuó hasta mostrar que estas hipótesis no pueden refutarse desde el sistema común de axiomas de la teoría de conjuntos.

El 20 de septiembre de 1938 contrajo matrimonio con Adele Nimbursky (nacida Porkert, 1899-1981), a la que conocía desde hacía 10 años. Los padres de Gödel se oponían a esta relación. porque se trataba de una bailarina divorciada y seis años mayor que él. Nunca tuvieron hijos.

Posteriormente realizó otra visita a los Estados Unidos, donde pasó el otoño de 1938 en el IEA y la primavera de 1939 en la Universidad de Notre Dame. Durante sus vacaciones del IEA, Gödel y su esposa Adele pasaron el verano de 1942 en Blue Hill, Maine. Sin embargo Gödel no solo estaba descansando, pues tuvo un verano de trabajo muy productivo. John W. Dawson, Jr. conjetura que durante esas vacaciones Gödel, empleando el volumen 15 de su obra todavía sin publicar Arbeitshefte (Cuadernos de notas), descubrió una prueba de la independencia del axioma de elección de la teoría finita de tipos, una forma debilitada de la teoría de conjuntos. Hao Wang, amigo cercano de Gödel, apoya dicha conjetura, señalando que los cuadernos de notas de Blue Hill contienen su tratamiento más extenso del problema.

Trabajo en Princeton

Después del Anschluss en 1938, Austria pasó a formar parte de la Alemania nazi. Alemania abolió el título de Privatdozent, de modo que Gödel tuvo que concursar a un cargo diferente en el nuevo orden. Sin embargo, sus vínculos anteriores con miembros judíos del Círculo de Viena, especialmente con Hans Hahn, pesaban en su contra. Su situación se precipitó a finales de 1939, cuando se le encontró apto para el servicio militar, arriesgándolo a ser llamado a las filas del ejército alemán durante la II Guerra Mundial. Por esta razón emigró hacia los Estados Unidos para asumir un cargo docente en el IEA. Gödel y su esposa tuvieron que tomar el Ferrocarril Transiberiano hasta el Pacífico, navegando desde Japón hasta San Francisco (donde llegaron el 4 de marzo de 1940), y luego cruzaron los Estados Unidos en tren hasta Princeton.^[7]

Rápidamente retomó su trabajo en matemáticas y en 1940 publicó su obra Consistencia del axioma de elección y de la hipótesis del continuo generalizada con los axiomas de la teoría de conjuntos, que constituye un clásico de la matemática moderna. En dicho trabajo introdujo el universo construible, un modelo de la teoría de conjuntos en el cual los únicos conjuntos que existen son aquellos que pueden construirse a partir de conjuntos más simples. Gödel mostró que tanto el axioma de elección (AC) y la hipótesis del continuo generalizada (HCG) son verdaderas en el universo construible y por lo tanto deben de ser consistentes con los axiomas de Zermelo-Fraenkel para la teoría de conjuntos (ZF). Posteriormente Paul Cohen construyó un modelo de ZF en el cual AC y HCG son falsos. En conjunto, estas demostraciones significan que AC y HCG son independientes de los axiomas de ZF para la teoría de conjuntos.

Hacia el final de la década de 1940, Gödel demostró la existencia de soluciones paradójicas a las ecuaciones de campo de la relatividad general de Albert Einstein. Estos «universos rotatorios» permitirían viajar en el tiempo y provocaron dudas en Einstein sobre su propia teoría. Sus soluciones se conocen como la métrica de Gödel (o el Universo de Gödel).

Durante sus muchos años en el Instituto, los intereses de Gödel se tornaron hacia la filosofía y la física. Estudió y admiró las obras de Gottfried Leibniz, pero llegó a la conclusión (sin evidencia) de que la mayor parte del trabajo de Leibniz había sido suprimida. En menor medida también estudió a Kant y a Edmund Husserl. Al principio de los años 1970, Gödel distribuyó entre sus amistades una elaboración de la demostración ontológica de Leibniz sobre la existencia de Dios, la cual se conoce ahora como la demostración ontológica de Gödel.

En 1946, Gödel se convirtió en miembro permanente del IEA. Alrededor de este período dejó de publicar, aunque continuó trabajando. Se convirtió plenamente en profesor del instituto en 1955 y en profesor emérito en 1976.

En 1951, fue reconocido (junto a Julian Schwinger) con el primer Premio Albert Einstein, y también recibió la National Medal of Science en 1974.

Muerte

Tumba de Gödel y su esposa en Princeton

En sus últimos años, Gödel sufrió de períodos de inestabilidad y enfermedad mental. Tenía temores obsesivos a ser envenenado, y no comía a menos que su esposa Adele preparara su comida. A finales de 1977, Adele fue hospitalizada durante seis meses y no pudo continuar preparándole la comida. En su ausencia, Gödel rehusó comer, hasta el punto de dejarse morir de hambre. En el momento de su muerte pesaba unos 30 kg. El certificado de defunción en el Hospital de Princeton, el 14 de enero de 1978, dice que murió de «desnutrición e inanición causadas por perturbaciones en la personalidad».^[8]

Legado y distinciones

En su honor, en 1987 se fundó la Kurt Gödel Society, una organización internacional dedicada a la promoción de la investigación en lógica, filosofía e historia de las matemáticas. En 1951, la Universidad de Yale le nombró doctor honorario en literatura. También recibió un doctorado honorario en ciencias por la Universidad de Harvard en 1952, con una mención en la que se le declaró «el descubridor de la verdad matemática más significativa del siglo». Fue elegido miembro de la Academia Nacional de Ciencias en 1955 y de la Academia Norteamericana de las Artes y las Ciencias en 1957. En 1961 ingresó en la Sociedad Filosófica de América y en 1967 fue elegido miembro honorario de la Sociedad Matemática de Londres. Finalmente, en 1975 el presidente Gerald Ford le entregó la Medalla Nacional de las Ciencias.

La amistad de Gödel con Einstein

Albert Einstein

Albert Einstein y Gödel entablaron una amistad legendaria, compartida en las caminatas que daban juntos en el IEA de Princeton. La naturaleza de sus conversaciones -que realizaban en alemán, el idioma nativo de ambos- permaneció en el misterio para los otros miembros del Instituto. El economista Oskar Morgenstern recuerda que, hacia el final de su vida, Einstein le confió que «su propio trabajo ya no importaba mucho, que llegaba al instituto únicamente para tener el privilegio de caminar a casa junto a Gödel».^[9]

Einstein y Morgenstern asesoraron a Gödel para el examen de su ciudadanía estadounidense, preocupados porque el comportamiento impredecible de su amigo pusiera en riesgo su oportunidad. Cuando se mencionó brevemente el régimen nazi, Gödel informó al juez que presidía el examen que había descubierto una manera por la que una dictadura podría instaurarse legalmente en los EE. UU., mediante una contradicción lógica en la Constitución. Posteriormente este postulado ha recibido el nombre de fallo de Gödel. El juez, Einstein y Morgenstern le impidieron terminar la elaboración de su pensamiento y se le entregó la ciudadanía.

^[

EPÓNIMO :

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.

Síntesis

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 se pueden probar ni refutar 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 se pueda llevar a cabo mediante un algoritmo.^{[cita requerida]}

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, se puede construir una refutación, y viceversa. Sin embargo, la interpretación natural de dicha sentencia en términos de números naturales es verdadera.^[1]

Segundo teorema de incompletitud de Gödel

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] Los teoremas implican que los sistemas axiomáticos de primer orden tienen severas limitaciones para fundamentar las matemáticas, y supusieron un duro golpe para el llamado programa de Hilbert para la fundamentación de las matemáticas. Por otra parte, durante algún tiempo ni Hilbert ni otros de sus colaboradores fueron conscientes de la importancia del trabajo de Gödel para su programa.

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.

Primer teorema

El enunciado del primer teorema reza:

Primer teorema de incompletitud de Gödel Cualquier teoría aritmética recursiva que sea consistente es incompleta.

La demostración de este teorema pasa por construir una cierta fórmula, la «sentencia de Gödel» G, que no puede ser probada ni refutada en la teoría aritmética recursiva T: ni G ni ¬G (la negación de G) son teoremas de T. Se dice entonces que G y ¬G son indecidibles o independientes en T.

Para llegar a esta, Gödel desarrolló un método para codificar signos y fórmulas mediante números, llamado numeración de Gödel. Usando esta numeración, es posible traducir las propiedades de una teoría formal T, tales como «estos signos constituyen una fórmula» o «estas fórmulas no son una demostración en T», a propiedades aritméticas de dichos números. En particular, la sentencia de Gödel G es una fórmula aritmética cuyo significado es «no existe una demostración de G en la teoría T», o en otras palabras, «no soy demostrable en la teoría T».

Consecuencias

La sentencia de Gödel G no es demostrable pero es cierta, pues afirma precisamente su propia indemostrabilidad.^[2] Esto significa que ninguna teoría aritmética en las condiciones del teorema es capaz de demostrar todos los enunciados verdaderos de la aritmética.^[1]

Además, aunque ¬G sea falsa (por afirmar lo contrario que G) no es refutable (puesto G es indemostrable). Esta sentencia puede tomarse como axioma si se desea y esto no produce una contradicción. La teoría resultante contiene muchos de los enunciados verdaderos sobre los números naturales y algunos falsos, empezando por ¬G. Los objetos descritos por una teoría así forman un modelo no estándar de la aritmética.^[3]

Tomando G (o su contraria) como axioma se obtiene una nueva teoría T' en la que G (o su contraria) es demostrable automáticamente. Sin embargo esto no invalida el teorema, puesto que G afirma su indemostrabilidad relativa a la teoría T. La nueva teoría T' es también incompleta: puede encontrarse una nueva sentencia independiente G', que afirma «no soy demostrable en T'».

En definitiva, en una teoría formal que sea consistente y completa debe fallar alguna de las hipótesis: o bien no es recursiva y no hay un algoritmo para distinguir los axiomas del resto de fórmulas; o bien no son aritméticas, y no incluyen las propiedades básicas necesarias de los números naturales. Por ejemplo, en la demostración del teorema de completitud semántica se utilizan teorías consistentes y completas que no son recursivas.^[4] Por otro lado, la aritmética de Presburger es una colección de axiomas sobre los números naturales que omite varias de sus propiedades, a tal punto que una teoría basada en ellos puede ser consistente y completa.^[5]

Segundo teorema

El segundo teorema de incompletitud muestra otro ejemplo explícito de una fórmula que ninguna teoría aritmética puede demostrar, además de G. De nuevo, usando la numeración de Gödel, puede encontrarse una fórmula, denotada Consis T, cuyo significado es «no puede encontrarse una contradicción en T», o en otras palabras, «T es consistente».

Segundo teorema de incompletitud de Gödel En toda teoría aritmética recursiva consistente T, la fórmula Consistente T no es un teorema.

La demostración del segundo teorema requiere traducir el primero a una fórmula. El primer teorema afirma, entre otras cosas, que si T es consistente, entonces G no es demostrable. La fórmula que afirma la consistencia de T es Consis T, mientras que la fórmula que afirma la indemostrabilidad de G es la propia G. La fórmula que traduce el primer teorema (una parte de él) es Consis T ⇒ G, donde «⇒» significa implicación. Gödel demostró que esta fórmula es un teorema,^[6] y que por lo tanto Consis T no es un teorema: si lo fuera, de las reglas básicas de T como teoría formal se deduciría que G es demostrable, en contradicción con el enunciado del primer teorema de incompletitud.

Consecuencias

El segundo teorema de incompletitud limita las posibilidades de demostrar la consistencia de una teoría formal T, puesto que no puede hacerse utilizando únicamente la propia T. Además, si se encuentra una teoría más fuerte T' en la que Consis T pueda demostrarse, la propia consistencia de T' no podrá demostrarse en T' ni tampoco en T. Por ello, el segundo teorema se considera una respuesta negativa al llamado programa de Hilbert, que proponía demostrar la corrección de los razonamientos matemáticos basados en objetos infinitos usando tan solo razonamientos basados en objetos finitos, menos potentes que los primeros.

Enunciados indecidibles

Artículo principal: Independencia lógica

El primer teorema de incompletitud de Gödel demuestra la existencia de enunciados indecidibles o independientes en la aritmética de Peano, y tanto el primero como el segundo muestran ejemplos concretos de enunciados indecidibles. Desde entonces se han encontrado otros ejemplos de enunciados independientes de los axiomas de Peano, como por ejemplo el teorema de Ramsey «fuerte». Existen además numerosos ejemplos de enunciados independientes en otras teorías formales más fuertes que la aritmética, como la hipótesis del continuo o el axioma de elección en teoría de conjuntos; o incluso en teorías no directamente relacionadas con la aritmética, como en el caso de la geometría euclídea y el postulado de las paralelas.

Discusión e implicaciones

Los resultados de incompletitud afectan a la filosofía de las matemáticas, particularmente a los puntos de vista tales como el formalismo, que usa la lógica formal para definir sus principios.

Se puede parafrasear el primer teorema diciendo que «nunca se podrá encontrar un sistema axiomático que sea capaz de demostrar todas las verdades matemáticas y ninguna falsedad».

Por otra parte, desde una perspectiva estrictamente formalista esta paráfrasis se consideraría sin significado porque presupone que la «verdad» y «falsedad» matemáticas están bien definidas en un sentido absoluto, en lugar de ser relativas a cada sistema formal.

La siguiente reformulación del segundo teorema es todavía más inquietante para los fundamentos de las matemáticas:

Si se puede demostrar que un sistema axiomático es consistente a partir de sí mismo, entonces es inconsistente.

Por tanto, para establecer la consistencia de un sistema ${\displaystyle S}$ se necesita utilizar otro sistema ${\displaystyle T}$, pero una prueba en ${\displaystyle T}$ no es totalmente convincente a menos que la consistencia de ${\displaystyle T}$ ya se haya probado sin emplear ${\displaystyle S}$. La consistencia de los axiomas de Peano para los números naturales por ejemplo se puede demostrar en la teoría de conjuntos, pero no en la teoría de los números naturales por sí sola. Esto proporciona una respuesta negativa al problema número dos de la famosa lista de cuestiones abiertas importantes en matemáticas de David Hilbert (llamada problemas de Hilbert).

En principio, los teoremas de Gödel todavía dejan alguna esperanza: podría ser posible producir un algoritmo general que para una afirmación dada determine si es indecidible o no, permitiendo a los matemáticos evitar completamente los problemas indecidibles. Sin embargo, la respuesta negativa al Entscheidungsproblem demuestra que no existe tal algoritmo.

Es de notar que los teoremas de Gödel solo son aplicables a sistemas axiomáticos suficientemente fuertes. Este término significa que la teoría contiene la suficiente aritmética para llevar a cabo las instrucciones de codificación requeridas por la prueba del primer teorema de incompletud. Esencialmente, todo lo que se exige son algunos hechos básicos sobre la adición y la multiplicación tal y como por ejemplo se formalizan en la aritmética Q de Robinson.

Hay sistemas axiomáticos incluso más débiles que son consistentes y completos, por ejemplo la aritmética de Presburger que demuestra todas las afirmaciones de primer orden ciertas aplicando solo la suma.

El sistema axiomático puede consistir en un número infinito de axiomas (tal y como hace la aritmética de primer orden de Peano), pero para poder aplicarse el teorema de Gödel debe haber un algoritmo efectivo que sea capaz a verificar la corrección de las pruebas. Por ejemplo, el conjunto de todas las declaraciones de primer orden que son ciertas en el modelo estándar de los números naturales es completo. El teorema de Gödel no se puede aplicar porque no hay ningún procedimiento efectivo que decide si una cierta declaración es un axioma. De hecho, que esto sea así es una consecuencia del primer teorema de incompletud de Gödel.

Otro ejemplo de una especificación de una teoría en la que el primer teorema de Gödel no es aplicable se puede construir de la siguiente manera: ordenemos todas las posibles declaraciones sobre los números naturales primero por su longitud y luego en orden lexicográfico; comencemos con un sistema axiomático inicialmente igual a los axiomas de Peano, repasemos la lista de declaraciones una a una, y, si la declaración actual no se puede demostrar ni refutar a partir del actual sistema de axiomas, entonces añadámosla a la lista. Esto crea un sistema que es completo, consistente y suficientemente potente, pero no recursivamente enumerable.

El propio Gödel solo demostró una versión de los teoremas arriba expuestos que es técnicamente un poco más débil; la primera demostración de las versiones descritas arriba fue dada por J. Barkley Rosser en 1936.

En esencia, la prueba del primer teorema consiste en construir una declaración ${\displaystyle p}$ dentro de un sistema formal axiomático al que se le puede dar la siguiente interpretación meta matemática:

${\displaystyle p=}$ «Esta declaración no se puede probar.»

Como tal, puede verse como una versión moderna de la paradoja del mentiroso. Al contrario de la declaración del mentiroso, ${\displaystyle p}$ no se refiere directamente a sí mismo; la interpretación de arriba solo se puede "ver" desde fuera del sistema formal.

En un trabajo publicado en 1957 en Journal of Symbolic Logic, Raymond Smullyan mostró que los resultados de incompletitud de Gödel pueden obtenerse para sistemas mucho más elementales que los considerados por Gödel. Smullyan también ha reivindicado las pruebas más simples con el mismo alcance, basadas en los trabajos de Alfred Tarski sobre el concepto de verdad en los sistemas formales. Más simples, pero no menos perturbadoras filosóficamente. Smullyan no ha plasmado sus reflexiones sobre incompletitud solo en obras técnicas; también han inspirado célebres libros de divulgación como ¿Cómo se llama este libro?

Si el sistema axiomático es consistente, la prueba de Gödel muestra que ${\displaystyle p}$ (y su negación) no se pueden demostrar en el sistema. Por tanto ${\displaystyle p}$ es cierto (${\displaystyle p}$ afirma no ser demostrable y no lo es) y, sin embargo, no se puede probar formalmente en el sistema. Fíjese que añadir ${\displaystyle p}$ a los axiomas del sistema no resolvería el problema: habría otra sentencia de Gödel para la teoría ampliada.

Roger Penrose afirma que esta (presunta) diferencia entre lo que se puede probar mecánicamente y lo que los humanos pueden ver como cierto muestra que la inteligencia humana no es mecánica en su naturaleza. También John R. Lucas se ha ocupado de esta cuestión en Mentes, Máquinas y Gödel.^[7]

Esta perspectiva no está ampliamente aceptada, porque tal y como lo plantea Marvin Minsky, la inteligencia humana es capaz de errar y de comprender declaraciones que son en realidad inconsistentes o falsas. Sin embargo, Minsky ha informado de que Kurt Gödel le dijo a él en persona que él creía que los seres humanos tienen una forma intuitiva, no solamente computacional, de llegar a la verdad y por tanto su teorema no limita lo que puede llegar a ser sabido como cierto por los humanos.

Véanse Refutaciones a la interpretación de Penrose en los Enlaces en Inglés de la sección Enlaces externos y referencias

La posición de que el teorema muestra que los humanos tienen una habilidad que transciende la lógica formal también se puede criticar de la siguiente manera: No sabemos si la sentencia ${\displaystyle p}$ es cierta o no, porque no sabemos (ni podemos saber) si el sistema es consistente. De modo que en realidad no sabemos ninguna verdad que esté fuera del sistema. Todo lo que sabemos es lo siguiente:

O ${\displaystyle p}$ es indemostrable dentro del sistema, o el sistema es inconsistente.

Esta declaración es fácilmente demostrable dentro del sistema.

Otra implicación es que el trabajo de Gödel motivó a Alan Turing (1912-1954) a estudiar qué funciones eran susceptibles de poder ser calculadas y cuáles no. Para ello se sirvió de su Máquina de Turing, una máquina de propósito general mediante la que formalizó las funciones y procedimientos de cálculo, demostrando que existían funciones que no son posibles de calcular mediante la Máquina de Turing. El paradigma de este conjunto de funciones lo representa la función que establece: «si dada una Máquina de Turing, esta produce un resultado o, por el contrario, se queda calculando indefinidamente». Esta función, conocida con el nombre de Problema de parada (Halting Problem), será pieza fundamental para demostrar la incomputabilidad de ciertas funciones.

Demostración de los teoremas

Este portal es tan solo divulgación invitamos al lector consultar bibliografía muy seria lo que decimos son descripciones no demostraciones indispensables La demostración de los teoremas de incompletitud se basa en tres conceptos, siguiendo el artículo de 1931 "SOBRE SENTENCIAS FORMALMENTE INDECIDIBLES DE PRINCIPIA MATHEMATICA Y SISTEMAS AFINES" :

1. La numeración de Gödel, que permite traducir las teorías formales a operaciones de aritmética pura.
2. La potencia expresiva de las teorías formales aritméticas, cuyas expresiones recogen dichas operaciones.
3. El lema diagonal, que permite que las fórmulas sean autorreferentes.

El enunciado original debido a Gödel, cuya demostración se esboza en esta sección, es más débil que el presentado arriba, ya que en lugar de la consistencia de la teoría T se exige una propiedad más fuerte, la ω-consistencia.

Una teoría aritmética es ω-inconsistente si, para alguno de sus teoremas formales de la forma ∃x, φ(x), puede refutarse cualquier caso particular, esto es, puede probarse ¬φ([n]), para cada numeral [n]. Una teoría que no es ω-inconsistente se dice ω-consistente.

(Los numerales [n] son los símbolos que utilice el lenguaje de la teoría para especificar los números naturales concretos. En el ejemplo de la aritmética de Peano en la sección siguiente, los numerales son los símbolos dados por: [0] ≡ 0, [1] ≡ S0, [2] ≡ SS0, etc.). La ω-consistencia implica la consistencia (pero no al revés). El enunciado «fuerte», en el que solo se requiere la consistencia de la teoría fue probado por J. B. Rosser mediante un método muy similar.

Numeración de Gödel

Artículo principal: Numeración de Gödel

La numeración de Gödel es una herramienta que permite relacionar las teorías formales con la aritmética. El lenguaje de una teoría formal de primer orden está compuesto por una cantidad —a lo sumo— numerable de signos, como por ejemplo:

∃ , ⇒ , ¬ , |, =, x , y , z , ... , 0 , + , × , S

en el caso del lenguaje de la aritmética de Peano, donde además de los símbolos lógicos y las variables, aparecen algunos símbolos adicionales para la arimética (donde S es el símbolo para denotar «el número siguiente a»). También el conjunto de todas las cadenas (sucesiones finitas de signos) es numerable, así como el conjunto de las sucesiones finitas de cadenas.

Una numeración de Gödel es una asignación de un único número natural para cada elemento de cada uno de estos tres conjuntos: signos, cadenas de signos y sucesiones de cadenas.

Ejemplo

Una posible codificación para los signos, cadenas y sucesiones de cadenas es la siguiente. Para los signos se adopta: «∃» → 10 , «⇒» → 11 , «¬» → 12 , «|» → 13 , «=» → 14 , «0» → 15 , «S» → 16 , «+» → 17 , «×» → 18 , «x» → 20 , «y» → 2000 , «z» → 200000 , … Dada una cadena de signos, se adopta el criterio de «apilar» los números de Gödel de sus signos, con un 77 inicial para indicar que se trata de una cadena: «x + [5] = 0» se torna en: 77-20-17-16-16-16-16-16-15-14-15, es decir, en 7720171616161616151415 Para una sucesión de cadenas de signos, puede adoptarse un convenio similar, con un 88 inicial, para indicar que se trata de una sucesión: La sucesión «0 = 1, y + 1 = 0» se convierte en: 88-77-15-14-16-15-77-2000-17-16-15-14-15, es decir en: 8877151416157720001716151415

Puesto que la manipulación de estos signos, cadenas y sucesiones puede traducirse en manipulación de unos ciertos números, tanto la sintaxis que distingue las cadenas de signos «con sentido» —las fórmulas− como el cálculo deductivo que distingue las sucesiones de cadenas «que demuestran algo» —las demostraciones— se ven traducidas a operaciones aritméticas. Es decir, existen una serie de relaciones y funciones aritméticas que se corresponden con las reglas sintácticas y del cálculo deductivo, como por ejemplo:

Sig x : x es (el número de Gödel de) un signo

Cad x : x es (el número de Gödel de) una cadena (de signos)

(Se omite «el número de Gödel de» en adelante)

Suc x : x es una sucesión (de cadenas)

Form x : la cadena x es una fórmula

Ax x : la fórmula x es un axioma

Cons(x, y, z): «x es una fórmula consecuencia inmediata de las fórmulas y y z»

Dem(x, y): «la sucesión x es una demostración de la fórmula y»

La forma precisa de estas funciones y relaciones es laboriosa y depende del criterio que se haya escogido para efectuar la numeración de Gödel. En particular la relación Ax x ha de construirse teniendo en cuenta un cierto conjunto de axiomas concreto, luego la relación Dem hace referencia a una teoría concreta que no se ha especificado.

Ejemplo

Es sencillo entender ahora cómo deben definirse algunas de estas relaciones según la numeración de Gödel mostrada antes: Sig x ≡ x está entre 10 y 18 (ambos inclusive), o es de la forma 20·100i (con i > 1) Cad x ≡ En base 10, x es de la forma 77n(s1)...n(sk), donde cada n(si) representa las cifras de un número tal que Sig n(si) es cierto Suc x ≡ En base 10, x es de la forma 88n(π1)...π(sk) donde cada n(πi) representa las cifras de un número tal que Cad n(πi) es cierto

Expresabilidad y recursividad

Artículo principal: Función recursiva

Mediante la numeración de Gödel, es posible «traducir» los signos y reglas de una teoría formal T en números y operaciones aritméticas. Es posible ir más allá, ya que T es una teoría aritmética y se pueden «recodificar» las mencionadas operaciones mediante el lenguaje formal de T, al igual que se puede hacer con otras funciones y relaciones aritméticas como por ejemplo:

La función «multiplicar por 2» está representada por la fórmula: y = [2] × x

La relación de orden x ≤ y, puede expresarse mediante: ∃z, z + x = y

La relación «x e y son primos entre sí» puede expresarse como: ∀z, z ≠ [1] ∧ ∃w, x = z × w ⇒ ¬∃u, y = z × u.

Cada una de estas relaciones es expresada por su fórmula correspondiente, en el sentido de que si dos números están relacionados, puede demostrarse la expresión formal correspondiente; y cuando no lo están, puede refutarse.^[8] Por ejemplo:

Para cada entero n, se tiene que si n es par puede probarse la expresión formal ∃x, [n] = [2] × x; y si es impar, puede refutarse dicha fórmula.

Para cada par de enteros m y n, si se tiene m ≤ n puede demostrarse la fórmula ∃z, z + [m] = [n]; cuando m > n, puede refutarse dicha expresión.

Que las relaciones presentadas en la sección anterior —como Dem— sean expresables, implica que una teoría formal aritmética es lo suficientemente potente como para «hablar» de las características de una teoría formal arbitraria y, en particular, de sí misma.

Probar que todas estas relaciones y funciones son expresables es sencillo si son recursivas, es decir, si pueden calcularse o verificarse mediante un algoritmo, ya que puede demostrarse que toda relación recursiva es expresable en una teoría aritmética. Las teorías formales para las que esto es posible —asignar los números de Gödel de manera que distinguir los signos, cadenas, sucesiones, fórmulas, consecuencias y axiomas, puede llevarse a cabo con un algoritmo— son las llamadas teorías recursivas, y por ello esta característica se asume como hipótesis en los teoremas de incompletitud.

Diagonalización

Para construir la sentencia autorreferente G ha de idearse una manera para que una fórmula hable de las propiedades de su número de Gödel correspondiente. Esto ha de hacerse de manera indirecta, ya que dada una fórmula φ con número de Gödel n, otra fórmula que «hable» de φ mediante el numeral [n] en general tendrá un número de Gödel mayor que n, y por tanto no puede ser la propia φ. Esto se consigue mediante el llamado lema diagonal.

En una teoría aritmética recursiva, dada una fórmula φ(x) existe una sentencia ψ con número de Gödel n tal que puede demostrarse ψ ⇔ φ([n]).

En definitiva, dada una propiedad cualquiera φ(x) existe una sentencia ψ que afirma «mi número de Gödel cumple la propiedad φ».

Demostración del primer teorema

Sea una teoría formal aritmética y recursiva T ω-consistente. Sea la fórmula ¬∃z, DEM(z, x), donde DEM es la fórmula que expresa la relación numérica Dem —relativa a la teoría formal T—. Por el lema de diagonalización existe una sentencia G con número de Gödel g, para la que se demuestra G ⇔ ¬∃z, DEM(z, [g]), es decir, que afirma «ningún número codifica una demostración (en T) de la fórmula representada por g», o de otro modo, «no soy demostrable (en T)». La negación de esta sentencia, ¬G, es equivalente a ∃z, DEM(z, [g]), o «mi negación es demostrable (en T)».

Supóngase entonces que G puede demostrarse. Entonces existe un número n que cumple Dem(n, g), y en T puede probarse entonces DEM([n], [g]), lo cual implica formalmente ¬G; y esto es imposible si T es consistente. Por tanto no existe una demostración de G, y se cumple ¬Dem(n, g) para todos los números n, lo cual resulta en un número infinito de teoremas formales ¬DEM([n], [g]) para cada numeral [n]. Como T es ω-consistente, no puede ocurrir entonces que ∃x, DEM(x, [g]) sea un teorema, por lo que ¬G es indemostrable, y T es indecidible.

Demostración del segundo teorema

La demostración del segundo teorema de incompletitud requiere de un hecho técnico que Gödel originalmente no probó. Sea una teoría T en las condiciones anteriores y sea la fórmula Consis T ≡ ¬∃z, DEM(z, [k]), donde k es el número de Gödel de la sentencia 0 = 1. Consis T afirma que la teoría T es consistente (pues deja algo sin demostrar). La versión formal (de la primera parte) del primer teorema de incompletitud puede expresarse como Consis T ⇒ ¬∃y, DEM(y, [g]) y esto es equivalente precisamente a Consis T ⇒ G. De modo que, de poder probar formalmente esta sentencia, Consis T sería indemostrable puesto que se tendría entonces una demostración de G, en contradicción con el primer teorema.

El hecho técnico que se necesita es precisamente una prueba de que la demostración del primer teorema de incompletitud puede «traducirse» en una demostración formal de la sentencia Consis T ⇒ ¬∃y, DEM(y, [g]). Esto es posible en toda teoría aritmética recursiva, ya que verifican unas ciertas condiciones de demostrabilidad.