Ver la fonte de Teoremas de incompletitud de Gödel

[[Ficheru:1925 kurt gödel.png|thumb|250px|[[Kurt Gödel]] a los 19 años d'edá, 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óxica matemática]] demostraos por [[Kurt Gödel]] en [[1931]]. Dambos tán rellacionaos cola esistencia de [[proposición|proposiciones]] [[Independencia (lóxica matemática)|indecidibles]] en ciertes teoríes [[aritmética|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 [[consistencia (lóxica)|consistente]] y [[Completitud semántica|completa]]. Esto ye, si los [[axoma|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 {{math|''G''}} 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 felicidá sentencia en términos de númberos naturales ye verdadera.<ref name="GEBintro">Vease la parte dedicada a [[Kurt Gödel|Gödel]] na introducción de {{Harvsp|Hofstadter|1989}}.</ref>

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 teoremas de incompletitud 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 [[Problemes de Hilbert|segundu problema de Hilbert]].<ref name="GEBintro" />

== Contestu ==
Los teoremas de incompletitud 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 (lóxica matemática)|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órmula bien formada|fórmules]], y ciertes socesiones de fórmules como demostraciones. Los teoremas 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 [[consistencia lóxica|teoría consistente]] nun contién contradicciones, esto ye, nun ye posible demostrar al empar una fórmula y la so [[negación lóxica|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 [[completitud sintáctica|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:
{{teorema|títulu=Primer teorema de incompletitud de Gödel|1=Cualquier teoría aritmética recursiva que sía consistente ye incompleta.}}
La demostración d'esti teorema pasa por construyir una cierta fórmula, la sentencia de Gödel» {{math|''G''}}, que nun puede ser probada nin refutada en {{math|''T''}}: nin {{math|''G''}} nin {{math|¬''G''}} (la negación de {{math|''G''}}) son teoremas de {{math|''T''}}. Dizse entós que {{math|''G''}} y {{math|¬''G''}} son indecidibles o [[independencia lóxica|independientes]] en {{math|''T''}}.

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 {{math|''T''}}, tales como «estos signos constitúin una fórmula» o «estes fórmules nun son una demostración en {{math|''T''}}», a propiedaes aritmétiques de dichos númberos. En particular, la sentencia de Gödel {{math|''G''}} ye una fórmula aritmética que'l so significáu ye «nun esiste una demostración de {{math|''G''}} na teoría {{math|''T''}}», o n'otres pallabres, «nun soi demostrable na teoría {{math|''T''}}».

=== Consecuencies ===
La sentencia de Gödel {{math|''G''}} nun ye demostrable pero ye cierta, pos afirma precisamente la so propia indemostrabilidad.<ref>Esto namái ye ciertu na '''interpretación natural''' en que les variables de la teoría interprétense como los [[númberos naturales]].</ref> Esto significa que nenguna teoría aritmética nes condiciones del teorema ye capaz de demostrar tolos enunciaos verdaderos de l'aritmética.<ref name="GEBintro" /> 

Amás, anque {{math|¬''G''}} sía falsa (por afirmar lo contrario que {{math|''G''}}) nun ye refutable (puestu {{math|''G''}} 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 {{math|¬''G''}}. Los oxetos descritos por una teoría asina formen un [[aritmética non estándar|modelu non estándar]] de l'aritmética.<ref>Vease {{Harvsp|Hofstadter|1989|loc=§XIV}} pa una esposición de nivel entemediu sobre l'aritmética non estándar.</ref>

Tomando {{math|''G''}} (o la so contraria) como axoma llógrase una nueva teoría {{math|''T<nowiki>'</nowiki>''}} na que {{math|''G''}} (o la so contraria) ye demostrable automáticamente. Sicasí esto nun invalida'l teorema, yá que {{math|''G''}} afirma'l so indemostrabilidad relativa a la teoría {{math|''T''}}. La nueva teoría {{math|''T<nowiki>'</nowiki>''}} ye tamién incompleta: puede atopase una nueva sentencia independiente {{math|''G<nowiki>'</nowiki>''}}, qu'afirma «nun soi demostrable en {{math|''T<nowiki>'</nowiki>''}}».

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.<ref>Vease {{Harvsp|Boolos|2007|loc=§17.2}}.</ref> 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.<ref>Vease {{Harvsp|Boolos|2007|loc=§24}}.</ref>

== 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 {{math|''G''}}. De nuevu, usando la numberación de Gödel, puede atopase una fórmula, denotada {{math|Consis ''T''}}, que'l so significáu ye «nun puede atopase una contradicción en {{math|''T''}}», o n'otres pallabres, «{{math|''T''}} ye consistente».

{{teorema|títulu=Segundu teorema de incompletitud de Gödel|1=En toa teoría aritmética recursiva consistente {{math|''T''}}, la fórmula {{math|Consistente ''T''}} nun ye un teorema.}}

La demostración del segundu teorema rique traducir el primeru a una fórmula. El primer teorema afirma, ente otres coses, que si {{math|''T''}} ye consistente, entós {{math|''G''}} nun ye demostrable. La fórmula qu'afirma la consistencia de {{math|''T''}} ye {{math|Consis ''T''}}, ente que la fórmula qu'afirma la indemostrabilidad de {{math|''G''}} ye la mesma {{math|''G''}}. La fórmula que traduz el primer teorema (una parte d'él) ye {{math|Consis ''T'' {{unicode|⇒}} ''G''}}, onde «{{math|{{unicode|⇒}}}}» significa [[implicación lóxica|implicación]]. Gödel demostró qu'esta fórmula ye un teorema,<ref>En realidá, la prueba orixinal de Gödel omite ciertos detalles téunicos.{{ensin referencies}}</ref> y que polo tanto {{math|Consis ''T''}} nun ye un teorema: si dir, de les regles básiques de {{math|''T''}} como teoría formal deduciríase que {{math|''G''}} 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 {{math|''T''}}, yá que nun puede faese utilizando namái la mesma {{math|''T''}}. Amás, si atopa una teoría más fuerte {{math|''T<nowiki>'</nowiki>''}} na que {{math|Consis ''T''}} pueda demostrase, la mesma consistencia de {{math|''T<nowiki>'</nowiki>''}} nun va poder demostrase en {{math|''T<nowiki>'</nowiki>''}} nin tampoco en {{math|''T''}}. 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 [[finito|finitos]], menos potentes que los primeres.

== Enunciaos indecidibles ==
{{AP|Independencia lóxica}}
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 Paris-Harrington|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 ==
Les resultancies de incompletitud afecten a la [[filosofía de les matemátiques]], particularmente a los puntos de vista tales como'l [[Lóxica simbólica|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 <math>S</math> precísase utilizar otru sistema <math>T</math>, pero una prueba en <math>T</math> nun ye totalmente convincente nun siendo que la consistencia de <math>T</math> yá se probara ensin emplegar <math>S</math>.
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 teoremas 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 teoremas 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.

Otru exemplu d'una especificación d'una teoría na que'l primera teorema de Gödel nun ye aplicable puede construyise de la siguiente manera: ordenemos toles posibles declaraciones sobre los númberos naturales primeru pol so llargor y depués en [[orde lexicográficu]]; empecemos con un sistema axomáticu primeramente igual a los axomes de Peano, repasemos la llista de declaraciones una a una, y, si la declaración actual nun puede demostrase nin refutar a partir del actual sistema d'axomes, entós añadámosla a la llista.
Esto crea un sistema que ye completu, consistente y abondo potente, pero non [[conxuntu recursivamente enumerable|recursivamente enumerable]].

El mesmu Gödel namái demostró una versión de los teoremas enriba espuestos que ye téunicamente un pocu más débil; la primer demostración de les versiones descrites enriba foi dada por [[J. Barkley Rosser]] en [[1936]].

N'esencia, la prueba del primer teorema consiste en construyir una declaración <math>p</math> dientro d'un sistema formal axomáticu al que se-y puede dar la siguiente interpretación meta matemática:

:<math>p =</math> «Esta declaración nun puede probase.»

Como tal, puede trate como una versión moderna de la [[paradoxa del mentirosu]]. Al contrariu de la declaración del mentirosu, <math>p</math> nun se refier direutamente a sigo mesmu; la interpretación de riba namái se puede "ver" dende fora del sistema formal.

Nun trabayu publicáu en 1957 en ''Journal of Symbolic Logic'', [[Raymond Smullyan]] amosó que los resultaos de incompletitud de Gödel pueden llograse pa sistemes muncho más elementales que los consideraos por Gödel. Smullyan tamién reivindicó les pruebes más simples col mesmu algame, basaes nos trabayos d'[[Alfred Tarski]] sobre'l conceutu de verdá nos sistemes formales. Más simples, pero non menos perturbadoras filosóficamente. Smullyan nun afiguró les sos reflexones sobre incompletitud namái n'obres téuniques; tamién inspiraron célebres llibros de divulgación como ''¿Cómo se llama esti llibru?'' 

Si'l sistema axomáticu ye consistente, la prueba de Gödel amuesa que <math>p</math> (y la so negación) non pueden demostrase nel sistema.
Por tanto <math>p</math> ye ''ciertu'' (<math>p</math> afirma nun ser demostrable y nun lo ye) y, sicasí, nun puede probase formalmente nel sistema.
Afítese qu'añader <math>p</math> a los axomes del sistema nun resolvería'l problema: habría otra sentencia de Gödel pa la teoría ampliada.

[[Roger Penrose]] afirma qu'esta (presunta) diferencia ente ''lo que puede probase mecánicamente'' y ''lo que los humanos pueden ver como ciertu'' amuesa que la intelixencia humana nun ye mecánica na so naturaleza. Tamién [[John R. Lucas]] ocupóse d'esta cuestión en ''Mentes, Máquines y Gödel''.<ref>{{cita web |url=http://users.ox.ac.uk/~jrlucas/mmg.html |títulu=Minds, Machines and Gödel |fechaaccesu=15 de setiembre de 2011 |apellíu=Lucas |nome=John R. |idioma=inglés |urlarchivu=https://web.archive.org/web/20180506135515/http://users.ox.ac.uk/~jrlucas/mmg.html |fechaarchivu=2018-05-06 }}</ref>

Esta perspeutiva nun ta llargamente aceptada, porque tal que lo plantega [[Marvin Minsky]], la intelixencia humana ye capaz d'errar y de ''entender'' declaraciones que son en realidá inconsistentes o falses. Sicasí, Minsky informó de que [[Kurt Gödel]] díxo-y a él en persona qu'él creía que los seres humanos tienen una forma intuitiva, non solamente computacional, de llegar a la verdá y por tanto'l so teorema nun llinda lo que puede aportar a sabíu como ciertu polos humanos.

Veanse '''Refutaciones a la interpretación de Penrose''' nos ''Enllaces n'Inglés'' de la seición ''Enllaces esternos y referencies''

La posición de que'l teorema amuesa que los humanos tienen una habilidá que transciende la lóxica formal tamién puede criticase de la siguiente manera: Nun sabemos si la sentencia <math>p</math> ye cierta o non, porque nun sabemos (nin podemos saber) si'l sistema ye consistente.
De cuenta qu'en realidá nun sabemos nenguna verdá que tea fuera del sistema.
Tou lo que sabemos ye lo siguiente:

:O <math>p</math> ye indemostrable dientro del sistema, o'l sistema ye inconsistente.

Esta declaración ye fácilmente demostrable ''dientro del sistema''.

'''Otra implicación''' ye que'l trabayu de Gödel motivó a [[Alan Turing]] (1912-1954) a estudiar qué funciones yeren susceptibles de poder ser calculaes y cuálos non. Pa ello sirvióse del so [[Máquina de Turing]], una máquina de propósitu xeneral por aciu la que formalizó les funciones y procedimientos de cálculu. Demostrando qu'esistíen funciones que nun son posibles de calcular por aciu la Máquina de Turing. El [[paradigma]] d'esti conxuntu de funciones representar la función qu'establez "si dada una Máquina de Turing, ésta produz un resultáu o, otra manera, quédase calculando indefinidamente". Esta función, conocida col nome de [[Problema de parada]] (Halting Problem), va ser pieza fundamental pa demostrar la incomputabilidad de ciertes funciones.

== Demostración de los teoremas ==
La demostración de los teoremas de incompletitud basar en tres conceptos:
#La numberación de Gödel, que dexa traducir les teoríes formales a operaciones d'[[aritmética]] pura.
#La potencia espresiva de les teoríes formales aritmétiques, que les sos espresiones recueyen diches operaciones.
#El [[lema diagonal]], que dexa que les fórmules sían autorreferentes.
L'enunciáu orixinal por cuenta de Gödel, que la so demostración esbozar nesta seición, ye más débil que'l presentáu enriba, yá qu'en llugar de la consistencia de la teoría ''T'' esíxese una propiedá más fuerte, la [[ω-consistencia]].
{{definición|1=Una teoría aritmética ye '''ω-inconsistente''' si, pa dalgún de los sos teoremas formales de la forma {{math|{{unicode|∃}}''x'', ''φ''(''x'')}}, puede refutarse cualquier casu particular, esto ye, puede probase {{math|¬''φ''([''n''])}}, pa cada numberal {{math|[''n'']}}. Una teoría que nun ye ω-inconsistente dizse '''ω-consistente'''.
}}
(Los '''numberales''' {{math|[''n'']}} son los símbolos qu'utilice'l llinguaxe de la teoría pa especificar los númberos naturales concretos. Nel exemplu de l'aritmética de Peano na seición siguiente, los numberales son los símbolos daos por: {{math|[0] ≡ 0}}, {{math|[1] ≡ S0}}, {{math|[2] ≡ SS0}}, etc.) 
La consistencia implica la consistencia (pero non al aviesu). L'enunciáu fuerte», nel que namái se riquir la consistencia de la teoría foi probáu por J. B. Rosser por aciu un métodu bien similar.

=== Numberación de Gödel ===
{{AP|Numberación de Gödel}}
La numberación de Gödel ye una ferramienta que dexa rellacionar les teoríes formales cola [[aritmética]]. El [[llinguaxe formal|llinguaxe]] d'una [[lóxica de primer orde|teoría formal de primer orde]] ta compuestu por una cantidá —a lo sumo— [[conxuntu numerable|numerable]] de signos, como por casu:

:{{math|{{unicode|∃}}}} , {{math|{{unicode|⇒}}}} , {{math|¬}} , {{math|{{!}}}}, {{math|{{=}}}}, {{math|''x''}} , {{math|''y''}} , {{math|''z''}} , ... , {{math|0}} , {{math|+}} , {{math|×}} , {{math|S}} 

nel casu del llinguaxe de l'[[aritmética de Peano]], onde amás de los símbolos lóxicos y les variables, apaecen dellos símbolos adicionales pa la arimética (onde {{math|S}} ye'l símbolu pa denotar «el númberu siguiente a»). Tamién el conxuntu de toles cadenes (socesiones finitas de signos) ye numerable, según el conxuntu de les socesiones finitas de cadenes. 

Una '''numberación de Gödel''' ye una asignación d'un únicu [[númberu natural]] pa cada elementu de cada unu d'estos trés conxuntos: signos, cadenes de signos y socesiones de cadenes.

{{demostración|plegada=non|títulu=Exemplu|1=Una posible codificación pa los signos, cadenes y socesiones de cadenes ye la siguiente. Pa los signos adóptase:
 
: «{{math|{{unicode|∃}}}}» → 10 , «{{math|{{unicode|⇒}}}}» → 11 , «{{math|¬}}» → 12 , «{{math|{{!}}}}» → 13 , «{{math|{{=}}}}» → 14 , «{{math|0}}» → 15 , :
«{{math|S}}» → 16 , «{{math|+}}» → 17 , «{{math|×}}» → 18 , «{{math|''x''}}» → 20 , «{{math|''y''}}» → 2000 , «{{math|''z''}}» → 200000 , ...

Dada una cadena de signos, adóptase'l criteriu de «apilar» los númberos de Gödel de los sos signos, con un 77 inicial pa indicar que se trata d'una cadena:

: «{{math|1=''x'' + [5] = 0}}» tornar en: 77-20-17-16-16-16-16-16-15-14-15, esto ye, en 7720171616161616151415

Pa una socesión de cadenes de signos, puede adoptase un conveniu similar, con un 88 inicial, pa indicar que se trata d'una socesión:

: La socesión «{{math|1=0 = 1}}, {{math|1=''y'' + 1 = 0}}» convertir en: 88-77-15-14-16-15-77-2000-17-16-15-14-15, ye dicir en: 8877151416157720001716151415
}}

Yá que la manipulación d'estos signos, cadenes y socesiones puede traducise en manipulación d'unos ciertos númberos, tantu la sintaxis qu'estrema les cadenes de signos «con sentíu» —les fórmules− como'l cálculu deductivu qu'estrema les socesiones de cadenes «que demuestren daqué» —les demostraciones— vense traducíes a operaciones ''aritmétiques''. Esto ye, esisten una serie de [[rellación matemática|rellaciones]] y [[función matemática|funciones]] aritmétiques que se correspuenden coles regles sintáctiques y del cálculu deductivu, como por casu:

:{{math|Sig ''x''}} : {{math|''x''}} ye (el númberu de Gödel de) un signu :{{math|Cad''x''}} : {{math|''x''}} ye (el númberu de Gödel de) una cadena (de signos)
:(Omítese «el númberu de Gödel de» d'equí p'arriba)
:{{math|Suc ''x''}} : {{math|''x''}} ye una socesión (de cadenes)
:{{math|Form ''x''}} : la cadena {{math|''x''}} ye una fórmula :{{math|Ax''x''}} : la fórmula {{math|''x''}} ye un axoma :{{math|Cons(''x'',''y'', ''z'')}}: «{{math|''x''}} ye una fórmula consecuencia inmediata de les fórmules {{math|''y''}} y {{math|''z''}}»
:{{math|Dem(''x'', ''y'')}}: «la socesión {{math|''x''}} ye una demostración de la fórmula {{math|''y''}}»

La forma precisa d'estes funciones y rellaciones ye aballadora y depende del criteriu que s'escoyera pa efectuar la numberación de Gödel. En particular la rellación {{math|Ax ''x''}} hai de construyise teniendo en cuenta un ciertu conxuntu d'axomes concretu, depués la rellación {{math|Dem}} fai referencia a una teoría concreta que nun s'especificó.

{{demostración|títulu=Exemplu|plegada=non|1=Ye senciellu entender agora cómo tienen de definise dalgunes d'estes rellaciones según la numberación de Gödel amosada antes:

:{{math|Sig ''x''}} {{math|≡}} {{math|''x''}} ta ente 10 y 18 (dambos inclusive), o ye de la forma 20·100<sup>''i''</sup> (con ''i'' &gt; 1)
:{{math|Cad ''x''}} {{math|≡}} En base 10, {{math|''x''}} ye de la forma {{math|88''n''(s<sub>1</sub>)...''n''(s<sub>k</sub>)}}, onde cada {{math|''n''(s<sub>i</sub>)}} representa les cifres d'un númberu tal que {{math|Sig ''n''(s<sub>i</sub>)}} ye ciertu :{{math|Suc
''x''}} {{math|≡}} En base 10, {{math|''x''}} ye de la forma {{math|77''n''(π<sub>1</sub>)...π(s<sub>k</sub>)}} onde cada {{math|''n''(π<sub>i</sub>)}} representa les cifres d'un númberu tal que {{math|Cad ''n''(π<sub>i</sub>)}} ye ciertu }}.


=== Expresabilidad. Recursividad ===
{{AP|Función recursiva}}
Por aciu la numberación de Gödel, ye posible «traducir» los signos y regles d'una teoría formal {{math|''T''}} en númberos y operaciones aritmétiques. Ye posible dir más allá, yá que {{math|''T''}} ye una teoría ''aritmética'' y puédense «recodificar» les mentaes operaciones por aciu el llinguaxe formal de {{math|''T''}}, al igual que puede faese con otres funciones y rellaciones aritmétiques como por casu:

:La función «multiplicar por 2» ta representada pola fórmula: {{math|1=''y'' = [2] × ''x''}}
:La rellación d'orde {{math|''x'' ≤ ''y''}}, puede espresase por aciu: {{math|1={{unicode|∃}}''z'', ''z'' + ''x'' = ''y''}} 
:La rellación «{{math|''x''}} y {{math|''y''}} son [[coprimos|primos ente sigo]]» puede espresase como: {{math|1={{unicode|∀}}''z'', ''z'' ≠ [1] {{unicode|∧}} {{unicode|∃}}''w'', ''x'' = ''z'' × ''w'' {{unicode|⇒}} ¬{{unicode|∃}}''o'', ''y'' = ''z'' × ''o''}}.

Caúna d'estes rellaciones ye ''espresada'' pola so fórmula correspondiente, nel sentíu de que si dos númberos tán rellacionaos, puede demostrase la espresión formal correspondiente; y cuando nun lo tán, puede refutarse.<ref>De manera rigorosa, dizse qu'una rellación {{math|''R''(''n''<sub>1</sub>, ..., ''n''<sub>k</sub>)}} ye '''expresable''' nuna teoría formal aritmética si esiste una fórmula {{math|''φ''(''x''<sub>1</sub>,..., ''x''<sub>k</sub>)}} de forma que si la rellación {{math|''R''(''n''<sub>1</sub>, ..., ''n''<sub>k</sub>)}} cumplir pa unos ciertos númberos {{math|''n''<sub>1</sub>, ..., ''n''<sub>k</sub>}} entós puede demostrase la fórmula {{math|''φ''([''n''<sub>1</sub>],..., [''n''<sub>k</sub>])}}; y si la rellación nun se cumple, entós dicha fórmula puede refutarse. Vease {{Harvsp|Ivorra||loc=§6.3}} o {{Harvsp|Boolos|Burgess|Jeffrey|2007|loc=§16}} (onde se denomina ''definability'').</ref> Por casu:

:Pa cada enteru {{math|''n''}}, tiense que si {{math|''n''}} ye par puede probase la espresión formal {{math|1={{unicode|∃}}''x'', [''n''] = [2] × ''x''}}; y si ye impar, puede refutarse dicha fórmula.
:Pa cada par d'enteros {{math|''m''}} y {{math|''n''}}, si tiense {{math|''m'' ≤ ''n''}} puede demostrase la fórmula {{math|1={{unicode|∃}}''z'', ''z'' + [''m''] = [''n'']}}; cuando {{math|''m'' &gt; ''n''}}, puede refutarse dicha espresión.

Que les rellaciones presentaes na seición anterior —como {{math|Dem}}— sían expresables, implica qu'una teoría formal aritmética ye lo suficientemente potente como pa «falar» de les carauterístiques d'una teoría formal arbitraria ysobremanera, de sigo mesma.

Probar que toes estes rellaciones y funciones son expresables ye senciellu si son [[función recursiva|''recursivas'']], esto ye, si pueden calculase o verificase por aciu un [[algoritmu]], yá que puede demostrase que toa rellación recursiva ye expresable nuna teoría aritmética. Les teoríes formales pa les qu'esto ye posible —asignar los númberos de Gödel de manera qu'estremar los signos, cadenes, socesiones, fórmules, consecuencies y axomes, puede llevase a cabu con un algoritmu— son les llamaes teoríes '''recursivas''', y por ello esta carauterística asumir como hipótesis nos teoremas de incompletitud.

=== Diagonalización ===
Pa construyir la sentencia autorreferente {{math|''G''}} hai d'escurrise una manera por que una fórmula fale de les propiedaes del so númberu de Gödel correspondiente. Esto hai de faese de manera indireuta, yá que dada una fórmula {{math|''φ''}} con númberu de Gödel {{math|''n''}}, otra fórmula que «fale» de {{math|''φ''}} por aciu el numberal {{math|[''n'']}} polo xeneral va tener un númberu de Gödel mayor que {{math|''n''}}, y por tanto nun puede ser la mesma {{math|''φ''}}. Esto consíguese por aciu el llamáu '''lema diagonal'''.
{{teorema|1=Nuna teoría aritmética recursiva, dada una fórmula {{math|''φ''(''x'')}} esiste una sentencia {{math|''ψ''}} con númberu de Gödel {{math|''n''}} tal que puede demostrase {{math|''ψ'' {{unicode|⇔}} ''φ''([''n''])}}.}}
A última hora, dada una propiedá cualesquier {{math|''φ''(''x'')}} esiste una sentencia {{math|''ψ''}} qu'afirma «el mio númberu de Gödel cumple la propiedá {{math|''φ''}}».

=== Demostración del primer teorema ===
Sía una teoría formal aritmética y recursiva {{math|''T''}} ω-consistente. Sía la fórmula {{math|¬{{unicode|∃}}''z'', DEM(''z'', ''x'')}}, onde {{math|DEM}} ye la fórmula qu'espresa la rellación numbérica {{math|Dem}} —relativa a la teoría formal {{math|''T''}}—. Pol lema de diagonalización esiste una sentencia {{math|''G''}} con númberu de Gödel {{math|''g''}}, pa la que se demuestra {{math|''G'' {{unicode|⇔}} ¬{{unicode|∃}}''z'', DEM(''z'', [''g''])}}, esto ye, qu'afirma «nengún númberu codifica una demostración (en {{math|''T''}}) de la fórmula representada por {{math|''g''}}», o otra manera, «nun soi demostrable (en {{math|''T''}})». La negación d'esta sentencia, {{math|¬''G''}}, ye equivalente a {{math|{{unicode|∃}}''z'', DEM(''z'', [''g''])}}, o «la mio negación ye demostrable (en {{math|''T''}})».

Supóngase entós que {{math|''G''}} puede demostrase. Entós esiste un númberu {{math|''n''}} que cumple {{math|Dem(''n'', ''g'')}}, y en {{math|''T''}} puede probase entós {{math|DEM([''n''], [''g''])}}, lo cual implica formalmente {{math|¬''G''}}; y esto ye imposible si {{math|''T''}} ye consistente. Por tantu nun esiste una demostración de {{math|''G''}}, y cumplir {{math|¬Dem(''n'', ''g'')}} pa tolos númberos {{math|''n''}}, lo cual resulta nun númberu infinitu de teoremas formales {{math|¬DEM([''n''], [''g''])}} pa cada numberal {{math|[''n'']}}. Como {{math|''T''}} ye ω-consistente, nun puede asoceder entós que {{math|{{unicode|∃}}''x'', DEM(''x'', [''g''])}} sía un teorema, polo que {{math|¬''G''}} ye indemostrable, y {{math|''T''}} ye indecidible.

=== Demostración del segundu teorema ===
La demostración del segundu teorema de incompletitud rique d'un fechu téunicu que Gödel orixinalmente nun probó. Sía una teoría {{math|''T''}} nes condiciones anteriores y sía la fórmula {{math|Consis ''T'' ≡ ¬{{unicode|∃}}''z'', DEM(''z'', [''k''])}}, onde {{math|''k''}} ye'l númberu de Gödel de la sentencia {{math|1=0 = 1}}. {{math|Consis ''T''}} afirma que la teoría {{math|''T''}} ye consistente (pos dexa daqué ensin demostrar). La versión formal (de la primer parte) del primer teorema de incompletitud puede espresase como {{math|Consis ''T'' {{unicode|⇒}} ¬{{unicode|∃}}''y'', DEM(''y'', [''g''])}} y esto ye equivalente precisamente a {{math|Consis ''T'' {{unicode|⇒}} ''G''}}. De cuenta que, de poder probar formalmente esta sentencia, {{math|Consis ''T''}} sería indemostrable yá que se tendría entós una demostración de {{math|''G''}}, en contradicción col primer teorema.

El fechu téunicu que se precisa ye precisamente una prueba de que la demostración del primer teorema de incompletitud puede «traducise» nuna demostración formal de la sentencia {{math|Consis ''T'' {{unicode|⇒}} ¬{{unicode|∃}}''y'', DEM(''y'', [''g''])}}. Esto ye posible en toa teoría aritmética recursiva, yá que verifiquen unes ciertes ''condiciones de demostrabilidad''.

== Ver tamién ==
* [[Consistencia lóxica]]
* [[Autorreferencia]]
* [[Loxicismu]]
* [[Teorema de Löb]]
* [[Teorema de completitud de Gödel]]
* [[Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemes rellacionaos]]

== Referencies ==
{{llistaref|2}}

== Bibliografía ==
*{{cita llibru|títulu=Handbook of mathematical logic|apellíos=Barwise|nome=Jon|editorial=Elsevier|añu=1989|isbn=9780444863881|idioma=inglés}}
*{{cita llibru|títulu=Computability and logic|idioma=inglés|nome=George|apellíos=Boolos|nome2=John P.|apellíos2=Burgess|nome3=Richard C.|apellíos3=Jeffrey|editorial=[[Cambridge University Press]]|añu=2007|isbn=9780521701464}}.
*{{cita llibru|nome=Norbert|apellíos=Domeisen|títulu=Logik der Antinomien|editor=Peter Lang|añu=1990|isbn=3-261-04214-1|url=http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?nome=1&maxdocs=3&type=html&an=0724.03003&formatu=complete Zentralblatt MATH|idioma=alemán}}
* {{cita publicación|nome=Kurt|apellíos=Gödel|títulu=Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I|doi=10.1007/BF01700692|publicación=Monatshefte für Mathematik und Physik|volume=38|añu=1931|páxines=173-198|idioma=alemán}} 
:Traducíu al castellán en: 
*{{cita llibru|nome=Kurt|apellíos=Gödel|títulu=Obres completes|máscaraautor=3|editor=Jesús Mosterín|editorial=Alianza Editorial|añu=1981|isbn=84-206-2286-9}}
*{{cita llibru|nome=Kurt|apellíos=Gödel|máscaraautor=3|títulu=Sobre proposiciones formalmente indecidibles de los Principia Mathematica y sistemes allegaos|editorial=KRK Ediciones|añu=2006|isbn=978-84-96476-95-0}}
*{{cita llibru|apellíos=Hofstadter|nome=Douglas R.|añu=1989|títulu=[[Gödel, Escher, Bach]]|editorial=Tusquets editores|isbn=84-7223-459-2}}
*{{cita llibru|nome2=Ernest|apellíos2=Nagel|nome3=James Roy|apellíos3=Newman|nome=Douglas R.|apellíos=Hofstadter|títulu=Gödel's Proof|añu=2002|isbn=0-8147-5816-9|idioma=inglés|editorial=NYU Press}}
*{{Enllaz rotu|1=Lóxica y teoría de conxuntos |2=http://www.uv.es/ivorra/Llibros/Logica.pdf |date=August 2024 |bot=InternetArchiveBot }}.
*{{cita llibru|nome=Guillermo|apellíu=Martínez|enllace-autor=Guillermo Martinez (escritor)|editorial=Seix Barral|títulu=Gödel pa toos añu=2009|isbn=978-950-731-605-0}}
* {{cita publicación|nome=B.|apellíos=Rosser|títulu=Extensions of some theorems of Gödel and Church|publicación=Journal of Symbolic Logic|volume=1|añu=1936|páxines=87-91|url=http://www.jstor.org/stable/2269028|númberu=3}}
*{{cita llibru|nome=Raymond|apellíos=Smullyan|títulu=Gödel's Incompleteness Theorems|editorial=[[Oxford University Press]]|añu=1992|isbn=0-19-504672-2|idioma=inglés}}

== Enllaces esternos ==
* '''Refutaciones a la interpretación de Penrose:'''
** ''[http://cs.nyu.edu/cs/faculty/davism/penrose.ps Is Mathematical Insight Algorithmic?]''
** ''[http://cs.nyu.edu/cs/faculty/davism/penrose2.ps How Subtle is Gödel's Theorem]''
** ''[http://citeseer.ist.psu.edu/laforte98why.html Why Gödel's Theorem Cannot Refute Computationalism]''
** ''[http://citeseer.ist.psu.edu/106920.html Human and Machine Understanding of Mathematics]''
* Ignacio Jané, ''[http://divulgamat.ehu.es/weborriak/historia/Gaceta/historia93b.pdf La obra de Gödel en lóxica matemática y teoría de conxuntos] {{Webarchive|url=https://web.archive.org/web/20070611203750/http://divulgamat.ehu.es/weborriak/historia/Gaceta/historia93b.pdf |date=2007-06-11 }}'' Una introducción sintética y histórica que respeta los conceutos orixinales, evitando tracamundios. 
* [https://web.archive.org/web/20090617103727/http://redalyc.uaemex.mx/redalyc/pdf/294/29406405.pdf Reseña en castellán] de [[Torkel Franzén]], ''Gödel's theorem : an incomplete guide to its use and abuse''. El llibru de Franzen, de 2005, ta siendo bien citáu como obra d'interés pa introducir al verdaderu sentíu de los teoremas de Gödel y prevenir frente a la so aplicación inxustificada en campos non matemáticos.
* Kārlis Podnieks: ''Around Goedel's Theorem'', http://www.ltn.lv/~podnieks/gt.html
* [http://aleph0.clarku.edu/~djoyce/hilbert/problems.html#prob2 Hilbert's second problem]
* {{Cita publicación
 |last=Gödel |first=K. |authorlink=Kurt Gödel
 |añu=1929 
 |títulu=Über die Vollständigkeit des Logikkalküls
 |version=Doctoral dissertation |publisher=University Of Vienna. 
}} Primer demostración del teorema de completitud.
* {{cita publicación
 |apellíu=Gödel |nome=K. |enllaceautor=Kurt Gödel
 |títulu=Die Vollständigkeit der Axiome des logischen Funktionenkalküls
 |idioma=alemán
 |publicación=Monatshefte für Mathematik
 |volume=37 |páxines=349–360 |añu=1930
 |doi=10.1007/BF01696781
 |id={{JFM|56.0046.04}}
}}





{{Tradubot|Teoremas de incompletitud de Gödel}}

{{control d'autoridaes}}
[[Categoría:Teoremas de lóxica|Incompletitud de Gödel]]
[[Categoría:Metalógica]]
[[Categoría:1931]]
[[Categoría:Wikipedia:Correxir/Revisar títulu]]