Recorrido por las diferentes versiones del teorema de incompletitud de Kurt Gödel
Abstract
Departamento de Filosofía (Filosofía, Lógica y Filosofía de la Ciencia, Teoría e Historia de la Educación, Filosofía Moral, Estética y Teoría de las Artes)
Full text
RECORRIDO POR LAS DIFERENTES VERSIONES DEL TEOREMA DE INCOMPLETITUD DE KURT GÖDEL AUTORA: María Pérez Calvo TUTOR: Juan Barba Escribá Grado en Filosofía Facultad de Filosofía y Letras Universidad de Valladolid Julio, 2019
Resumen: en el presente trabajo se ofrece un recorrido explicativo por las diferentes versiones del Teorema de Incompletitud presentado por el lógico Kurt Gödel. La primera será la más sencilla, la cual se demuestra a través del teorema propuesto por Tarski. En segundo lugar veremos una demostración de incompletitud para un sistema aritmético básico con suma, multiplicación y exponenciación, para posteriormente demostrar que es posible llevar a cabo la demostración en un sistema equivalente que prescinde de la exponenciación. Mostraremos también la demostración de Gödel para los VLVWHPDV TXH pO GHQRPLQDUi Ȧ-consistentes y finalizaremos con la demostración de incompletitud que ofrece Rosser a través de una nueva fórmula diferente a la empleada por Gödel. Palabras clave: Kurt Gödel, Incompletitud, Lógica, Sistema Incompleto, Filosofía, Tarski, Rosser.
Índice Introducción 7 1. Primeras versiones abstractas del teorema 9 2. Una aplicación más concreta: el lenguaje LE16 3. Demostración de incompletitud del Sistema P.E. 24 4. Demostración de incompletitud del Sistema P.A. 31 5. 7HRUHPDGH*|GHO\Ȧ-consistencia 40 6. El Teorema de Incompletitud según Rosser 53 Comentarios finales 58 Bibliografía 61
María Pérez Calvo Universidad de Valladolid 7 Introducción El Teorema de Incompletitud, publicado en 1931, propuesto por el lógico, matemático y filósofo austríaco Kurt Gödel (1906 – 1978) ha tenido una relevancia fundamental en la lógica del s. XX. Dada la popularidad del resultado y la existencia de diferentes versiones del teorema es frecuente encontrar referencias imprecisas, inexactas o directamente erróneas. Durante el desarrollo de este trabajo vamos a ir recorriendo las diferentes versiones de este teorema, desde la más sencilla de demostrar, a través del teorema propuesto por el lógico polaco Alfred Tarski (1901 – 1983), hasta la versión ofrecida en 1936 por el lógico estadounidense John Barkley Rosser (1907 – 1989). Además, iremos explicando cada una de las demostraciones paso a paso con la intención de esclarecer los procesos que nos llevan a afirmar la incompletitud de los sistemas aritméticos. Las diferentes versiones de las que iremos hablando se irán sucediendo desde las más débiles y sencillas de entender, en las que asumimos condiciones más fuertes, hasta versiones más fuertes en las que asumimos condiciones cada vez más débiles, pero que a su vez son más complejas de entender. En el primer apartado vamos a ofrecer una primera idea de los elementos básicos que necesitamos para posteriormente aplicarlos a los casos concretos que nos lleven hasta las diferentes versiones de la demostración de incompletitud de los sistemas. Además, veremos dos versiones abstractas de los dos primeros teoremas, el propuesto por Tarski y uno que combina las ideas de Tarski con las propuestas por Gödel. En el segundo apartado comenzamos a aplicar estos elementos básicos a un caso concreto, el del lenguaje LE, un lenguaje de primer orden estándar pensado para la aritmética, lenguaje para el que estableceremos una formulación precisa del Teorema de Tarski. Los dos siguientes apartados consistirán en la demostración de incompletitud del sistema P.E, es decir, un sistema conformado por la Aritmética de Peano con el añadido de unos esquemas de exponenciación. Para este sistema veremos una formulación concreta del Teorema de Gödel-Tarski. Posteriormente demostramos que la exponenciación es superflua y que la Aritmética de Peano solo con la suma y la multiplicación (sistema al que nos referiremos como P.A.) es equivalente e igualmente
María Pérez Calvo Universidad de Valladolid 8 válida para esta demostración. Veremos entonces la demostración de la incompletitud de este sistema a través del teorema genuinamente propuesto por Gödel, el Teorema G. En HVWHVHHPSOHDUiODFRQVLVWHQFLDVLPSOHGHORVVLVWHPDV\HOFRQFHSWRGHODȦ-consistencia de estos introducida por Gödel. Demostraremos la incompletitud de este sistema a partir de la demostración de incompletitud de su subsistema más básico. Por último, en el sexto apartado, veremos la versión que ofrece Rosser de la demostración de incompletitud empleando una sentencia diferente a la utilizada por Gödel que, pese a ser menos intuitiva, nos ofrece la demostración del Teorema R, de mayor fuerza que el Teorema G. En este caso únicamente se asumirá la consistencia VLPSOH GH ORV VLVWHPDV GHMDQGR WDPELpQ GH ODGR OD Ȧ-consistencia necesaria en la demostración de Gödel. Además, realizaremos una breve comparativa de ambas sentencias. Finaliza el trabajo un apartado con ciertas consideraciones finales que ayudan a la comprensión general de todo lo explicado.
María Pérez Calvo Universidad de Valladolid 9 1. Primeras versiones abstractas del teorema Para empezar vamos a ofrecer una versión abstracta de lo que vamos a ir elaborando posteriormente en el trabajo. Vamos a describir unos elementos básicos con los que luego estructurar los razonamientos de Gödel. Cada uno de los lenguajes L a los que podemos aplicar el argumento de Gödel contiene al menos los siguientes elementos: xExpresiones: en primer lugar, un conjunto enumerable E, cuyos elementos se denominan expresiones de L xSentencias: de este conjunto de expresiones obtenemos un subconjunto S formado por las sentencias de L. Dentro de las sentencias vamos a resaltar: oUn subconjunto Pde Sformado por las sentencias demostrables de L. oUn subconjunto Rde Sformado por las sentencias refutables de L. xPredicados: un conjunto Hde expresiones integrado por los llamados predicados de L. Informalmente, cada uno de ellos representa o sería el nombre de un conjunto de números naturales. xUna función que se encarga de asignar a cada expresión Ey a cada número natural nuna expresión E(n). Lo que nos interesa de esta función es que tiene que cumplir la condición de que para todo predicado Hy todo número natural n, la expresión H(n) sea una sentencia. ¿Por qué nos interesa? De esta forma vamos a poder tener una sentencia que predica cualquier predicado de cualquier número. Lo explicamos de forma tan general porque cuando lo aritmetizamos tenemos una función binaria con un número que representa una expresión y un número que representa a un número, y para que esto valga siempre, el argumento de expresión tiene que poder ser cualquier número. xSentencias verdaderas: en la primera versión, vía Teorema de Tarski, se añade este elemento, el conjunto Tde sentencias compuesto por las sentencias verdaderas de L.
María Pérez Calvo Universidad de Valladolid 16 2. Una aplicación más concreta: el lenguaje LE Vamos a empezar a dar contenido a lo visto de forma abstracta a través de lenguajes y sistemas aritméticos concretos. Hasta ahora hemos hablado de características generales de los distintos lenguajes a los cuales se aplican estos diferentes argumentos lo hacíamos desde una perspectiva muy general. Ahora vamos a ver el primer ejemplo particular de un lenguaje que encaja con esa descripción abstracta. Vamos a definir lenguaje de primer orden estándar pensado para la aritmética, basado en la suma, la multiplicación y la exponenciación (LE). Este lenguaje lo formulamos usando únicamente un alfabeto finito formado por los siguientes 12 símbolos: 0 ’ ( ) f,v~ـ=; y un último elemento que utilizamos como separador: #. xCon estos símbolos construimos los numerales, representados por las expresiones 0, 0’, 0’’, 0’’’... y que utilizaremos como nombres de los números naturales 0, 1, 2, 3… respectivamente. xLa virgulilla tiene la función de representar a la función de sucesor. xDe igual forma que necesitamos los numerales para dar nombre a los números naturales, necesitamos nombres para las operaciones de suma, multiplicación y exponenciación, y para eso utilizaremos las expresiones f,,f,, yf,,, respectivamente. Estas tres expresiones se abrevian con H[SUHVLRQHVPiVIDPLOLDUHVÂ\E. xTanto ~como ـdesempeñan la misma función que en la lógica proposicional, la negación el primero y la implicación material el segundo, de igual forma que también aparece realizando la labor de cuantificador universal, pero únicamente cuantificará números naturales, no conjuntos ni relaciones. xEl símbolo = también desempeña su labor usual como designador de la relación de identidad, igual que con la relación “menor o igual que”. xPor último, v1, v2,v3…las expresiones denominadas variables, se designarán por las expresiones respectivas (v,), (v,,), (v,,,)… En este lenguaje, una expresión se denomina término si se sigue como consecuencia de las dos siguientes reglas: toda variable y todo numeral es un término; si
María Pérez Calvo Universidad de Valladolid 17 tenemos dos términos t1yt2, entonces también se consideran términos (t1+t2), (t1Ât2), (t1Et2) y t1’. Si el término no contiene variables se dice que es un término cerrado o constante. Dados dos términos cualesquiera también obtenemos las dos expresiones t1=t2 yt1t2, denominadas fórmulas atómicas. El conjunto de todas las fórmulas se obtiene entonces de forma inductiva siguiendo las siguientes reglas: toda fórmula atómica es una fórmula; si FyGson fórmulas, entonces ~Fy (FـG) son fórmulas, y para toda variable vi, también es una fórmula la expresión viF. Las variables pueden aparecer en las fórmulas de LEo bien ligadas, o bien libres. Para cualquier término t, todas las apariciones de vien tse denominan apariciones libres. También son apariciones libres todas las apariciones de vies cualquier fórmula atómica A. Para cualesquiera fórmulas FyG, las apariciones libres de vien (FـG) son la unión de las apariciones libres en Fy en G, mientras que las de ~Fson las mismas que las de F. Lo contrario de las apariciones libres son las apariciones ligadas, y esto es lo que ocurre con todas las apariciones de vien viF. Para cualquier ji, las apariciones libres de vien viFson aquellas que aparecen en F. Cuando hablamos de las sentencias que conforman LE, nos referimos a cualquier fórmula en la que no hay ninguna variable libre, también llamada fórmula cerrada. Como se ha dicho más arriba, llamamos numerales a los nombres que utilizamos para designar a los números naturales. Para cualquier número natural n, el numeral que designa nserá ݊ത, símbolo que abrevia el 0 seguido de napariciones del símbolo ’ según los 13 símbolos que conforman LE. Escribimos F(ݒభ,…, ݒ) para designar cualquier fórmula en la que ݒభ, …, ݒsean las únicas variables libres, ypara cualesquiera números k1, …, kn, escribimos F(݇ ത1, …, ݇ തn) para representar el resultado de sustituir cada aparición libre de ݒభ, …, ݒpor ݇ ത1, …, ݇ തnrespectivamente. F(݇ ത1, …, ݇ തn) se denominará instancia de F(ݒభ, …, ݒ). Esta última puede denominarse regular siempre que i1= 1, …, in=n, es decir, si para cada i, si vies una variable libre de F, entonces para cualquier ji,vj también es una variable libre de F. Si fuese regular, se escribiría de la siguiente forma: F(v1, …, vn). Una vez definidas inductivamente las fórmulas, podemos definir el grado de una fórmula. Con él nos referimos al número de veces que aparecen los conectores lógicos ~ yـy el cuantificador en la fórmula. De esta forma podemos decir que las fórmulas atómicas son de grado 0, y que para dos fórmulas cualesquiera FyGde grados
María Pérez Calvo Universidad de Valladolid 18 respectivos d1yd2, la fórmula ~Fserá de grado d1+ 1; la fórmula (F1ـF2) es de grado d1+d2+ 1; y para cualquier variable vi, la fórmula viF1será de grado d1+ 1. Su papel es muy relevante en tanto que el principio de inducción matemática consiste en mostrar que si una propiedad la cumplen todas las fórmulas atómicas y además, si la cumplen las fórmulas de grado n, también la cumplen las de grado n+ 1, entonces la cumplen todas las fórmulas. ¿Cómo definimos la verdad de las expresiones de este lenguaje? El concepto de verdad desempeña una función principal en la versión del teorema Gödel-Tarski, no así en otras versiones del teorema que veremos. Definimos inductivamente el conjunto de las sentencias verdaderas mediante las siguientes 4 condiciones: T0: en primer lugar, una sentencia atómica c1=c2(donde ambos son términos constantes, es decir, no tienen variables) es verdadera syss ambos términos designan al mismo número natural. Segundo, la sentencia atómica c1c2es verdadera syss el número que designa c1es menor o igual que el designado por c2. T1: una sentencia de forma ~Xes verdadera syss Xno es verdadera. T2: una sentencia condicional XـYes verdadera syss, o bien Xno es verdadera, o bien tanto Xcomo Yson verdaderas. T3: una sentencia universal viFes verdadera syss para todo número n, la sentencia F(݊ത) es verdadera. La noción de verdad es aplicable a las fórmulas cerradas, en el caso de las fórmulas abiertas como F(ݒభ, …, ݒೖ) hablamos de corrección. La fórmula se considera correcta si para todos los números n1, …, nkla sentencia F(݊ത1, …, ݊തk) es verdadera. Diremos de dos sentencias que son equivalentes cuando ambas son verdaderas o ambas son falsas. En el caso de dos fórmulas abiertas F(ݒభ, …, ݒೖ) y G(ݒభ, …, ݒೖ) con las mismas variables, diremos que son equivalentes cuando syss para todos los números n1, …, nk, las sentencias F(݊ത1, …, ݊തk) y G(݊ത1, …, ݊തk) son equivalentes. Para cualquier fórmula F(v1), donde v1es la única variable libre, F(v1) expresa el conjunto Asyss para todos los números n,F(݊തHVYHUGDGļnאA. En el caso de una fórmula regular F(v1, …, vn), esta expresa la relación R(x1, …, xn) syss para todos los números k1, …, kn, se cumple la siguiente condición: F(݇ ത1, …, ݇ തnHVYHUGDGļR(k1, …,
María Pérez Calvo Universidad de Valladolid 19 kn). Como vemos, conjuntos y relaciones se expresan a través de fórmulas. Esto nos lleva a diferenciar entre los conjuntos y relaciones Aritméticas, expresadas por alguna fórmula de LE, podemos caracterizarlos informalmente como aquellos definibles en lógica de SULPHURUGHQSRUÂ\E; y los conjuntos y relaciones aritméticas (conviene subrayar que la diferencia se encuentra en el uso de la mayúscula o la minúscula), expresadas por una fórmula de LE, pero en la que no aparece el símbolo exponencial E. Una función f(x1, …, xn), con n-tuplas de números naturales a números naturales, será Aritmética si la relación f(x1, …, xn) = yes Aritmética, es decir, syss hay una fórmula F(v1, …, vn,vn+1) tal que para todos los números x1, …, xney, la sentencia F(ݔҧ1, …, ݔҧn,ݕത) es verdad syss f(x1, …, xn) = y. En el caso de una propiedad P, de los números naturales, es Aritmética cuando el conjunto de números que tienen esa propiedad Pes Aritmética. Como ya habíamos dicho, queremos que el lenguaje hable sobre las expresiones del lenguaje. Para ello lo que hacemos es asignar números a las expresiones y conseguir reflejar las operaciones que hacemos con expresiones en operaciones aritméticas con números. Lo que hacemos es manipular símbolos, para lo que necesitamos tratar la idea de la yuxtaposición, la operación más básica que hacemos con expresiones, algo que aritméticamente es fácil de llevar a cabo yuxtaponiendo números mediante concatenación. La concatenación a la Base b emplea un sistema de numeración que sustituye al que emplea Gödel puesto que en él, el paralelo entre lo que hacemos con números y lo que hacemos con símbolos es más sencillo. Para cualquier número bYDPRVDGHILQLU una cierta función x*byllamada concatenación a la base b. Como introducción intuitiva a este concepto vamos a dar un ejemplo con dos números en base 10, el 19 y el 45. La \X[WDSRVLFLyQGHDPERVQ~PHURVVHUtDUHVXOWDGRGHÂ2+ 45. Para explicarlo de forma general es necesario que empecemos definiendo la base 10: para cualesquiera números myn,m*10 n=mÂl(n)+n, donde l(n) es la longitud de n. En el caso de que la base no fuera 10, sino base b, sería análogo. De esta forma, para cualquier número b 2, m*bn PÂ್ܾ()+n, donde lb(n) es la longitud de nescrita en notación de base b. Atendiendo a lo que acabamos de explicitar, para cada bODUHODFLyQx*by= zes Aritmética. La demostración consta de los siguientes pasos, partiendo de la premisa de que b
María Pérez Calvo Universidad de Valladolid 20 1. Tomamos Powb(x) como la condición de que xes una potencia de b. Esta condición es Aritmética, porque Powb(x) se cumple syss y(x=by). 2. La relación ್ܾ(ೣ)=y, entre xey, es equivalente a la condición de que (x= 0 רy=b)ש(x്0רs(x,y)), donde s(x,y) es la relación “yes la potencia menor de bmayor que x”. Esta condición también es Aritmética porque s(x,y) se cumple syss Powb(y)רx<yרz((Powb(z)רx<z)ـyz). 3. La relación xÂ್ܾ()+y=z, que es x*by=z, es la condición z1z2(್ܾ()=z1רxÂz1=z2רz2+y=z) Por tanto, la relación x*by=zes Aritmética. De esta demostración podemos concluir que, para cada n \FXDOTXLHUb la relación x1*bx2*b… *bxn=yes Aritmética. De forma inductiva demostramos este corolario: acabamos de demostrar esto mismo para n= 2, si suponemos que nes ahora un número igual o mayor que 2 tal que la relación x1*b… *bxn=yes Aritmética, entonces x1, *b… *bxn*bxn+1 =ysyss z(x1*b… *bxn=zרz*bxn+1 =y). Por tanto, la relación también es Aritmética. Las sentencias Aritméticas hablan acerca de números, no acerca de expresiones de LE. Mediante la asignación de números Gödel a las expresiones, permitimos a las sentencias hablar de manera indirecta acerca de expresiones hablando directamente de los números Gödel de estas. La numeración Gödel que nosotros vamos a emplear en esta explicación es la que emplea Smullyan (1992), que se basa en la idea de la propuesta por Quine (1940), que formuló su lenguaje en un alfabeto de 9 símbolos S1,S2, …, S9. De esta forma, para cada expresión compuesta ܵ, asigna el número Gödel que, escrito en notación base 10, corresponde a in. En el caso de nuestro LEcontamos con 13 símbolos, por lo que utilizaremos una notación base 13. La elección de Smullyan de la base 13, una base prima, tiene unas ventajas que veremos más adelante. x1 para 0. x0 para ’. x2 para (. x3 para ). x4 para f.
María Pérez Calvo Universidad de Valladolid 21 x5 para ,. x6 para v. x7 para ~. x8 para ـ. x9 para . xȘSDUD xİSDUD xįSDUD &RPRYHPRVXWLOL]DPRVȘ,İ\įFRPRORVGtJLWRV\HQEDVHCuando tenemos una cadena de estos símbolos, reemplazamos cada uno por su dígito correspondiente en base 13. Basándonos en esta idea, llamaremos expresión a cualquier cadena formada por estos 13 símbolos, o algunos de ellos, que no empiece por ’ (porque tendríamos el mismo número para ’, para ’’, para ’’’…), excepto que sea únicamente ’. Para cualesquiera expresiones ExyEy, la expresión ExEyconsiste en Exseguido de Ey.El número Gödel de esta expresión será x*13 y. Llegamos a lo que se conoce como el Teorema de Tarski. Tomamos Tcomo el conjunto de números Gödel de las sentencias verdaderas de LE, un conjunto perfectamente bien definido de números naturales, pero que, como vamos a demostrar, no es Aritmético. Como dijimos antes, llamamos sentencia Gödel para un conjunto de números A, a una sentencia Xsi, o bien Xes verdadera y su número Gödel se encuentra en A; o en cambio, Aes falsa y su número Gödel no se encuentra en A. Demostraremos que para cada conjunto Aritmético Aencontramos una sentencia Gödel. Dada una fórmula F(v1) con v1como la única variable libre, esto es, un predicado, la sentencia F(݊ത), la sentencia que predica el predicado de n, es equivalente a la sentencia v1(v1=݊തـF(v1)), que es la que aquí vamos a considerar como la diagonalización de F(v1), a la que de aquí en adelante vamos a referirnos como F[݊ത]. A partir de esto va a ser fácil mostrar que el número Gödel de esta sentencia es una función Aritmética del número Gödel de F(v1) y el número n. Para cualquier expresión E, fórmula o no fórmula, la expresión v1(v1=݊തـE), es decir, E[݊ത], es una expresión perfectamente bien definida. En el caso de que Esí que fuese una fórmula, entonces su equivalente E[݊ത] también lo es, aunque no necesariamente una sentencia. Si Efuese una fórmula con v1como la única variable, entonces por supuesto que E[݊ത] sería una sentencia. Para cualesquiera números
María Pérez Calvo Universidad de Valladolid 22 xey, por r(x,y) nos referimos al número Gödel de la expresión Ex[ݕത], donde Exes la expresión cuyo número Gödel es x. La función r(x,y) es Aritmética, y recibirá el nombre de función de representación de LE.Ex[ݕത] es la expresión v1(v1=ݕതـEx). Si kes el número Gödel de la expresión v1(v1=, y aplicamos el resto de los números Gödel de los distintos elementos que conforman la expresión, tendríamos lo siguiente: ݒ1(ݒ1 = ᇣ ᇧ ᇧ ᇤ ᇧ ᇧ ᇥ ݕത ณ ଵଷ ـณ ଼ ܧ௫ ด ௫ ) ณ ଷ Observamos que el número Gödel de Ex[ݕത]es k* 13y* 8 * x* 3, y por tanto, r(x, y) = k* 13y* 8 * x* 3. La relación r(x,y) = zes obviamente Aritmética. Tomamos ahora d(x) = r(x,x), siendo d(x) la llamada función diagonal, que será obviamente Aritmética, puesto que r(x,y) lo es. Para cualquier número n,d(n) es el número Gödel de En[݊ത]. Para cualquier conjunto de números A,A* será el conjunto de todos los ntal que d(n)אA. Por tanto, A* es el conjunto de todos los números xtal que y(d(x) = yרyאA). Ya que la función diagonal es Aritmética, existe una fórmula D(v1, v2) que expresa la relación d(x) = y. Ahora supongamos que F(v1) es una fórmula que expresa el conjunto A, entonces, A* se expresa por la fórmula v2(D(v1,v2)ـF(v2)). De esta manera hemos demostrado que, si Aes Aritmético, entonces A* también lo es. Así vemos que en este sistema se cumple la condición G1. La clase de conjuntos Aritméticos está cerrada sobre complementación porque si F(v1) expresa A, entonces su negación expresa el complementario de A, el conjunto ܣ ሚ. Vemos como también para este sistema se cumple G2. En este lenguaje se cumplen G1yG2, por tanto, esto sumado a la versión más abstracta del teorema nos lleva al Teorema de Tarski: Teorema de Tarski (para el lenguaje L L E): el conjunto Tde números Gödel de las sentencias verdaderas de LEno es expresable en LE, es decir, no es Aritmético. ¿Cómo demostramos en concreto el Teorema de Tarski? Se trata de ver cuál es el papel de la fórmula que expresa la diagonalización. Si Tes expresable, existe una fórmula H(y) que expresa T, de forma que H(n) es verdadera syss nes verdadero. ~H(y) expresa el conjunto T ෩, entonces ~H(n) equivale a que nno es verdadero. La fórmula y(D(x,y) ـ~H(y)) significa que la diagonalización de xno es verdadera. Si diagonalizamos esta
María Pérez Calvo Universidad de Valladolid 23 fórmula obtenemos la fórmula que será verdadera y no demostrable en el sistema: x(x= k)ـ(y(D(x,y)ـ~H(y))).
María Pérez Calvo Universidad de Valladolid 24 3. Demostración de incompletitud del sistema P.E. Ya tenemos demostrado tanto G1como G2, el siguiente paso es definir un concepto de demostrabilidad y demostrar que se cumple G3. Para ello necesitamos un sistema, que será el Sistema axiomático P.E. Se compone de ciertas fórmulas a las que denominamos axiomas, y dos reglas de inferencia que nos van a permitir demostrar nuevas fórmulas a partir de las fórmulas que ya hemos demostrado. El número de axiomas será infinito, pero cada uno de ellos será de una de las 19 formas reconocidas establecidas, los esquemas axiomáticos. Estos 19 se clasifican en cuatro grupos. En los axiomas, F,GyHse toman como cualesquiera fórmulas, viyvjcomo cualesquiera variables y tcomo cualquier término: xGrupo I: los esquemas axiomáticos para la lógica proposicional. oL1:(Fـ(GـF)) oL2:(Fـ(GـH)) ـ((FـG)ـ(FـH)) oL3:((~Fـ~G)ـ(GـF)) xGrupo II: los esquemas axiomáticos adicionales para la lógica de primer orden con identidad. oL4:(vi(FـG)ـ(viFـviG)) oL5:(FـviF), con tal de que vino aparezca en F. oL6:vi(vi=t), con tal de que vino aparezca en t. oL7:(vi=tـ(X1viX2ـX1tX2)), donde X1yX2son expresiones tales que X1viX2es una fórmula atómica. Estos dos primeros grupos reciben el sobrenombre de axiomas lógicos y junto con las dos reglas de inferencia constituyen una formalización llevada a cabo por Kalish y Montague (1964) de la lógica de primer orden con identidad. Los dos siguientes grupos de axiomas son los llamados axiomas aritméticos. xGrupo III. oN1:(v1’ = v2’ـv1=v2) oN2:0 ത=v’1 oN3:(v1+0 ത) = v1 oN4:(v1+v2’) = (v1+v2)’
María Pérez Calvo Universidad de Valladolid 25 oN5:(v1Â0 ത) = 0 ത oN6:(v1Âv2’) = ((v1Âv2) + v1) oN7:(v10 തؠv1=0 ത) oN8:(v1v2’ؠ(v1v2שv1=v2’) oN9:((v1v2)ש(v2v1)) oN10:(v1E0 ത) = 0 ത’ oN11:(v1Ev2’) = ((v1Ev2Âv1) xGrupo IV: se forma únicamente por el esquema axiomático correspondiente a la inducción matemática. Por F[v1’] entenderemos cualquiera de las fórmulas vi(vi=v1’ـv1(v1=viـF)), donde vies cualquier variable que no aparezca en F. oN12:(F[0 ത]ـ(v1(F(v1)ـF[v1’]) ـv1F(v1))) Las dos reglas de inferencia que constituyen junto a estos 19 esquemas axiomáticos el sistema P.E. son las siguientes: xModus Ponens: de Fy (FـG) inferimos G. xGeneralización: de Finferimos viF. Dentro del sistema P.E. se considera una demostración como una secuencia finita de fórmulas tal que cada uno de los miembros de la secuencia es, o bien un axioma, o bien es directamente derivable por dos miembros de la secuencia anteriores a través de la regla de modus ponens o directamente derivable de un miembro anterior de la secuencia mediante la regla de generalización. Una fórmula Fserá demostrable si existe una demostración cuyo último elemento sea F, si esto no sucede la fórmula es refutable. El objetivo ahora es demostrar que el conjunto de números Gödel de las fórmulas demostrables del sistema P.E. es un conjunto Aritmético. Recordamos que para cualquier base bODUHODFLyQx*by=zes Aritmética, y para cada n, la relación x1*bx2*b… *bxn=ytambién lo es. Llevamos a cabo una aritmetización de la sintaxis, es decir, mostramos que las propiedades y relaciones sintácticas de las expresiones se corresponden a través de la numeración de Gödel en propiedades y relaciones aritméticas entre los números correspondientes. A partir de aquí vamos a mostrar varios ejemplos de aritmetización.
María Pérez Calvo Universidad de Valladolid 32 xSi FHVXQȈ-fórmula, entonces para cualquier variable vi, la expresión viF HVXQDȈ-fórmula. xSi FHVXQDȈ-fórmula, entonces para cualesquiera variables distintas viy vj, las fórmulas (vivj)Fy (vivj)FVRQȈ-fórmulas, y para cualquier numeral n, las fórmulas (vi݊ത)Fy (vi݊ത)FVRQȈ-fórmulas. x3DUDFXDOHVTXLHUDȈ-fórmulas FyG, las fórmulas FשGyFרGVRQȈ- fórmulas. Si FHVXQDȈ0-fórmula y GHVXQDȈ-fórmula, la fórmula FـG HVXQDȈ-fórmula. 8QDȈ-fórmula puede contener cuantos cuantificadores existenciales libres sean necesarios, pero todos los cuantificadores universales tienen que estar necesariamente acotados. Ya hemos visto anteriormente que para cualquier bODFRQFDWHQDFLyQDODEDVH bes Aritmética. Pero en el sistema P.A. lo que estamos buscando son relaciones aritméticas, que no requieran el uso de la exponenciación. Para ello utilizamos la idea propuesta por John Myhill (1955), que establece que para cualquier número primo p, podemos definir Powp(x) sin recurrir a la exponenciación: xes una potencia de psyss cada divisor propio de xes divisible por p. Aquí podemos observar las ventajas de emplear un sistema en base 13. Según esta idea, podemos fácilmente mostrar que para un número primo p, la relación x*p y=zes aritméticaHQFRQFUHWRGHOWLSRȈ0. La demostración parte de comprobar que las siguienWHVWUHVUHODFLRQHVVRQGHOWLSRȈ0: xxdiv y oxdiv yļ(zy)(xÂz=y) xPowp(x) oPowp(xļzx)((zdiv xרzـpdiv z) xy=(౮) oy=(౮)ļPowp(y)רy>xרy>1) ר(z<y)~(Powp(z)רz >xרz>1) Como conclusión, x*p y=zļxÂ(౯)+y=z;x*p y=zļw1z)(w2 z)(w1=(౯)רw2=xÂw1רw2+y=z) también lo es. 7DPELpQODVVLJXLHQWHVUHODFLRQHVVRQȈ0:
María Pérez Calvo Universidad de Valladolid 33 xxBpy,xEpyyxPpy. oRecordamos que: xBbyļx=yש(xר(zy)(wy)(Powb(w)ר(x · w) *bz=y)) xEb\ļ[=yש(zy)(z*bx=y) xPb\ļ(zy)(zbyרx Bbz) &RQGLFLRQHVODVWUHVTXHVRQFODUDPHQWHȈ0. xPara cada nODUHODFLyQx1*p, …, *pxn=y. oSabemos que la relación x1*px2=yHVȈ0. Supongamos ahora que nHVWDOTXHODUHODFLyQx1*p, …, *pxn=yHVȈ0. Entonces la relación x1*p, …, *pxn, *pxn+1 =yWDPELpQHVȈ0y puede escribirse como (zy)(x1 *p, …, *pxn=zרz*pxn+1 =y). xPara cada nODUHODFLyQx1*p, …, *pxnPpy. oLa relación x1*p, …, *pxnPpypuede escribirse claramente como (zy)(x1 *p, …, *pxn=zPpy). Puesto que 13, que es la base que estamos utilizando, es un número primo, si utilizamos para sustituir a pen lo que acabamos de ver, llegamos a la conclusión de que el conjunto PEes aritmético, y más en concreto, dado que en él no aparece ningún cuantificador universal no acotado, es GH WLSR Ȉ &RPR FRQVHFXHQFLD HO FRQMXQWR ܲா ෪ también es aritmético. Sin embargo, no resulta tan sencillo afirmar que ܲா ෪* lo sea. Para inferir la aritmeticidad de un conjunto A* a partir de la de un conjunto Aes necesario mostrar que la relación 13x=yes aritmética, porque aparece en la fórmula que expresa la función diagonal, que es la clave para demostrar que A* es expresable. Para demostrar esto usaremos el siguiente teorema: Teorema E: la relación xy=zHVȈ1. Para demostrarlo necesitamos introducir el siguiente lema auxiliar: Lema K: existe una relación aritmética K(x,y,z) que posee las dos siguientes propiedades: para cualquier secuencia finita (a1,b1), (a2,b2), …, (an,bn) de pares ordenados de números naturales, existe un número ztal que para cualesquiera números x ey, la relación K(x,y,z) se cumpla syss (x,y) es una de los pares (a1,b1), …, (an,bn); y para cualesquiera números x,yyz, si K(x,y,z) se cumple, entonces xzeyz.
María Pérez Calvo Universidad de Valladolid 34 Intuitivamente, este lema establece que cuando tengo una secuencia de pares, puedo encontrar un número que codifica esa secuencia de pares. Demostración: recurrimos a las condiciones y afirmaciones que anteriormente hemos visto y demostrado que son de WLSR Ȉ0. Estas proposiciones se cumplían para cualquier número primo p, por lo que identificaremos los números naturales con sus representaciones en base 13. Recurriremos también a la idea de los marcos, presentada por Quine (1946), que establece que un marco es un número de forma 2t2 en el que la t es una cadena de unos (111…1). 1(x) será la condición de que xes una cadena de unos en QRWDFLyQEDVHFRQGLFLyQTXHHVGHWLSRȈ0(1(xļxר(yx)(yPx ـ1Py)). 9DPRVDWRPDUșFRPRODsecuencia finita ((a1,b1), …, (an,bn)) de pares ordenados de números, y fcomo el marco que es más largo que cualquier marco que sea parte de cualquiera de los números a1,b1, …, an,bn. Para tal fHOQ~PHURVHFXHQFLDGHșVHUi ffa1fb1ff,…,ffanfbnff. Estamos representando otro tipo de secuencias con otro mecanismo. xserá un marco maximal de ysi xes un marco, xes parte de yyxes tan largo como cualquier marco que forme parte de y. La relación xmf yHVȈ0, ya que xmf yļxPy ר (zy)(1(z)רx= 2z2ר ~(wy)(1(w)ר2zw2Py)). &RQWRGDODLQIRUPDFLyQTXHWHQHPRVHQHVWHPRPHQWRSRGHPRVGHILQLUODȈ0- relación que posteriormente jugará un papel crucial: K(x,y,z)ௗ ୀ(w z)(wmf zר wwxwywwPz רwܲ ෨xרwܲ ෨y). 3DUDFXDOTXLHUVHFXHQFLDșGHSDUHVRUGHQDGRVGHQ~PHURV si zHV FXDOTXLHU Q~PHUR VHFXHQFLD GH ș HQWRQFHV K(x,y,z) se cumplirá syss el par ordenado (x,ySHUWHQHFHDODVHFXHQFLDș$GHPiVSRUGHILQLFLyQGHK(x,y,z), para cualesquiera números x,yyz, si se cumple la relación, entonces xzyyz. Así queda demostrado el Lema K. De la demostración del Lema K se sigue fácilmente la demostración del Teorema E. Se cumple xy=zsyss existe un conjunto Sde pares ordenados tal que: x(y,z)אS. xPara todo par (a,b) en S, o bien (a,b) = (0, 1), o existe algún par (c,d) en Stal que (a,b) = (c+ 1, dÂx). Podemos ver esto de la siguiente manera: si xy=z, entonces tomamos Scomo el conjunto {(0, 1), (1, x), (2, x2), …, (y,xy)}. De forma inversa, suponemos que Ses cualquier conjunto de pares ordenados tal que las dos condiciones anteriores se cumplen.
María Pérez Calvo Universidad de Valladolid 35 Entonces de la segunda condición se sigue que para cualquier par (a,b) en S, se tiene que cumplir xa=b; y de la primera condición se sigue que xy=z. De esta forma, xy=zsyss existe un número wtal que K(y, w, z) y para cualquier número awy cualquier bw, si K(a,b,w), entonces o bien a= 0 y b= 1, o hay un número cay un número dbtales que K(c,d,w) y a=c+1 y b=dÂx. Por tanto, xy=zsyss se cumple la siguiente condición: w(K(y,z,w)ר(aw)(bw)(K(a,b,w)ـ((a= 0 רb= 1) ש(ca)(d b)(K(c,d,w)רa=c+ 1 רb=dÂx)))). Con esto concluye la demostración del Teorema E. Del Teorema E se siguen tres corolarios importantes. En primer lugar, que para cualquier conjunto aritmético A, el conjunto A* es aritmético, y además, si AHVȈA* también lo será. Ya que la relación xy=zHVȈODUHODFLyQx=ytambién lo es, y en consecuencia, la función diagonal d(x) también. 3RUWDQWRKD\XQDȈ-fórmula D(v1,v2) que expresa la relación d(x) = y. Entonces, para cualquier fórmula A(v1) que exprese un conjunto A, la fórmula v2(D(v1,v2)רA(v2)) expresa el conjunto A*, y si Aes aritmético, A* lo es también. El segundo corolario extraído del Teorema E afirma que el conjunto de números Gödel de las sentencias aritméticas verdaderas no es aritmético. Denominamos a este conjunto TA. Si fuera aritmético, entonces el conjunto ܶ ෪también tendría que serlo, y en consecuencia, ܶ ෪* también, algo que nos conduciría a contradicción. Por último, el tercer corolario dice que el conjunto P*Ees Ȉ \ HO FRQMXQWR ܲா ෪* es aritmético. Ya hemos demostrado que PEes ȈSRUWDQWRVHJ~QHOSULPHUFRURODULRTXHDFDEDPRVGHYHUP*E es ȈWDPELpQ(OKHFKRGHVHUȈKDFHTXHPEsea aritmético, por tanto, su complementario es aritmético, y según este primer corolario, ܲா ෪* también lo es. Si el conjunto ܲா ෪* es aritmético, existe una fórmula aritmética H(v1) que lo expresa. La diagonalización de esta fórmula, H[݄ ത]es una sentencia Gödel aritmética para ܲா ෪, y por tanto no es demostrable en P.E. ni en P.A., aunque sea verdadera. ~H[݄ ത]es falsa y tampoco es demostrable en P.A., si es correcto, entonces H[݄ ത]es una sentencia en el lenguaje LAde P.A. que no es ni demostrable ni refutable en el sistema P.A, que como vemos, es incompleto. Pero podemos demostrar también la incompletitud del sistema P.A. sin recurrir necesariamente a P.E., tomando PAcomo el conjunto de números Gödel de las fórmulas
María Pérez Calvo Universidad de Valladolid 36 GHPRVWUDEOHV HQ 3$ \ GHPRVWUDU TXH HVWH HV XQ FRQMXQWR GH WLSR Ȉ \ SRU WDQWR XQ conjunto aritmético. La demostración de la aritmeticidad de este conjunto es igual a la que realizamos para demostrar que PEera un conjunto aritmético, pero con algunos cambios: tenemos que hacer desaparecer la exponenciación del lenguaje y, por tanto, de los axiomas. Podemos reducir la exponenciación a operaciones que únicamente emplean la suma y la multiplicación y, por tanto, prescindir de ella y de los axiomas en los que interviene. Transformamos las fórmulas que teníamos para que no hagan referencia a esa posibilidad que ya no está. R1(x,y,z) se sustituye por Ezes una de las expresiones (Ex+Ey), (ExÂEy) o E’x, y en su demostración, z = x pl yשz=xtim yשz=xexp yשz=s(x), eliminamos la parte de z=xexp y. Con este cambio, tm(x) y fm(x) serán entonces las condiciones de que Ex es un término o una fórmula de P.A.; En el caso de A(x), eliminamos las cláusulas disyuntivas N10(x) y N11(x), con lo que pasa a ser la condición de que Exes un axioma de P.A.; por último, las última condición se reformula para que afirme que Exes demostrable en P.A. Entonces, el conjunto PAHV Ȉ \ HQFRQVHFXHQFLD los conjuntos ܲ ෪yܲ ෪*son aritméticos. Si tomamos ahora una fórmula aritmética H(v1) que exprese al conjunto ܲ ෪*, su diagonalización H[݄ ത]expresaría su propia no demostrabilidad en el sistema P.A., y así quedaría demostrada la incompletitud de este sistema. Tras concluir el apartado demostraremos la siguiente proposición C1, y para ello demostramos primero lo siguiente: Proposición C: x7RGDȈ0-UHODFLyQWDPELpQHVȈ1. xSi R(x1, …, xn,yHVȈ1también lo es la relación yR(x1, …, xn,y). xSi R1(x1, …, xn,y) y R2(x1, …, xn,yVRQȈ1, también lo son las relaciones R1(x1, …, xn,y)שR2(x1, …, xn,y) y R1(x1, …, xn,y)רR2(x1, …, xn,y). xSi R(x1, …, xn,y,zHVȈ1también lo son las relaciones (yz)R(x1, …, xn,y,z) y (yz)R(x1, …, xn,y,z). xSi RHVȈ0ySHVȈ1, entonces la relación RـSHVȈ1. Demostración:
María Pérez Calvo Universidad de Valladolid 37 x7RGDȈ0-UHODFLyQWDPELpQHVȈ1. oSupongamos que la relación R(x1, …, xnHVȈ0. Tomemos F(v1, …, vn FRPR XQD Ȉ0-fórmula que la exprese. Entonces, la fórmula vn+1F(v1, …, vnHVXQDȈ1-fórmula que expresa la misma relación R(x1, …, xn), por lo que RHVȈ1. xSi R(x1, …, xn,yHVȈ1también lo es la relación yR(x1, …, xn,y). oPara cualquier relación S(x1, …, xn,y,z) las dos siguientes condiciones son equivalentes: yzS(x1, …, xn,y,z)ؠw(yw) (zw)S(x1, …, xn,y,z). Supongamos ahora que x1, …, xnson números tal que la primera de ellas se cumple. Entonces tiene que haber números yyztales que S(x1, …, xn,y,z) se cumpla. Si tomamos wcomo el máximo de yyz, entonces (yw)(z w)S(x1, …, xn,y,z) se cumple para tal número wy, en consecuencia, la segunda condición se cumple. Supongamos ahora que R(x1, …, xn,yHVȈ1. Entonces R(x1, …, xn, y) es de forma zS(x1, …, xn,y,z), donde SHVXQDȈ0-relación. Entonces la relación yR(x1, …, xn,y) es la misma que la relación yzS(x1, …, xn,y,z). Como hemos visto, esta relación es equivalente a la relación w(yw)(zw)S(x1, …, xn,y,z), y HVWRHVȈ1, porque la relación (yw)(zw)S(x1, …, xn,y,z) es XQDȈ0-relación entre wyx1, …, xn. xSi R1(x1, …, xn,y) y R2(x1, …, xn,yVRQȈ1, también lo son las relaciones R1(x1, …, xn,y)שR2(x1, …, xn,y) y R1(x1, …, xn,y)רR2(x1, …, xn,y). oEsta afirmación equivale a aquella que establece que para FXDOHVTXLHUDȈ0-relaciones S1(x1, …, xn,y) y S2(x1, …, xn,y), las dos relaciones yS1(x1, …, xn,y)שyS2(x1, …, xn,y) y yS1(x1, …, xn, y)רyS2(x1, …, xn,yVRQȈ1.yS1(x1, …, xn,y)שyS2(x1, …, xn, y) porque equivale a y(S1(x1, …, xn,y)שS2(x1, …, xn,y)); la segunda porque equivale a yz(S1(x1, …, xn,y)רS2(x1, …, xn,z)), TXHHVȈ1según el punto anterior que acabamos de ver. xSi R(x1, …, xn,y,zHVȈ1también lo son las relaciones (yz)R(x1, …, xn,y,z) y (yz)R(x1, …, xn,y,z).
María Pérez Calvo Universidad de Valladolid 38 oSupongamos que R(x1, …, xn,y,zHVȈ1. Sabemos que la relación yzHVȈ0. Por tanto, el conjunto Kde todas las n+2-tuplas (x1, …, xn,y,z) tales que yzHVȈ0. En consecuencia, la relación K(x1, …, xn,y,zHVȈ1según el primer punto de esta Proposición C. De esto se sigue, gracias al tercer punto, que la relación K(x1, …, xn,y,z)ר R(x1, …, xn,y,zHVȈ1. El punto dos demuestra que la relación y(y zרR(x1, …, xn,y,zHVȈ1, ya que es la relación (yz)R(x1, …, xn,y,z). La demostración para (yz)R(x1, …, xn,y,z) es algo diferente. Dado que RHVȈ1H[LVWHXQDȈ0-relación S(x1, …, xn,y,z,w) tal que para todo x1, …, xn,yyz,R(x1, …, xn,y,z) se cumple syss wS(x1, …, xn,y,z,w). Entonces (yz)R(x1, …, xn,y,z) es la condición (yz)wS(x1, …, xn,y,z,w). Ahora supongamos que x1, …, xnyzson números tales que (yz)wS(x1, …, xn,y,z,w) VHFXPSOH(QWRQFHVSDUDWRGR\z, existe un número wytal que S(x1, …, xn,y,z,wy) se cumple. Si ves el mayor de esos números w0,w1, …, wz, entonces w0, …, wzVHUiQWRGRVv, y para todo y z, existe algún wy, para el que wv, tal que S(x1, …, xn,y,z,w). Por tanto, para esta v, la condición (yz)(wv)S(x1, …, xn,y, z,w) se cumple, y en consecuencia la condición v(yz)(w v)S(x1, …, xn,y,z,w) también. A la inversa, esta condición implica (yz)wS(x1, …, xn,y,z,w), que es la condición (yz)R(x1, …, xn,y,z). xSi RHVȈ0ySHVȈ1, entonces la relación RـSHVȈ1. oSuponemos que RHVȈ0ySHVȈ1.ܴ ෨VHUtDWDPELpQȈ0, y por el punto XQRȈ1. Según el punto tres, ܴ ෨שSHVȈ1, y esta es la relación Rـ S. Queda así demostrada la proposición. Proposición C1:WRGDȈ-UHODFLyQHVȈ1. Para cualquier fórmula F(ݒభ, …, ݒೖ)(i1<i2<…<ik) y cualquier nik,F(n) será el conjunto de todas las n-tuplas (a1, …, an) tal que F(ܽభ, …, ܽೖ) es una sentencia verdadera. Si Fes una fórmula regular F(v1, …, vn), entonces, F(n)es la relación expresada
María Pérez Calvo Universidad de Valladolid 39 por F(v1, …, vn). A partir de todo lo visto en la Proposición C, llegamos a la llamada Proposición C1TXHHVWDEOHFHTXHWRGDȈ-UHODFLyQHVȈ1. De esta extraemos dos corolarios: el primero que dice que si AHVȈ1,A* también lo es; y el segundo que establece que los conjuntos P*AyR*AVRQȈ1. Diremos de un conjunto o una relación que es recursiva si ella misma y su FRPSOHPHQWDULDVRQDPEDVȈ1. Una función f(x1, …, xn) = yes recursiva si la relación correspondiente es recursiva. Si repasamos todo lo que hemos visto hasta el momento en lo que se hace uso de secuencias contamos cuatro puntos donde recurrimos a ellas: la exponenciación (xy=z), en el que acudimos a una secuencia de yoperaciones con el número xque tienen como resultado a z; la formación de términos, en el que recurrimos a una secuencia de operaciones que tienen como resultado un término; la formación de fórmulas, en el que acudimos a una secuencia de operaciones que tienen como resultado una fórmula; y el ser demostrable, en el que recurrimos a una secuencia de fórmulas que es una demostración. En los tres primeros tipos de secuencias, a partir del tamaño del resultado final de la secuencia, podemos acotar el tamaño de la propia secuencia. Cuando decimos que algo es una fórmula es porque hay una secuencia de formación de una fórmula, y en función de lo larga que sea esa fórmula, podemos acotar el tamaño de su secuencia de formación. De igual forma con las secuencias de formación de términos o con la secuencia de la exponenciación. Esto es lo que no ocurre en una demostración. Viendo la fórmula demostrable no puedo hacer ningún cálculo del tamaño posible de la demostración, no podemos acotar nada. Intuitivamente esto significa que todos los conceptos que estás manejando hasta llegar al de ser demostrable son conceptos decidibles, el concepto de ser demostrable ya no lo es. Es decir, cuando me dan una expresión, puedo hacer una comprobación para ver si es una fórmula o no. Pero cuando me dan una fórmula y me preguntan si es demostrable en P.A., no tengo ningún procedimiento que me permita contestar en un numero finito de pasos a esa pregunta. Eso hace que en la fórmula PE(x) en P.E. (o en su equivalente PA(x) en P.A.), que es y(Pf(y)רxאy), es decir, “existe una secuencia de demostración yen la que parece x”, no sea posible acotar el cuantificador yy que intuitivamente sea una IyUPXODȈ1.
María Pérez Calvo Universidad de Valladolid 40 5. 7HRUHPDGH*|GHO\Ȧ-consistencia La demostración que hemos visto en el apartado anterior descansa sobre la hipótesis de que la Aritmética de Peano es correcta, es decir, que en ella cada una de las sentencias demostrables en P.A. es una sentencia verdadera. La demostración original de la incompletitud de este sistema que propone Gödel implica una asunción más débil que GHQRPLQDȦ-consistencia. Tomamos un sistema axiomático arbitrario Scuyas fórmulas son las de LE, cuyos axiomas incluyen todos los de los grupos I y II y cuyas reglas de inferencia son la generalización y el Modus Ponens. Este sistema es lo que podemos denominar una teoría de primer orden. xDiremos que Ses simplemente consistente si no contiene ninguna sentencia que sea a la vez demostrable y refutable en S. xDiremos que SHV Ȧ-inconsistente si existe una fórmula F(w) con una variable libre wtal que la sentencia wF(w) es demostrable, a pesar de que todas las sentencias F(0 ത), F(1 ത), …, F(݊ത), … son refutables. Según eso, un VLVWHPDȦ-consistente es un sistema que no eVȦ-inconsistente. 8Q VLVWHPD Ȧ-inconsistente nunca puede ser correcto, porque si wF(w) es verdadera, entonces al menos para alguna nla sentencia F(݊ത) tiene que ser verdadera. Lo que sí puede suceder es que XQVLVWHPDȦ-inconsistente sea simplemente consistente. Si Ses simplemente inconsistente, esto significa que toda sentencia es demostrable en él, por tanto, trivialmente WLHQH TXH VHU Ȧ-inconsistente; Así pues, si SHV Ȧ-consistente, entonces es también simplemente consistente. Se dice que Ses recursivamente axiomatizable o, lo que es lo mismo, axiomatizable, si el conjunto Pde números Gödel de las sentencias demostrables de Ses Ȉ1.(VWRVVLVWHPDVWDPELpQVHGHQRPLQDQVLVWHPDVIRUPDOHVVLVWHPDVUHRȈ1-sistemas. Dados dos sistemas SyS1, diremos que S1es un subsistema de SoSuna extensión de S1 si todas las fórmulas demostrables de S1también son demostrables en S. 7RGRVLVWHPDFRUUHFWRHVDXWRPiWLFDPHQWHȦ-consistente, por tanto, es más fuerte asumir que el sistema P.A. es correcto que DVXPLU TXH HV Ȧ-consistente. Ya hemos demostrado la incompletitud de P.A. tomando como premisa que P.A. es un sistema correcto. El objetivo principal de este apartado es la demostración del Teorema G, para
María Pérez Calvo Universidad de Valladolid 41 lo cual vamos a recurrir a otros teoremas que a su vez necesitan de más teoremas y lemas para su demostración. Como es un proceso complejo, vamos a ofrecer primero un esquema de cómo se organiza: Teorema GVLOD$ULWPpWLFDGH3HDQRHVȦ-consistente, entonces es incompleta. 1. Teorema A:si Ses cualquier sLVWHPDD[LRPDWL]DEOHȦ-consistente en el TXHWRGDVODVȈ0-sentencias verdaderas son demostrables, entonces Sdebe ser incompleto. oLema 2VLWRGDVODVȈ0-sentencias verdaderas son demostrables en SHQWRQFHVWRGRVORVȈ1-conjuntos y relaciones son enumerables en S. oTeorema A’:si SHVFXDOTXLHUVLVWHPDȦ-consistente axiomatizable HQHOFXDOWRGRVORVȈ1-conjuntos son enumerables, entonces Ses incompleto. Teorema 1: supongamos que Ses simplemente consistente yH(v1) es una fórmula cuya negación representa el conjunto P* en S. De esta forma la sentencia H(݄ ത) no es ni probable ni refutable en Sdonde hes el número Gödel de la fórmula H(v1). xLema 1: para cualquier fórmula H(v1) con número Gödel h:H(݄ ത) es demostrable en SļhאP*. /HPD Ȧ:si SHV Ȧ-consistente, entonces todo conjunto enumerable en Ses representable en S. Teorema 2:si P* es enumerable en SySHVȦ-consistente, entonces Ses incompleto. Teorema 3: suponemos que A(v1,v2) enumera P* en S. Tomamos acomo el número Gödel de la fórmula v2~ A(v1,v2)yGcomo la sentencia v2~A(v1,v2). De esta forma: xSi Ses simplemente consistente, entonces Gno es demostrable en S. xSi SHV Ȧ-consistente, entonces Sno es ni demostrable ni refutable. 2. Teorema B:WRGDVODVȈ0-sentencias verdaderas son demostrables en P.A.
María Pérez Calvo Universidad de Valladolid 48 Demostración: xSuponiendo que las 3 se cumplen, vamos a demostrar que C1debe entonces cumplirse también. Según D1WRGDVODVȈ0-sentencias atómicas verdaderas son demostrables en S. Tenemos que demostrar que todas las Ȉ0-sentencias atómicas falsas son refutables en S. oSi la sentencia falsa tiene la forma ݉ഥ =݊ത será refutable en Spor D2. oSi la sentencia falsa tiene la forma ݉ഥ ݊ത, entonces todas las sentencias ݉ഥ =0 തש…ש݉ഥ=݊ത son refutables. De esto se sigue según D3que ݉ഥ ݊ത es refutable. oSi la sentencia falsa tiene la forma ݉ഥ +݊ത =݇ ത. Ya que la sentencia es falsa, m+n=ppara algún número pk. Entonces ݉ഥ +݊ത =ҧ es demostrable en Spor D1yҧ ݇ തes demostrable en Spor D2. Por tanto, la fórmula ݉ഥ +݊ത ݇ തes demostrable en S. Por tanto, la sentencia falsa ݉ഥ +݊ത =݇ തes refutable en S. xDemostramos también que la condición C2es derivable de D3. Aceptamos D3. Suponemos que F(wHVXQDȈ0-fórmula con wcomo única variable libre, y nes un número tal que cada una de las nsentencias F(0 ത), …, F(݊ത) son todas demostrables en S. Por tanto, las fórmulas abiertas w=0 തـF(w), …, w=݊തـF(w) son todas demostrables en S. Por tanto, por lógica proposicional, la fórmula w= 0 ש…שw=݊തـF(w) es demostrable en S, de lo que se sigue que la fórmula w=݊തـF(w) lo es. Por tanto, según la regla de generalización, la sentencia w(w݊തـF(w)) es demostrable en S, y esta sentencia es la sentencia (w݊ത)F(w). Aquí finaliza la demostración de la Proposición 2. 9DPRV DKRUD D RIUHFHU DOJXQRV HMHPSORV GH VXEVLVWHPDV Ȉ0-completos de la Aritmética de Peano. Son cuatro subsistemas de P.A. que van de más fuerte a más débil, siendo este último el sistema (R0), el sistema mínimo que necesitamos para demostrar el teorema. Tenemos que demostrar que (R0 HV Ȉ0-completo y también que (R0) es un
María Pérez Calvo Universidad de Valladolid 49 VXEVLVWHPDGHWRGRVORVGHPiVTXHFRQVHFXHQWHPHQWHVRQȈ0-completos, al igual que P.A., que los incluye a todos. El primero de ellos es el sistema (Q), resultado de eliminar el esquema axiomático N12, el esquema de inducción, al sistema P.A. Trivialmente (Q) كP.A. Quedaría compuesto de los siguientes elementos: xN1:v1’ = v2’ـv1=v2 xN2:v1’ = 0 ത xN3:v1+0 ത=v1 xN4:v1+v2’ = (v1+v2)’ xN5:v1Â0 ത=0 ത xN6:v1Âv2’ = (v1Âv2) + v1 xN7:v10 തؠv1=0 ത xN8:v1v2’ؠ(v1v2שv1=v2’) xN9:v1v2שv2v1 En segundo lugar consideramos el sistema (Q0), formado por los esquemas axiomáticos desde el N1al N8, por tanto, trivialmente (Q0)ك(Q). Los otros dos sistemas a considerar son (R) y (R0). El sistema (R), debido a Raphael Robinson (1950). Este sistema tiene infinitos axiomas no lógicos que se recogen bajo los cinco siguientes esquemas axiomáticos: xȍ1: todas las sentencias ݉ഥ +݊ത =݇ ത, donde m+n=k. xȍ2: todas las sentencias ݉ഥ Â݊ത =݇ ത, donde mxn=k. xȍ3: todas las sentencias ݉ഥ ݊ത, donde mynson números distintos. xȍ4: todas las fórmulas v1݊തؠ(v1=0 തש…שv1=݊ത). xȍ5: todas las fórmulas v1݊തש݊തv1. 6LHOLPLQDPRVHOHVTXHPDD[LRPiWLFRȍ5obtenemos el sistema (R0), obviamente (R0)ك(R), del cual vamos a demostrar su Ȉ0-completitud y que es un subsistema del sistema (Q0). 'HPRVWUDPRVVXȈ0-completitud demostrando que cumple las condiciones D1,D2yD3de la Proposición 2. Para empezar, observamos que para cualquier número n, la sentencia ݊ത =݊ത es un teorema de lógica de primer orden con identidad. Por tanto, es demostrable en (R0). Suponemos mn. Dado que ݉ഥ =݉ഥ es demostrable, también lo es
María Pérez Calvo Universidad de Valladolid 50 ݉ഥ =0 തש…ש݉ഥ=݉ഥש…ש݉ഥ=݊ത De lo anterior más ȍ4se seguiría que la sentencia ݉ഥ ݊ത es demostrable. Por tanto, WRGDVODVȈ0-sentencias verdaderas con forma ݉ഥ ݊ത son demostrables en (R0). 6HJ~Qȍ1 \ȍ2WRGDVODVȈ0-sentencias atómicas verdaderas son demostrables en (R0). De esta forma, el sistema (R0) satisface la condición D1. También satisface la condición D2VHJ~Qȍ3. Para demostrar que satisface D3, para cada n, la fórmula v1݊തـ(v1=0 തש…שv1=݊ത) es demostrable en (R0), por lo que también lo es la fórmula v1(v1݊തـ(v1=0 തש…שv1=݊ത)). Por tanto, para cualquier variable w, la fórmula w݊തـ(w=0 തש…שw=݊ത)es demostrable en (R0). Así pues, de acuerdo con la Proposición 2, (R0HVȈ0completo. Demostramos a continuación que el sistema (R0) es un subsistema de (Q0). Aunque los axiomas de inducción de N12 no son axiomas de (Q0), podemos utilizar la inducción matemática en nuestro metalenguaje para demostrar varias cosas acerca de este subsistema. xSegún N4sabemos que si ݊ത +݉ഥ =ݍത es demostrable en (Q0), entonces también lo es ݊ത +݉+1 ത ത ത ത ത ത ത ത =ݍ+1 ത ത ത ത ത ത ത . Según N3también es demostrable ݊ത +0 ത =݊ത, por lo que podemos demostrar ݊ത +1 ത=݊+1 ത ത ത ത ത ത ത ,݊ത +2 ത=݊+2 ത ത ത ത ത ത ത , …, ݊ത +݉ഥ =݊+݉ ത ത ത ത ത ത ത ത 'HHVWDIRUPDWRGDVODVVHQWHQFLDVȍ1son demostrables en (Q0). xSegún N6, sabemos que si ݊ത Â݉ഥ =ݍത es demostrable, entonces también lo son ݊ത Â݉+1 ത ത ത ത ത ത ത ത =ݍത +݊ത y ݊ത Â݉+1 ത ത ത ത ത ത ത ത =ݍ+݊ ത ത ത ത ത ത ത Por tanto, si ݊ത Â݉ഥ =݊ × ݉ ത ത ത ത ത ത ത ത ത es demostrable, ݊ത Â݉+1 ത ത ത ത ത ത ത ത =݊ × (݉+1) ത ത ത ത ത ത ത ത ത ത ത ത ത ത ത ത ത también lo es. Según N5queda demostrado en este sistema ݊ത Â0 ത=0 ത. Con todo esto también se demuestra ݊ത Â1 ത=݊ × 1 ത ത ത ത ത ത ത ത ,݊ത Â2 ത=݊ × 2 ത ത ത ത ത ത ത ത , …, ݊ത Â݉ഥ =݊ × ݉ ത ത ത ത ത ത ത ത ത 'HHVWDIRUPDWRGDVODVVHQWHQFLDVȍ2son demostrables en (Q0).
María Pérez Calvo Universidad de Valladolid 51 x3DUDHOHVTXHPDD[LRPiWLFRȍ3tenemos que demostrar que para cualquier número my cualquier número positivo n, la sentencia ݉ഥ ݊+݉ ത ത ത ത ത ത ത ത es demostrable en (Q0). En primer lugar, para cualesquiera números myn, la sentencia ݉+1 ത ത ത ത ത ത ത ത =݊+1 ത ത ത ത ത ത ത ـ݉ഥ=݊ത es demostrable en el sistema según N1. Por tanto, ݉ഥ ݊തـ݉+1 ത ത ത ത ത ത ത ത ݊+1 ത ത ത ത ത ത ത es demostrable. De esta forma, si ݉ഥ ݊ത es demostrable, también lo es ݉+1 ത ത ത ത ത ത ത ത ݊+1 ത ത ത ത ത ത ത . Para cualquier número positivo n, la sentencia 0 ത݊ത es demostrable según N2. Por tanto, podemos demostrar 1 ത݊+1 ത ത ത ത ത ത ത ,2 ത݊+2 ത ത ത ത ത ത ത , …, ݉ഥ ݊+݉ ത ത ത ത ത ത ത ത . xPara el esquema axiomátiFRȍ4, demostramos por inducción de nque v1݊തؠ(v1=0 തש…שv1=݊ത) es demostrable en (Q0). Según N7,v10 തؠv1=0 തes demostrable. Supongamos que nes tal que v1݊തؠ(v1=0 തש…שv1=݊ത) es demostrable. Entonces, ya que v1݊+1 ത ത ത ത ത ത ത ؠ(v1݊തשv1=݊+1 ത ത ത ത ത ത ത ) es demostrable según N8, se sigue por lógica proposicional que v1݊+1 ത ത ത ത ത ത ത ؠ(v10 തש…ש݊തשv1=݊+1 ത ത ത ത ത ത ത ) es demostrable. Así se completa la inducción. Como hemos visto, OD Ȧ-consistencia juega un papel fundamental en la demostración de incompletitud llevada a cabo por Gödel. Una versión más intuitiva e informal de la demostración mostrará más claramente el papel GHODȦ-consistencia en la demostración. La fórmula G, que dice que “no existe una demostración de G”, sería la negación de XQDVHQWHQFLDȈ1:x(xes una demostración de G). xSi SٟG(léase, Ges demostrable en S), entonces Sٟ x(xes una demostración de G). Pero SٟGsignifica que existe una demostración de G, con número j\XQDȈ0-sentencia “jes una demostración de G”, que VHUiȈ0verdadera y por tanto, demostrable. De ella se deducirá fácilmente la afirmación existencial x(xes una demostración de G), que contradice
María Pérez Calvo Universidad de Valladolid 52 a la fórmula G, por hipótesis también demostrable. Por tanto, si el sistema es simplemente consistente, Gno es demostrable. xPor tanto, S٫G\DVtVRQGHPRVWUDEOHVODVȈ0-sentencias “0 no es una demostración de G”, “1 no es una demostración de G”, etc., puesto que VRQ Ȉ0y verdaderas. Pero si Sٟ~G, es decir, Sٟ x(xes una demostración de G), entonces, eliminando la doble negación, tenemos que Sٟx(xes una demostración de G 6L HVWR VXFHGH HO VLVWHPD HV Ȧ- inconsistente, puesto que demostraríamos una afirmación existencial junto con la negación de todos sus casos particulares. Por tanto, si SHV Ȧ- consistente, Gtampoco es refutable. No es difícil demostrar que (R) es un subsistema de (Q). Para ello basta demostrar TXHODVIyUPXODVGHȍ5se obtienen a partir de N9instanciando la variable v2.
María Pérez Calvo Universidad de Valladolid 53 6. El Teorema de Incompletitud según Rosser La demostración de incompletitud del sistema P.A. de Gödel se basa en la DVXQFLyQGHTXHHOVLVWHPD3$HVȦ-consistente. Rosser (1936), en la última versión del teorema que vamos a tratar, demuestra la incompletitud de este sistema partiendo de la asunción de su consistencia simple. Para ello no utiliza la sentencia G, sino que construye otra sentencia que la sustituye en la demostración. Otra diferencia entre ambas sentencias, además de que XQD UHTXLHUD TXH HO VLVWHPD 3$ VHD Ȧ-consistente y la otra que sea simplemente consistente, es que la fórmula de Gödel se basa en una fórmula que expresa el conjunto ܲ ෨*, mientras que la de Rosser se basaba en una fórmula que expresa el conjunto P*. Además, la demostración de Gödel se puede llevar a cabo para el subsistema más débil de P.A., el sistema (R0), mientras que la demostración de Rosser requiere como mínimo el sistema (R). Pese a esto, este subsistema sigue siendo menos que P.A., puesto que seguimos prescindiendo de la inducción. Para presentar el primer teorema conviene definir el siguiente concepto: un sistema SHVXQDH[WHQVLyQGHȍ4\ȍ5VLWRGDVODVIyUPXODVGHȍ4\ȍ5son demostrables en S. Como recordatorio, estos dos esquemas axiomáticos se conformaban de las siguientes fórmulas: xȍ4: todas las fórmulas v1݊തؠ(v1=0 തש…שv1=݊ത). xȍ5: todas las fórmulas v1݊തש݊തv1. El objetivo de este apartado va a ser demostrar el siguiente teorema: Teorema RWRGDH[WHQVLyQD[LRPDWL]DEOHVLPSOHPHQWHFRQVLVWHQWHGHȍ4\ȍ5en ODFXDOWRGRVORVȈ1-conjuntos son enumerables debe ser incompleta. De este teorema se siguen tres corolarios: en primer lugar, que toda extensión axiomatizable VLPSOHPHQWH FRQVLVWHQWH GH ȍ4\ ȍ5HQ OD FXDO WRGDV ODV Ȉ0-sentencias verdaderas son demostrables debe ser incompleta; segundo, toda extensión axiomatizable simplemente consistente del sistema (R) es incompleta; por último, si el sistema P.A. es simplemente consistente, es incompleto. Para llegar al Teorema R necesitaremos unos resultados previos:
María Pérez Calvo Universidad de Valladolid 54 Teorema 1:si H(v1) es una fórmula que representa en Sun superconjunto de R* disjunto de P*, entonces la sentencia H(݄ ത) es indecidible en S, donde hes el número Gödel de H(v1). Demostración:Aes el conjunto representado por H(v1). Suponemos que R*كA y que P* es disjunto de A.Ya que H(v1) representa A, entonces H(݄ ത) es demostrable en S syss hאA.H(݄ ത) es demostrable en Ssyss hאP*. De esta manera, hאP* syss hאA. Pero P*, por hipótesis, es disjunto de A, por lo que hבA. Ya que hבP*, entonces H(݄ ത) no es demostrable en S. Como hבA, entonces hבR*, de forma que H(݄ ത) no es refutable en S, así que es indecidible en S. Así concluye la demostración. El Teorema 1 sugiere la siguiente noción de separabilidad. Diremos que una fórmula F(v1) separa un conjunto Ade un conjunto Ben Ssi para todo nאA,F(݊ത) es demostrable en Sy para todo nאB,F(݊ത) es refutable en S. Lema 1:siF(v1) separa Ade Ben SySes consistente, entonces F(v1) representa algún superconjunto de Aque es disjunto de B. Demostración: asumimos la hipótesis. A’ será el conjunto representado por F(v1) en S. Ya que para todo nאAla sentencia F(݊ത) es demostrable, entonces AكA’. Si algún número nestuviera tanto en A’ como en B, entonces F(݊ത) sería a la vez demostrable y refutable en S. Por tanto, si Ses simplemente consistente, entonces A’ es disjunto de B. De esta forma queda demostrado el Lema 1. Del Teorema 1 y el Lema 1 surge un segundo teorema: Teorema 2:si H(v1) separa R* de P* en SySes simplemente consistente, entonces H(݄ ത) es indecidible en S, donde hes el número Gödel de H(v1). Decimos que Aes separable de Ben Ssi existe una fórmula F(v1) que separe Ade Ben S. Siguiendo el Teorema 2, para demostrar que P.A. es incompleto asumiendo únicamente su simple consistencia, es suficiente con demostrar que R* es separable de P* en P.A. Llamamos a Ssistema Rosser para conjuntos VLSDUDFXDOHVTXLHUDȈ1-conjuntos AyB, el conjunto A–Bes separable de B–Aen S; y para cada n>1, llamamos a Sun sistema Rosser para relaciones n-DULDVVLSDUDGRVȈ1-relaciones cualesquiera R1(x1, …, xn) y R2(x1, …, xn) que son enumerables en S, sus diferencias R1–R2yR2–R1son separables en S.
María Pérez Calvo Universidad de Valladolid 55 Lema S (Lema de Separación) VL WRGDV ODV IyUPXODV GH ȍ4\ ȍ5son demostrables en S, entonces para cada dos relaciones cualesquiera R1(x1, …, xn) y R2(x1, …, xn) enumerables en S, sus diferencias R1–R2yR2–R1son separables en S. Demostración:VXSRQJDPRVTXHWRGDVODVIyUPXODVGHȍ4\ȍ5son demostrables en S. Vamos a demostrar que para dos conjuntos cualesquiera AyBenumerables en S, el conjunto B–Aes separable de A–Ben S.A(x,y) y B(x,y) son fórmulas que enumeran respectivamente AyBen S. Demostramos que la fórmula y(A(x,y)ـ(zy)B(x,z)) separa B–Ade A–Ben S. xSuponemos n א B–A. De esta forma, nאB, y para algún número k, la sentencia B(݊ത,݇ ത) es demostrable en S. También, nבA, y por eso para todo mk, la sentencia A(݊ത,݉ഥHVUHIXWDEOH$GHPiVVHJ~Qȍ4, la sentencia (y݇ ത)~A(݊ത,y) es demostrable. Por tanto, la fórmula abierta y݇ തـ~ A(݊ത,y) es demostrable y, en consecuencia, A(݊ത,y)ـ~(y ݇ ത) es demostrable. 'Hȍ5se sigue que A(݊ത,y)ـ݇ തyes demostrable, y ya que B(݊ത,݇ ത) es demostrable, A(݊ത,y)ـ(݇ തyרB(݊ത,݇ ത)) es demostrable. Así, por lógica de primer orden, la fórmula A(݊ത,y)ـ(zy)B(݊ത,z) es demostrable, de forma que también lo es la sentencia y(A(݊ത,y)ـ(zy)B(݊ത,z)). xSuponemos nאA–B. Entonces para algún k,A(݊ത,݇ ത) es demostrable y para todo m k,B(݊ത,݉ഥ HV UHIXWDEOH \ GH HVWD IRUPD VHJ~Q ȍ4, la sentencia (zk)~B(݊ത,z) es demostrable. Se sigue que la sentencia A(݊ത,݇ ത)ר(z݇ ത)~B(݊ത,z) es demostrable, de forma que también lo es la sentencia ~(A(݊ത,݇ ത)ـ~(z݇ ത)~B(݊ത,z)) y esta es la sentencia ~(A(݊ത,݇ ത)ـ(z݇ ത)~B(݊ത,z)). Ya que la sentencia A(݊ത,݇ ത)ـ(z݇ ത)~B(݊ത,z) es refutable, equivale a la sentencia y(A(݊ത, ݇ ത)ـ(z݇ ത)~B(݊ത,z)). Así finaliza la demostración.
María Pérez Calvo Universidad de Valladolid 56 Teorema 3:FXDOTXLHUH[WHQVLyQ GH ȍ4\ ȍ5HQ OD TXHWRGDV ODV Ȉ0-sentencias verdaderas sean demostrables es un sistema Rosser. De este teorema extraemos el siguiente corolario: los sistemas (R), (Q) y P.A. son sistemas Rosser. A partir del Lema S y el Teorema 2 se sigue un nuevo teorema: Teorema 4:Sserá cualquier sistema simplemente consistente en el que los conjuntos P* y R*VHDQDPERVHQXPHUDEOHV\HQHOTXHWRGDVODVIyUPXODVGHȍ4\ȍ5son demostrables. Por tanto, Ses incompleto. Demostración: suponemos que A(x,y) es una fórmula que enumera P* en S, y B(x,y) es una fórmula que enumera R* en S. Según el Lema S, la fórmula y(A(x,y)ـ(zy)B(x,z)) separa R* de P*en S. Entonces, según el Teorema 2, si hes el número Gödel de esta fórmula, la sentencia y(A(݄ ത,y)ـ(zy)B(݄ ത,z)) es indecidible en S. Así queda demostrado el Teorema 4. Podemos ahora fácilmente demostrar el Teorema R. Suponemos que Sobedece a la hipótesis del Teorema R. Suponemos que SHVXQDH[WHQVLyQGHȍ4\ȍ5,A(x,y) es una fórmula que enumera P* en S, y B(x,y) es una fórmula que enumera R* en S. Según el Lema S, la fórmula y(A(x,y)ـ(zy)B(x,z)) separa R*–P* de P* –R*. Asumiendo que Ses consistente, los conjuntos R* y P* son disjuntos, por lo que R*–P* = R* y P* –R* =P*, y por tanto, la fórmula que acabamos de ver los separa. Tomamos hcomo el número Gödel de esta fórmula. Según el Teorema 2, la sentencia y(A(݄ ത,y)ـ(zy)B(݄ ത,z)) es indecidible en S. Finaliza aquí la demostración del Teorema R. Esta última sentencia es la sentencia indecidible de Rosser que sustituye en la demostración de incompletitud a la sentencia Gpropuesta por Gödel. Podemos comparar
María Pérez Calvo Universidad de Valladolid 57 ambas sentencias y establecer algunas diferencias dentro del sistema P.A. Dado que este sistema es axiomatizable, el conjunto PHVȈ1\HQFRQVHFXHQFLDH[LVWHXQDȈ0-fórmula A(x,yTXHH[SUHVDXQDȈ0-relación cuyo dominio es P*. De esta forma, para cualquier número n,nאP* syss existe algún número mtal que A(݊ത,݉ഥ) es una sentencia verdadera. Además, nאP* syss En(݊ത) es demostrable. mserá testigo de que En(݊ത) es demostrable syss la sentencia A(݊ത,݉ഥ) es demostrable. La sentencia Gödel, y~A(ܽത,y), expresa la proposición de que para todo y,yno es un testigo de que Ea(ܽത) es demostrable, pero Ea(ܽത) es la sentencia y~A(ܽത,y). Podríamos traducirla de forma intuitiva como “Yo no soy demostrable”. Asumiendo la Ȧ-consistencia del sistema, esta sentencia es indecidible. La sentencia Rosser, y(A(݄ ത,y)ـ(zy)B(݄ ത,z)), podría traducirse de forma intuitiva como “Si hay una demostración de mí con un cierto número, entonces hay un número más pequeño correspondiente a una refutación de mí”. Esta es la versión más fuerte del teorema, puesto que, entre todas las versiones, es la que se basa en la asunción más débil, la consistencia simple del sistema3UHVFLQGHGHODȦ-consistencia necesaria para la demostración de Gödel. Pero a su vez es la más olvidada, puesto que cuenta con la desventaja de que esta fórmula, en comparación con la sentencia G, es poco intuitiva.