Diferencies ente revisiones de «Teoremas de incompletitud de Gödel»

m
"rellación" en cuenta de "relación" (que nun ta nel DALLA)
m (apostrofación)
m ("rellación" en cuenta de "relación" (que nun ta nel DALLA))
*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 primera 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 relacionesrellaciones; 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 ==
}}
 
Cuidao 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 [[relaciónrellación matemática|relacionesrellaciones]] 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)
:{{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 relacionesrellaciones ye aballadora y depende del criteriu que s'escoyera pa efectuar la numberación de Gödel. En particular la relaciónrellación {{math|Ax ''x''}} hai de construyise teniendo en cuenta un ciertu conxuntu d'axomes concretu, depués la relaciónrellación {{math|Dem}} fai referencia a una teoría concreta que nun s'especificó.
 
{{demostración|título=Exemplu|plegada=non|1=Ye senciellu entender agora cómo tienen de definise dalgunes d'estes relacionesrellaciones 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)
=== 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 relacionesrellaciones aritmétiques como por casu:
 
:La función «multiplicar por 2» ta representada pola fórmula: {{math|1=''y'' = [2] × ''x''}}
:La relaciónrellación d'orde {{math|''x'' ≤ ''y''}}, puede espresase por aciu: {{math|1={{unicode|∃}}''z'', ''z'' + ''x'' = ''y''}}
:La relaciónrellació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 relacionesrellaciones 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 relaciónrellació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 relaciónrellació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 relaciónrellació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 relacionesrellaciones 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 relacionesrellaciones 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 relaciónrellació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 pollo esta carauterística asumir como hipótesis nos teoremas de incompletitud.
 
=== Diagonalización ===
 
=== Demostración del primera 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 relaciónrellació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.