thumb|250px|Kurt Gödel a los 19 años d'edá, cinco años antes de la demostración de los teoremes. Los teoremes d'incompletitú de Gödel son dos célebres teoremes de lóxica matemática demostraos por Kurt Gödel en 1931. Dambos tán rellacionaos cola esistencia de proposiciones indecidibles en ciertes teoríes aritmétiques.
El primer teorema de incompletitud afirma que, so ciertes condiciones, nenguna teoría matemática formal capaz de describir los númberos naturales y l'aritmética con abonda espresividá, ye al empar consistente y completa. Esto ye, si los axomes de dicha teoría nun se contradicen ente sigo, entós esisten enunciaos que nun pueden probase nin refutarse a partir d'ellos. En particular, la conclusión del teorema aplícase siempres que la teoría aritmética en cuestión sía recursiva, esto ye, una teoría na que'l procesu de deducción pueda llevase a cabu por aciu un algoritmu.
La prueba del teorema ye totalmente esplícita y nella constrúi una fórmula, denotada davezu n'honor a Gödel, pa la que dada una demostración de la mesma, puede construyise una refutación, y viceversa. Sicasí, la interpretación natural de dicha sentencia en términos de númberos naturales ye verdadera.Vease la parte dedicada a Gödel na introducción de .
El segundu teorema de incompletitud ye un casu particular del primeru: afirma qu'una de les sentencies indecidibles de dicha teoría ye aquella que «afirma» la consistencia de la mesma. Esto ye, que si'l sistema d'axomes en cuestión ye consistente, nun ye posible demostralo por aciu dichos axomes.
Los teoremes d'incompletitú de Gödel son unu de les grandes meyores de la lóxica matemática, y supunxeron —según la mayoría de la comunidá matemática— una respuesta negativa al segundu problema de Hilbert.
Contestu Los teoremes d'incompletitú de Gödel establecen ciertes llimitaciones sobre lo que ye posible demostrar por aciu un razonamientu matemáticu. Pa falar con precisión sobre qué «puede demostrase» o non, estúdiase un modelu matemáticu denomináu teoría formal. Una teoría formal consta d'una serie de signos y un conxuntu de regles pa manipolialos y combinalos. Por aciu estes regles pueden estremase ciertes coleiciones de signos como fórmules, y ciertes socesiones de fórmules como demostraciones. Los teoremes d'una cierta teoría son entós toles fórmules que puedan demostrase a partir d'una cierta coleición inicial de fórmules que s'asuman como axomes.
A una teoría formal pueden axudicáse-y ciertes propiedaes en función de lo que sía capaz de demostrar. Una teoría consistente nun contién contradicciones, esto ye, nun ye posible demostrar al empar una fórmula y la so contraria. Una teoría que nun sía consistente nun tien utilidá: debíu al principiu d'esplosión, a partir d'una contradicción pueden demostrase toles sos fórmules, y nun sirve pa modelizar razonamientos matemáticos. Una teoría completa «respuende cualquier entruga», nel sentíu de que pa caúna de les sos fórmules o bien ye demostrable, o bien esiste una demostración de la so contraria (ye refutable). Una teoría completa ye óptima, y correspuéndese cola intuición sobre la verdá lóxica: al igual que toa sentencia tien de ser verdadera o falsa, nuna teoría completa toa fórmula ye demostrable o refutable.
Sicasí, el primer teorema de incompletitud establez que, so ciertes hipótesis, una teoría formal nun puede tener dambes propiedaes al empar. La primera d'elles ye que sía una teoría aritmética, esto ye, que los sos símbolos sirvan pa describir los númberos naturales y les sos operaciones y rellaciones; y que sía capaz de demostrar delles propiedaes básiques sobre ellos. La segunda hipótesis ye que sía una teoría recursiva, lo cual significa que les regles pa manipoliar los sos signos y fórmules nes demostraciones han de poder executase por aciu un algoritmu: una serie precisa de pasos ensin ambigüedá que pueda llevase a cabu nun tiempu finito, ya inclusive implementase por aciu un programa informáticu.
Primer teorema L'enunciáu del primer teorema reza:
La demostración d'esti teorema pasa por construyir una cierta fórmula, la sentencia de Gödel» , que nun puede ser probada nin refutada en : nin nin (la negación de ) son teoremes de . Dizse entós que y son indecidibles o independientes en .
Pa llegar a esta, Gödel desenvolvió un métodu pa codificar signos y fórmules por aciu númberos, llamáu numberación de Gödel. Usando esta numberación, ye posible traducir les propiedaes d'una teoría formal , tales como «estos signos constitúin una fórmula» o «estes fórmules nun son una demostración en », a propiedaes aritmétiques de dichos númberos. En particular, la sentencia de Gödel ye una fórmula aritmética que'l so significáu ye «nun esiste una demostración de na teoría », o n'otres pallabres, «nun soi demostrable na teoría ».
Consecuencies La sentencia de Gödel nun ye demostrable pero ye cierta, pos afirma precisamente la so propia indemostrabilidad.Esto namái ye ciertu na interpretación natural en que les variables de la teoría interprétense como los númberos naturales. Esto significa que nenguna teoría aritmética nes condiciones del teorema ye capaz de demostrar tolos enunciaos verdaderos de l'aritmética.
Amás, anque sía falsa (por afirmar lo contrario que ) nun ye refutable (puestu ye indemostrable). Esta sentencia puede tomase como axoma si deseyar y esto nun produz una contradicción. La teoría resultante contién munchos de los enunciaos verdaderos sobre los númberos naturales y dellos falsos, empezando por . Los oxetos descritos por una teoría asina formen un modelu non estándar de l'aritmética.Vease pa una esposición de nivel entemediu sobre l'aritmética non estándar.
Tomando (o la so contraria) como axoma llógrase una nueva teoría na que (o la so contraria) ye demostrable automáticamente. Sicasí esto nun invalida'l teorema, yá que afirma'l so indemostrabilidad relativa a la teoría . La nueva teoría ye tamién incompleta: puede atopase una nueva sentencia independiente , qu'afirma «nun soi demostrable en ».
A última hora, nuna teoría formal que sía consistente y completa tien de fallar dalguna de les hipótesis: o bien nun ye recursiva y nun hai un algoritmu pa estremar los axomes del restu de fórmules; o bien nun son aritmétiques, y nun inclúin les propiedaes básiques necesaries de los númberos naturales. Por casu, na demostración del teorema de completitud semántica utilícense teoríes consistentes y completes que nun son recursivas.Vease . Per otru llau, l'aritmética de Presburger ye una coleición d'axomes sobre los númberos naturales qu'omite delles de les sos propiedaes, a tal puntu qu'una teoría basada nellos pue ser consistente y completa.Vease .
Segundu teorema El segundu teorema de incompletitud amuesa otru exemplu esplícitu d'una fórmula que nenguna teoría aritmética puede demostrar, amás de . De nuevu, usando la numberación de Gödel, puede atopase una fórmula, denotada , que'l so significáu ye «nun puede atopase una contradicción en », o n'otres pallabres, « ye consistente».
La demostración del segundu teorema requier traducir el primeru a una fórmula. El primer teorema afirma, ente otres coses, que si ye consistente, entós nun ye demostrable. La fórmula qu'afirma la consistencia de ye , ente que la fórmula qu'afirma la indemostrabilidad de ye la mesma . La fórmula que traduz el primer teorema (una parte d'él) ye , onde «» significa implicación. Gödel demostró qu'esta fórmula ye un teorema,En realidá, la prueba orixinal de Gödel omite ciertos detalles téunicos. y que polo tanto nun ye un teorema: si dir, de les regles básiques de como teoría formal deduciríase que ye demostrable, en contradicción col enunciáu del primer teorema de incompletitud.
Consecuencies El segundu teorema de incompletitud llinda les posibilidaes de demostrar la consistencia d'una teoría formal , yá que nun puede faese utilizando namái la mesma . Amás, si atopa una teoría más fuerte na que pueda demostrase, la mesma consistencia de nun va poder demostrase en nin tampoco en . Por ello, el segundu teorema considérase una respuesta negativa al llamáu programa de Hilbert, que proponía demostrar la correición de los razonamientos matemáticos basaos n'oxetos infinitu usando tan solu razonamientos basaos n'oxetos finitos, menos potentes que los primeres.
Enunciaos indecidibles
El primer teorema de inconmpletitud de Gödel demuestra la esistencia d'enunciaos indecidibles o independientes na aritmética de Peano, y tantu el primeru como'l segundu amuesen exemplos concretos d'enunciaos indecidibles. Dende entós atopáronse otros exemplos d'enunciaos independientes de los axomes de Peano, como por casu el teorema de Ramsey «fuerte». Esisten amás numberosos exemplos d'enunciaos independientes n'otres teoríes formales más fuertes que l'aritmética, como la hipótesis del continuu o'l axoma d'elección en teoría de conxuntos; o inclusive en teoríes non direutamente rellacionaes cola aritmética, como nel casu de la xeometría euclídea y el postuláu de les paraleles.
Discutiniu ya implicaciones Los resultaos de incompletitud afecten a la filosofía de les matemátiques, particularmente a los puntos de vista tales como'l formalismu, qu'usa la lóxica formal pa definir los sos principios.
Puede parafrasiase el primer teorema diciendo "nunca podrá atopase un sistema axomáticu que sía capaz de demostrar toes les verdaes matemátiques y nenguna falsedá".
Per otra parte, dende una perspeutiva puramente formalista esta paráfrasis considerar ensin significáu porque presupon que la verdá» y «falsedá» matemátiques tán bien definíes nun sentíu absolutu, en llugar de ser relatives a cada sistema formal.
La siguiente reformulación del segundu teorema ye inda más esmolecedor pa los fundamentos de les matemátiques:
Si puede demostrase qu'un sistema axomáticu ye consistente a partir de sigo mesmu, entós ye inconsistente.
Por tanto, pa establecer la consistencia d'un sistema precísase utilizar otru sistema , pero una prueba en nun ye totalmente convincente nun siendo que la consistencia de yá se probara ensin emplegar . La consistencia de los axomes de Peano pa los númberos naturales por casu puede demostrase na teoría de conxuntos, pero non na teoría de los númberos naturales por sigo sola. Esto apurre una respuesta negativa al problema número dos de la famosa llista de cuestiones abiertes importantes en matemátiques de David Hilbert (llamada problemes de Hilbert).
En principiu, los teoremes de Gödel inda dexen dalguna esperanza: podría ser posible producir un algoritmu xeneral que pa una afirmación dada determine si ye indecidible o non, dexando a los matemáticos evitar dafechu los problemes indecidibles. Sicasí, la respuesta negativa al Entscheidungsproblem demuestra que nun esiste tal algoritmu.
Ye de notar que los teoremes de Gödel namái son aplicables a sistemes axomáticos abondo fuertes. Esti términu significa que la teoría contién l'abonda aritmética pa llevar a cabu les instrucciones de codificación riquíes pola prueba del primer teorema de incompletud. Esencialmente, tou lo que s'esixe son dellos fechos básicos sobre la adición y la multiplicación tal que por casu formalícense na aritmética Q de Robinson.
Hai sistemes axomáticos inclusive más débiles que son consistentes y completos, por casu l'aritmética de Presburger que demuestra toles afirmaciones de primer orde ciertes aplicando namái la suma.
El sistema axomáticu puede consistir nun númberu infinitu d'axomes (tal que fai l'aritmética de primer orde de Peano), pero pa poder aplicase'l teorema de Gödel tien d'haber un algoritmu efectivu que sía capaz a verificar la correición de les pruebes. Por casu, el conxuntu de toles declaraciones de primer orde que son ciertes nel modelu estándar de los númberos naturales ye completu. El teorema de Gödel nun puede aplicase porque nun hai nengún procedimientu efectivu que decide si una cierta declaración ye un axoma. Ello ye que qu'esto sía asina ye una consecuencia del primer teorema de incompletud de Gödel.