Qué dice exactamente el primer teorema de incompletitud de Gödel
Hace un tiempo, sobre todo a raíz de algunos textos que leí acerca de la «aplicación» de los teoremas de incompletitud de Gödel a temas con los que no tienen ninguna relación, volvió a mi cabeza la idea de hablar sobre estos teoremas en el blog. Para ello preferí intentar contar con la colaboración de algún especialista en el tema, y casi automáticamente vino a mi mente el nombre de Gustavo Piñeiro, matemático argentino, autor junto a Guillermo Martínez del libro Gödel para Todos (editado en 2009 en Argentina y en 2010 en España y que ya os recomendé para el día del libro en 2012) y responsable del blog El Topo Lógico, dedicado a la divulgación de la matemática.
Gustavo accedió gustosamente a mi sugerencia de colaboración, y hoy, por fin, se publica el texto que escribió sobre el primer teorema de incompletitud de Gödel para Gaussianos. Espero que os aclare todas vuestras dudas sobre ello. Y si no es así ya sabéis que tenéis los comentarios de este post para plantearlas.
El Programa de Hilbert
Los dos teoremas de incompletitud de Gödel, publicados en 1931, forman parte de una larga polémica relativa a los fundamentos de las matemáticas. Esta polémica había comenzado a finales del siglo XIX a causa de los trabajos de Georg Cantor sobre los conjuntos infinitos, y se había exacerbado a principios del siglo XX con el descubrimiento de la Paradoja de Russell.
En esta polémica, la escuela intuicionista, encabezada por L.E.J. Brouwer, sostenía que el uso que había hecho Cantor del infinito en acto era absurdo e injustificado y que toda su teoría no era más que un juego de palabras sin sentido. Los únicos objetos matemáticos válidos, sostenía esta escuela, son aquellos que se pueden construir algorítmicamente en una cantidad finita de pasos.
Pero el gran matemático alemán David Hilbert no estaba para nada de acuerdo con la idea de descartar la teoría de Cantor y hacia 1920 intervino en la polémica para proponer una alternativa al intuicionismo. Fue así como, en una serie de artículos publicados a lo largo de los diez años siguientes, le dio forma al llamado Programa de Hilbert, el cual, en esencia, llevaba la exigencia de finitud y de constructividad de los objetos matemáticos a los razonamientos matemáticos.
Con más precisión, Hilbert proponía la creación de una nueva ciencia a la que él llamaba metamatemática. Esta ciencia tendría como objetivo verificar la validez de los razonamientos matemáticos. Para evitar polémicas, y para asegurarse de que no surgieran nuevas paradojas, esta ciencia sería puramente finitista, es decir, la metamatemática trataría a los enunciados y a los razonamientos matemáticos como si fueran simples secuencias de símbolos sin significado a los que manipularía algorítmicamente.
Con más precisión, el Programa de Hilbert proponía dar un conjunto de axiomas para la aritmética que cumpliera estas cuatro condiciones:
1. El sistema debía ser consistente; es decir, no debía existir un enunciado P tal que P y su negación fueran simultáneamente demostrables a partir de los axiomas.
2. La validez de cualquier demostración basada en esos axiomas debía ser verificable algorítmicamente en una cantidad finita de pasos.
3. Dado cualquier enunciado P, o bien él o bien su negación debía ser demostrable a partir de los axiomas.
4. La consistencia de los axiomas (es decir, la validez de la primera condición) debía ser verificable algorítmicamente en una cantidad finita de pasos.
(La aritmética es la teoría que habla de la suma y el producto de los números naturales. Hilbert consideraba que era ésta la teoría fundamental de la Matemática, y no la Teoría de Conjuntos.)
Los teoremas de Gödel
En un congreso sobre los fundamentos de las matemáticas celebrado en la ciudad de Königsberg en septiembre de 1930 Arend Heyting, en representación de la escuela intuicionista, dio por terminada la polémica al aceptar que el Programa de Hilbert era el camino que debía seguir el pensamiento matemático. Pero lamentablemente para Hilbert, en ese mismo momento un joven y aún desconocido Kurt Gödel pidió la palabra para decir que él acababa de demostrar dos teoremas que probaban que el Programa de Hilbert era completamente irrealizable.
Concretamente, el primer teorema de incompletitud de Gödel, el más famoso de los dos, dice que si se cumplen las dos primeras condiciones planteadas por Hilbert entonces la tercera nunca podrá cumplirse. Es decir, si el sistema de axiomas es consistente y sólo se admiten demostraciones que sean verificables algorítmicamente, entonces siempre habrá un enunciado P tal que ni él si su negación son demostrables. El segundo teorema, al que no nos referiremos aquí, dice que si se cumplen las dos primeras condiciones y una versión más débil de la tercera entonces es la cuarta condición la que no podrá cumplirse.
La demostración del primer teorema
Vamos a explicar las ideas principales de la demostración del primer teorema de incompletitud de Gödel. Imaginemos entonces que se ha dado un sistema de axiomas para la aritmética que es consistente y supongamos además que sólo admitimos demostraciones verificables algorítmicamente. Tenemos que demostrar entonces que existe un enunciado, al que llamaremos G, tal que ni él ni su negación son demostrables a partir de esos axiomas mediante las demostraciones admitidas.
El primer paso de la demostración consiste en asignar a cada enunciado aritmético un número natural, al que llamaremos el número de Gödel de ese enunciado. Por ejemplo, al enunciado “2 es par” podría corresponderle el número 19, mientras que al enunciado “9 es primo” podría corresponderle el número 44.
Debemos hacer aquí dos aclaraciones importantes. La primera es que la asignación de números de Gödel alcanza a todos los enunciados, tanto a los verdaderos como a los falsos. La segunda aclaración es que
Segunda parte de la demostración
Una vez que se han asignado todos los números de Gödel queda perfectamente establecido cuál es el conjunto de estos números que corresponden a los enunciados que son demostrables a partir de los axiomas dados. La segunda parte de la demostración del primer teorema de incompletitud consiste en probar que este conjunto puede definirse usando solamente propiedades aritméticas. Es decir, el conjunto formado por los números de Gödel de los enunciados demostrables es definible mediante propiedades puramente numéricas.
Normalmente esa propiedad numérica es terriblemente compleja de expresar; pero para que se entienda la idea vamos a suponer que los números de Gödel de los enunciados demostrables son exactamente los números que se pueden escribir como suma o resta de tres primos consecutivos. Por ejemplo, dado que 3 – 5 + 7 = 5, entonces el número 5 es el número de Gödel de un enunciado demostrable; lo mismo sucede con el 13, que es -5 + 7 + 11. El 2, en cambio, no puede escribirse como suma o resta de tres primos consecutivos, por lo que 2 no es el código de un enunciado demostrable (siempre entendemos «demostrable a partir de los axiomas dados»).
Es interesante observar que es en esta parte del razonamiento donde interviene la suposición de que las demostraciones aceptadas por el programa de Hilbert son aquellas que son verificables algorítmicamente. En efecto, si esta condición no se cumpliera entonces no hay modo de garantizar que el conjunto de los números de Gödel de los enunciados demostrables puede caracterizarse aritméticamente.
El método de autorreferencia
La tercera parte de la demostración consiste en probar que, dada cualquier propiedad aritmética P, existe un número k tal que al enunciado “k cumple la propiedad P” le corresponde ese mismo número k. Podemos llamar a esta idea el método de autorreferencia, ya que el enunciado en esencia está diciendo “Mi número de Gödel cumple la propiedad P”.
Este método nos dice entonces que existe un número n tal que al enunciado «n no se puede escribir como suma o resta de tres primos consecutivos» le corresponde como número de Gödel precisamente el número n. Supongamos, para fijar ideas, que ese número n es el 43. Es decir, estamos suponiendo que al enunciado, que llamaremos G, que dice «43 no se puede escribir como suma o resta de tres primos consecutivos» le corresponde el número de Gödel 43.
Notemos que G dice “Mi número de Gödel no se puede escribir como suma o resta de tres primos consecutivos», y como estamos suponiendo que ésa es la propiedad que caracteriza a los números de Gödel de los enunciados demostrables entonces G está diciendo: “Mi número de Gödel no corresponde a un enunciado demostrable”. En definitiva, G dice: “Yo no soy demostrable”.
Conviene destacar aquí que la referencia a los números que se pueden escribir como suma o resta de tres primos consecutivos sólo sirve a modo de ejemplo hipotético y con fines puramente didácticos. En realidad Gödel demuestra que, sin importar cuáles sean los axiomas propuestos, si se cumplen las dos primeras condiciones del Programa de Hilbert siempre es posible hallar un enunciado aritmético que puede parafrasearse como “Yo no soy demostrable”.
La cuarta, y última parte, de la demostración del primer teorema de Gödel consiste en probar que ni G ni su negación son demostrables a partir de los axiomas dados. Para facilitar la explicación de esta última parte vamos a suponer que los axiomas que se han dado son todos enunciados verdaderos, una suposición que parece evidente, pero que la demostración que hizo Gödel en realidad no necesita (para Gödel es suficiente con que el sistema sea consistente; los axiomas, en la versión original del teorema, no necesitan se verdaderos).
Tenemos entonces que el enunciado G es un enunciado aritmético que dice esencialmente “G no es demostrable a partir de los axiomas dados”.
Observemos que si todos los axiomas son todos enunciados verdaderos entonces los enunciados que pueden demostrarse a partir de ellos también son verdaderos. Ahora bien, el enunciado G puede ser verdadero o falso. Si fuera falso, entonces, leyendo lo que dice, deduciríamos que G sí es demostrable. Tendríamos así un enunciado falso y demostrable, pero esto, por lo dicho más arriba, es imposible.
Luego G es verdadero, pero como es verdadero entonces, tomando en cuenta lo que dice de sí mismo, deducimos que no es demostrable a partir de los axiomas dados. Luego G es verdadero, pero no demostrable. Observemos que la negación de G, dado que es falsa, tampoco es demostrable. Es decir, ni G ni su negación son demostrables a partir de los axiomas dados. Esto completa la demostración del primer teorema de Gödel.
Esta es la tercera contribución de Gaussianos a la Edición 5.7: Alan Turing del Carnaval de Matemáticas, que en esta ocasión tiene como anfitrión a @cuantozombi en su blog El zombi de Schrödinger.
23/10/2014
Hace años me leí las demostraciones de los teoremas. Eran difíciles de entender en abstracto, pero este ejemplo de «sumas-restas de 3 primos consecutivos» ayuda. Felicidades.
¿Podríais hablar de P vs. NP?.
23/10/2014
Antonio, es una de las ideas que tengo en mente para futuros artículos. Estate atento al blog, algo saldrá en los próximos tiempos :).
23/10/2014
Estaré atento. Pero aparte de la relación de Gödel con el problema P vs. PN, tengo una segunda duda. Penrose, apoyándose en los teoremas de incompletitud de Gödel, critica a quienes piensan que los ordenadores pueden llegar a ser conscientes de un modo esencialmente similar a como lo son los hombres. ¿Creéis apropiada esa argumentación godeliana de Penrose?, ¿tal vez sea algo artificiosa y su consclusión pudiera ser errónea?.
23/10/2014
Amigo Antonio (AKA \»Un físico\»), en lenguaje lógico-matemático me resulta forzado utilizar un concepto tan ambiguo como «esencialmente similar» mezclándolo con otro tan claro como «verdadero o falso». A no ser que definamos con toda precisión lo que significa «esencialmente similar» y sustituyamos la expresión por esa definición. Con definiciones distintas podríamos facilitar la respuesta sobre la verdad o falsedad de la argumentación de Penrose. Hablo por instinto ya que ignoro el valor que da Penrose a la expresión y la argumentación «gödeliana» en que apoya su conclusión.
24/10/2014
Muy bueno, el artículo. ¿Podrías hablar algo más sobre lo de la aplicación a temas que no tienen ninguna relación?
24/10/2014
Penrose no es el único autor que ha apelado a los teoremas de Gödel para intentar demostrar que una computadora nunca podrá igualar al cerebro humano (más exactamente, para demostrar que existen problemas que el cerebro puede resolver pero que son irresolubles para cualquier computadora). Pero estos argumentos son falaces. No digo que la conclusión de Penrose sea falsa (tampoco digo que sea verdadera), sólo digo que sus argumentos «gödelianos» no son válidos. Desde la página http://godelparatodos.blogspot.com se puede descargar el capítulo 1 del libro «Gödel para Todos», allí se habla un poco de este tema. Por otra parte, hay muchas otras «aplicaciones» del teorema de Gödel a cuestiones extra-matemáticas, pero muchas de ellas son, por así decir, muy dudosas.
25/10/2014
Muy interesante aunque no sé si entendido bien las implicaciones del teorema. El teorema de Godel hace imposible el sueño de Hilbert de un automatismo que fuera demostrando uno por uno todos los teoremas de la matemática partiendo de unos axiomas (algo así como el fin del oficio de matemático ¿no?). Sin embargo, ¿no sería aún posible una cosa así? Tal y como yo lo veo los enunciados autoreferentes son los que dan problemas y además no aportan información sobre la aritmética (¿no?). Dejando fuera los enunciados autoreferentes ¿no podría aún construirse un sistema axiomático consistente y completo?.
25/10/2014
Estimado Miguel Ángel. El teorema de Gödel impide, en efecto, completar el sueño de Hilbert, el cual consistía en hallar un conjunto bien definido de métodos automáticos (es decir, algorítmicos, programables en una computadora) que permitiera demostrar todos los teoremas aritméticos. El oficio del matemático, precisamente, está a salvo gracias a eso, si entendemos que ese oficio incluye la búsqueda de nuevos métodos de demostración.
Por otra parte, el enunciado indecidible que encuentra Gödel sólo es autorreferente en cierto nivel de lectura; en el nivel más básico es simplemente un enunciado aritmético. De hecho, en el ejemplo hipotético mostrado en el texto el enunciado que encuentra Gödel es “43 no se puede escribir como suma o resta de tres primos consecutivos” (que da, obviamente, información aritmética). Además, hay que decir que Gödel muestra un ejemplo concreto de enunciado indecidible, pero eso no impide que haya otros, e incluso que muchos de ellos no sean autorreferentes (a ningún nivel). Un ejemplo bien conocido de esto último está dado por la hipótesis del continuo, que es indecidible con respecto a los axiomas de Zermelo-Fraenkel y que no es autorreferente.
¿Puede construirse un sistema axiomático consistente y completo? Si nos restringimos a las condiciones propuestas por Hilbert, la respuesta es no (es lo que demostró Gödel); si permitimos métodos de demostración más «amplios» (léase, por ejemplo, basados en una lógica de segundo orden) entonces sí (siempre que lógica de segundo orden sea realmente consistente, hecho que, aunque sea cierto, tal vez sea indemostrable).
25/10/2014
Gustavo gracias por contestar. Para tí los argumentos de Penrose son falaces (entiendo que, según su Shadows of the mind de 1994, Penrose se apoya en la reducción al absurdo y en el corte diagonal de Cantor. Dice que un algoritmo A(q,n) no puede ser matemáticamente consciente; puesto que no puede detener la computación C_q(n) [la acción de la q-máquina_de_Turing sobre el número n] ya que si C_k(k) se detiene entonces C_k(k) no se detiene). Tal vez, Gustavo, quieras colaborar de nuevo con Gaussianos y justificar la falacidad de esa argumentación gödeliana en otra entrada.
25/10/2014
Estimado Antonio (AKA «Un físico»). El argumento que estás citando está inspirado en la demostración de Turing de la imposibilidad de resolver el «Halting Problem», y no tanto en el teorema de Gödel (aunque es cierto que ambos resultados están estrechamente relacionados).
Todos los argumentos «gödelianos» (o «turingianos», si se me permite el término) que intentan demostrar que cerebro y computadora son esencialmente diferentes tienen a grandes rasgos la misma estructura y dicen más o menos así:
(1) Existe un problema P que la computadora no puede resolver.
(2) Ese mismo problema P sí es resoluble por la mente humana.
Luego, «mente» y computadora son esencialmente distintas.
La falacia suele consistir en que, mientras que (1) puede demostrarse rigurosamente, en cambio la afirmación (2) termina siendo una petición de principio (en parte porque no hay una clara definición de qué es la «mente» o la «conciencia», ni tampoco hay una clara delimitación de cuáles son los alcances del cerebro humano.)
Por ejemplo, un argumento «gödeliano» típico es éste: una computadora no puede demostrar que el enunciado G de Gödel es verdadero, mientras que la mente humana sí puede (de hecho, en el texto yo lo he demostrado). Pero aquí hay una falacia, porque el enunciado G es verdadero si y sólo si los axiomas propuestos son consistentes (es decir, si los axiomas son inconsistentes entonces G es falso). De modo que suponer que la mente humana puede demostrar que G es verdadero equivale a suponer que la mente humana es siempre capaz de decidir si un sistema de axiomas es consistente. Sin embargo, ha habido en el pasado sistemas de axiomas que durante años se creyeron consistentes (que fueron dados por consistentes por seres humanos) pero que finalmente resultaron no serlo (un ejemplo famoso es el sistema de Frege, otro ejemplo es el sistema «New Fundations» de Quine, y ha habido otros). Es decir, la mente humana se ha mostrado poco confiable a la hora de juzgar la consistencia de ciertos sistemas de axiomas, por lo que no podemos atribuirle así como así la capacidad de «saber infaliblemente» si G es verdadero o falso.
[En el texto yo demostré que G es verdadero, pero sólo bajo la suposición de que los axiomas del sistema eran verdaderos, suposición que implica su consistencia.]
La mente humana sí puede probar que «si el sistema es consistente entonces G es verdadero», pero eso también puede probarlo la computadora; de hecho, esa afirmación (que la implicación puede ser probada por una computadora) es la base de la demostración del segundo teorema de incompletitud de Gödel. En resumen, este argumento «gödeliano» no permite probar que la mente sea «superior» a la computadora, aunque tampoco permite probar lo contrario. El juego sigue en empate.
26/10/2014
Gustavo Piñeiro, eres grande. Muchas gracias por la aclaración: es de esas que te abren la mente.
27/10/2014
Muchas gracias Gustavo por tu aclaración y un saludo.
27/10/2014
Gracias a ustedes, Antonio y Miguel Ángel, por el interés. Muy cordiales saludos para ambos.
01/11/2014
Buenos días. Genial artículo. No entiendo bien, al hablar de El método de autorreferencia, cuando concluye: “Mi número de Gödel cumple la propiedad k”. Lo veo como si identificara la propiedad P con el número k. Si es así, sería correcto decir también: «Mi número de Gödel cumple la propiedad P»?
Aprovecho para recomendar el libro de Ed. Crítica «El reto de Hilbert» de Jeremy J. Gray.
02/11/2014
Es una errata. Debe decir: “Mi número de Gödel cumple la propiedad P”.
Gracias.
22/11/2014
Arreglada la errata.
22/11/2014
Gracias.
09/03/2015
No se si tenga algo que ver con el tema, pero me pregunto si este teorema demuestra que aunque contemos con la tecnología necesaria, no podemos por ejemplo hacer «una copia» de nuestro cerebro, ya que no podemos colocar de manera comprobable la posición de cada átomo junto con sus respectivos electrones en la exacta posición para generar una copia.
10/04/2015
¿La prueba de Gödel es parte del sistema axiomático en cuestión o está en un «metalenguaje»?
Porque en el primer caso demostrar en el sistema que G no es demostrable en el sistema, cuando G dice que no es demostrable en el sistema, es demostrar a G en el sistema, lo cual sería una contradicción.
Y en el segundo caso, ¿no permanece de todos modos la contradicción a nivel del metalenguaje? Éste debería admitir a la vez que G no es demostrable en el sistema y que G es demostrable en el sistema.
Muchas gracias.
10/04/2015
Bueno, claro, en el segundo caso G no sería demostrable en el sistema y la prueba de ello se haría en un metalenguaje, no en el sistema.
10/04/2015
Aunque también es cierto que dicen que Gödel logró formalizar la prueba en el lenguaje de las matemáticas ¿por tanto, en el lenguaje-objeto? ¿En el sistema?
Gracias.
10/04/2015
G es un enunciado del sistema, y el hecho de que no sea demostrable es probado dentro del sistema.
En el ejemplo que se esboza en la entrada, G dice “43 no se puede escribir como suma o resta de tres primos consecutivos”; la interpretación según la cual G dice «G no es demostrable» está en el metalenguaje, más aún, está fuera de la demostración en sí: esta lectura no es necesaria para la demostración de Gödel, sólo nos sirve para entender lo que Gödel hizo.
13/04/2015
Gracias por la respuesta ,ese detalle se me había escapado.
Con todo, me queda todavía esta dificultad: Supongamos que «G» dice «43 no puede ser escrito como suma o resta de tres números primos consecutivos».
Y que demostramos en el sistema que «G» no es demostrable en el sistema.
Eso equivale a decir que demostramos en el sistema que «43 no puede ser escrito como suma o resta de tres números primos consecutivos».
¿Pero no es eso demostrar a «G» en el sistema?
Porque ¿qué otra forma tendríamos de demostrar en el sistema que «G» no es demostrable en el sistema sino demostrando, según el ejemplo hipotético, que «43 no puede ser escrito como suma o resta de tres números primos consecutivos»?
Saludos cordiales.
13/04/2015
Se demuestra que “43 no puede ser escrito como suma o resta de tres números primos consecutivos” no es demostrable. Eso no equivale a demostrar G «en el sistema» porque la lectura «G no es demostrable» está fuera del sistema.
El teorema de Gödel está lleno de sutilezas de este tipo, la mejor forma de captarlas es leyendo la demostración que hizo Gödel.
14/04/2015
Sin duda, estas preguntas sólo se pueden resolver adecuadamente analizando la prueba misma.
Porque según su respuesta, se demuestra que la proposición 43 no puede ser escrita como suma o resta de tres números primos consecutivos.
Y eso quiere decir que la proposición «43 no puede ser escrito como suma o resta de tres números primos consecutivos» se puede escribir como suma o resta de tres números primos consecutivos.
Pero lo que pusimos entre comillas es justamente la proposición 43, que entonces sí puede ser escrita como suma o resta de tres números primos consecutivos.
Lo cual es una contradicción.
Gracias y saludos cordiales.
16/04/2015
Estás muy confundido Néstor, estás confundiendo el lenguaje objeto con el metalenguaje de manera flagrante. Obserba atentamente:
1) Hola no es una porposición de ocho palabras.
Sin duda es indecidible: no puede ser verdadera, pero tampoco puede ser falsa porque tiene 8 palabras. Pero…
2) «Hola no es una porposición de ocho palabras» es una proposición de ocho palabras.
Sin duda es verdadera y decidible. Además, nos indica que 1), aunque indecidible, pertenece al sistema.
¿Dónde está la contradicción? En ningún lado. La confusión de tu ejemplo es que no Gödelizas el enunciado:
3) “43 no puede ser escrito como suma o resta de tres números primos consecutivos” se puede escribir como suma o resta de tres números primos consecutivos
Su número Gödel es el 83 que sí se puede escribir como suma de tres números primos consecutivos, y por tanto resulta verdadera y decidible. Además nos indica que su lenguaje objeto pertenece al sistema objeto pese a ser indecidible.
16/04/2015
Gustavo Piñeiro, lo digo con las obras completas de Gödel sobre la mesa:
Gödel no demuestra la indecibilidad de G en el sistema, lo que demuestra es que siempre y cuando G fuera demostrado, también sería demostrado ¬G. Lo que traducido significa que G (y por consiguiente ¬G) pueden ser demostrados en sistemas previamente inconsistentes. Esto conlleva que en sistemas consistentes no puedan ser demostrados
Como se ve, la demostración de indecibilidad no se produce en el sistema.
17/04/2015
Gustavo, ¿puedes sustituir los dos últimos párrafos de mi comentario de las 22:37 por lo siguiente?
3) 41 no puede ser escrito como suma o resta de tres números primos consecutivos.
Sin duda es indecidible: no puede ser verdadera, pero tampoco puede ser falsa porque 47+53-59=41.
4) «41 no puede ser escrito como suma o resta de tres números primos consecutivos” se puede escribir como suma o resta de tres números primos consecutivos.
Recordemos que 3) es autoreferente por lo que se puede escribir como 47+53-59. Esto hace que sin la menor duda 4) sea verdadera y decidible. Además, nos indica que 3), aunque indecidible, pertenece al sistema.
Gracias
17/04/2015
La demostración de Gödel está «en el sistema», en el sentido de que puede traducirse a una sucesión de enunciados aritméticos que constituyen una demostración, basada en los axiomas del sistema, del enunciado «no existe un k que sea el código de una demostración de G», así como una demostración de «no existe un k que sea el código de una demostración de no-G». De hecho, Gödel usa esto como base para demostrar su segundo teorema de incompletitud.
Por otra parte, no me queda claro a qué apuntan las objeciones, si es que lo son. ¿La intención es probar que Gödel se equivoca? (lo cual no es cierto)? ¿O la intención es probar que yo no entiendo el teorema de Gödel? (lo cual, claro está, es posible, pero ¿para qué molestarse?).
17/04/2015
En mi caso la intención es entender cómo, en todo caso, Gödel no se equivoca.
En el comentario de Antonio, no me queda claro cómo la proposición “41 no puede ser escrito como suma o resta de tres números primos consecutivos” pueda no ser ni verdadera ni falsa, sobre todo cuando ahí mismo se dice que 47+53-59=41.
Según eso, sería verdadera.
Y si encima entendemos que la proposición en cuestión habla de sí misma, de modo que su número es 41, entonces tenemos que, si, como se dice,
«“41 no puede ser escrito como suma o resta de tres números primos consecutivos” se puede escribir como suma o resta de tres números primos consecutivos.»
entonces 41 se puede escribir como suma o resta de tres números consecutivos, con lo cual 41 es falsa.
Parece entonces que más que no ser ni verdadera ni falsa, es verdadera y falsa a la vez, lo cual es obviamente contradictorio.
Pero además, en la frase
«“41 no puede ser escrito como suma o resta de tres números primos consecutivos” se puede escribir como suma o resta de tres números primos consecutivos.»
Se está diciendo que 41 es demostrable, pues «poder ser escrito como suma o resta de tres números primos consecutivos» habíamos acordado que era «ser demostrable».
Y esa no es la manera, obviamente, de demostrar que 41 no es demostrable.
Saludos cordiales.
17/04/2015
Si uno tiene dudas acerca de la validez de la demostración de Gödel, o quiere entender bien a fondo las ideas de Gödel, la única forma es leer detalladamente la demostración que hizo Gödel. No sirve de nada discutir sobre el contenido de una breve nota de divulgación, o sobre ejemplos simplificados, que, necesariamente e inevitablemente, incurren en omisiones y simplificaciones. Es como intentar, por ejemplo, sostener que el teorema de Banach-Tarski quizás sea falso mostrando esferas de plastilina, pero sin discutir nunca la demostración que ellos hicieron.
17/04/2015
Como mi último comentario a esta entrada, con las disculpas por ser autorreferente, me permito sugerir que tal vez que este enlace pueda ser de ayuda para pensar algunas ideas (con las salvedades que indiqué en mi comentario previo sobre las notas de divulgación):
http://eltopologico.blogspot.com.ar/2011/02/la-autorreferencia-en-la-demostracion.html
18/04/2015
No, Gustavo, el artículo es muy bueno, simplemente quería matizar tu comentario de que «la indecibilidad del enunciado G es demostrado en el sistema» porque le llevaba a Néstor a interpretar que el sistema es inconsistente. Gödel elige una propiedad del sistema, y desde la nada, mediante la sintaxis del sistema construye un enunciado al que le niega dicha propiedad (por lo tanto, aún no sabemos si pertenece semánticamente al sistema, sólo que tiene su sintaxis). Acto seguido, (justamente son las citas que nos traes) demuestra que si G (condicional como una catedral de grande) es deducible, entonces necesariamente ¬G es deducible también (seguimos sin saber si es decidible en el sistema, tiene su sintaxis, pero semánticamente sólo puede pertenecer a él en el caso de que el sistema sea previamente inconsistente, la inconsistencia siempre es previa). Ni demuestra G, ni demuestra ¬G, sólo demuestra qué ocurre si uno de los dos es deducible. Por tanto, es más correcta la expresión que demuestra para el sistema, no en el sistema. (Insisto, sólo quería subsanar la mala interpretación que Néstor ha hecho de tu comentario)
Néstor, olvidémosnos de que 3) es indecidible en cualquier sistema omega-consistente, bla,bla,bla; y de que en un sistema contradicctorio es decidible tanto él como su contradictorio, porque parece que es en el campo en el que te quieres mover:
3) 41 no puede ser escrito como suma o resta de tres números primos consecutivos
Independientemente de cualquier sistema ¿es por sí solo verdadero, o es falso? Por un lado tenemos que no puede ser verdadera ya que 41 puede ser expresado como sumas o restas de tres números primitivos conscutivos. Lo lógico es pensar ahora que, si no es verdadera, entonces es falsa (PTE), pero va a ser que tampoco lo es. Y no puede ser falsa porque 3) sólo podría ser falsa en el caso de que 41 no pudiera ser escrito como suma o resta de tres números primos consecutivos (recuerda que: «41 no puede ser escrito como suma o resta de tres números primos consecutivos»=»41»), lo cual tampoco es el caso.
No es ni verdadera ni falsa, porque (tienendo dos interpretaciones y siendo el enunciado recursivo, las dos interpretaciones se referencian) en cuanto declaras su verdad en una, te ves obligado a declarar inmediatamente su falsedad en la otra (y viceversa). Lo explica muy bien Gödel en la parte 7 de su artículo «sobre la incompletud…» en el que explica los enunciados indecidibles con lenguaje natural (la paradoja de Epiménides, concretamente). Ante esta fatalidad, simple y llanamente hay que declararlos indecidibles: no sé si 3) es cierto o no, y no hay manera de saberlo. Todo sea por salvar el principio de no contradicción.
18/04/2015
A ver si resolvemos de una vez la duda de Néstor:
5) estoy mintiendo
Sólo (necesidad lógica) puede ser verdadera si es falsa.
Sólo (necesidad lógica) puede ser falsa si es verdadera.
Si concedes un valor de verdad (y contínuamente te empeñas en concederlo) automáticamente caes en contradicción. Si no queremos desprendernos del principio de no contradicción, sólo (necesidad lógica, de nuevo) podemos suspender el juicio y declararlo indecidible.
27/04/2015
Es como dice Gustavo, hay que leer directamente la prueba, ya lo dijimos. De todos modos voy a seguir el «link» que pone.
Aquí debe haber un error, no?:
«Y no puede ser falsa porque 3) sólo podría ser falsa en el caso de que 41 no pudiera ser escrito como suma o resta de tres números primos consecutivos (recuerda que: “41 no puede ser escrito como suma o resta de tres números primos consecutivos”=”41″), lo cual tampoco es el caso.»
Si el caso es que sí puede ser escrito así, y la proposición dice que no puede ser escrito así, la proposición entonces es falsa, no? Ojo que esto también es un condicional.
Además, si un juicio es verdadero en caso de ser falso, y falso en caso de ser verdadero, no es que sea indecidible: es que decididamente eso es una contradicción.
No es un problema de que no lo podamos saber, sino que en sí misma la cosa es contradictoria. Y entonces, tal vez la única forma de evitar la contradicción sea negar que aquello sea un juicio.
Saludos cordiales.
27/04/2015
No hay error, Néstor. Hay que tener en cuenta que 3) es un enunciado recursivo. Si dices que
3) 41 no puede ser escrito como suma o resta de tres números primos consecutivos
es falsa, entonces
4) “41 no puede ser escrito como suma o resta de tres números primos consecutivos” se puede escribir como suma o resta de tres números primos consecutivos.
ha de ser falsa (y recuerda que habíamos quedado que por recursividad 4) sí era verdadera) . Tu apresudadísima afirmación contradice el supuesto en el que te basas para decir que falsa. ¿Cómo puedes decir que es falsa si para decirlo tienes que admitir que es verdadera? Cualquier decisión cae en contradicción.
Por otra parte, dices que «decididamente eso es una contradicción» porque te empeñas en conceder un valor de verdad. Haciendo un poco de mala metafísica: yo tengo claro que las contradicciones son casos límite que no pueden existir jamás (no es posible que Dios pueda crear una piedra que no pueda levantar). Si yo digo que el sol gira en torno a la tierra y que el sol no gira en torno a la tierra (proposiciones contradictorias) no existe contradicción física (sólo una de ellas resultará cierta). Pero si yo digo que «yo miento» (entiéndase que sólo voy a pronunciar esta única proposición a lo largo de toda mi vida) y te empeñas en conceder valor de verdad o de falsedad a tal afirmación estás concediendo la posibilidad de que quepa una contradicción en el mundo, es decir, admites que las contradicciones no son límite de la existencia y que, por tanto, pueden existir. Yo prefiero admitir que la proposición «yo miento» no es decidible, antes de admitir que una contradicción existe. Si hay algo realmente cierto es el principio de no contradicción.
Con Russell y Whitehead, niegas que sean verdaderos enunciados. Gödel (y yo con él) dice que es una solución demasiado precipitada: Tales enunciados son juicios porque siguen la sintaxis,es decir son Enunciados Bien Formados. Por otra parte tienen significado porque al ser recursivos, si carecieran de significado, carecerían de significado toda expresión metalingüistica sobre ellos; como es evidente que éstas tienen significado (El ejemplo 4 y 2 tienen significado) tienene que tenerlo las primeras (ejemplo 1 y 3).
27/04/2015
Te cito a Gödel (traducción de Mosterín):
«Sea φ(w) la fórmula Πv(~(β(v,δ(w,w))) y sea p el número de φ(w). Ahora bien, φ(zᵖ) es la fórmula que resulta de reemplazar todas las apariciones libres de w en la fórmula de número p por zᵖ y tiene en consecuencia el número d(p,p). Por tanto, si φ(zᵖ) es deducible, entonces hay un k tal que k B d(p,p) [mío: «B» ha de leerse como «deducción» según explica Gödel un poco más arriba, es decir, K es una decucción del número d(p,p)]. Pero como δ(u,v) representa d(x,y) y β(u,v) representa x B y ^[Mío:»x es dedución de y], se sigue entonces que β(zᵏ, δ(zᵖ,zᵖ) es deducible. También es una propiedad de nuestro sistema formal que siempre que Πv(α(v)) es deducible, entonces para cada n es deducible α(zᶰ); en consecuencia, si φ(zᵖ) es deducible, entonces tanto ~(β(zᵏ, δ(zᵖ,zᵖ)) como β(zᵏ, δ(zᵖ,zᵖ) son deducibles y el sistema contiene por tanto una cotradicción. Concluimos entonces que φ(zᵖ) no es deducible a menos que el sistema sea contradictorio.
Nos planteamos ahora la pregunta de si ~φ(zᵖ) es deducible si el sistema no es contradictorio. Si el sistema no es contradictorio, entonces φ(zᵖ) no es deducible, como ya se ha visto. Como φ(zᵖ) es la fórmula de número d(p,p), tenemos que para todo k ¬k B d(p,p) [mío: ¬k es deducible de d(p,p)], y por tanto para todo k es deducible ~(β(zᵏ, δ(zᵖ,zᵖ))). Si ~φ(zᵖ), es decir ~(Πv(~(β(v,δ(w,w)))), fuese deducible, tendríamos que sería deducible una fórmula que afirma que no es el caso de que para todo k ~(β(zᵏ, δ(zᵖ,zᵖ))), y esto, junto con el hecho de que para todo k es deducible ~(β(zᵏ, δ(zᵖ,zᵖ))), hace que el sistema sea intuitivamente contradictorio […] Por tanto ni φ(zᵖ) ni ~φ(zᵖ) son deducibles a menos que el sistema sea contradictorio».
Espero que te sirva.
29/04/2015
Sobre la paradoja del mentiroso:
El principio de tercero excluido dice que algo es, o no es. Nada puede ni ser ni no ser algo.
A su vez, en toda proposición categórica se afirma o se niega algo.
Por tanto, hay cuatro posibilidades: o se afirma algo, y lo afirmado es, o se niega algo, y lo negado no es, o se afirma algo, y lo afirmado no es, o se niega algo, y lo negado es.
En los dos primeros casos, la proposición es verdadera, en los otros dos, falsa.
Por tanto, toda proposición es verdadera o falsa (principio de bivalencia).
Por tanto, si «Esta proposición es falsa», digamos, es una proposición, es verdadera o falsa. No puede ni ser verdadera ni ser falsa.
Pero en este caso, si la supuesta proposición es verdadera, es falsa, y si es falsa, es verdadera, y eso es una contradicción.
Por tanto, no es una proposición.
O sea, que tú dices que como es una proposición, no es contradictoria; yo digo que como sería contradictorio que fuese una proposición, y efectivamente lo contradictorio es imposible, entonces no es una proposición.
Para poder decir que sí es una proposición, hay que negar el principio de bivalencia arriba señalado, para negar éste, hay que negar el tercero excluido, porque hay que admitir que algo afirmado o negado por alguien puede ni ser ni no ser en la realidad.
Y para negar el principio de tercero excluido, hay que negar el de no contradicción, porque hay que aceptar la posibilidad de que algo ni sea ni no sea, lo cual implica que a la vez es verdad y no es verdad que no es, lo cual es contradictorio.
Saludos cordiales.
30/04/2015
No, lo que digo es que si existe (y hablo de existencia real, no mental), no puede ser contradicción.
Sea proposición o no (es evidente que sí lo es por lo expuesto), es algo que existe, luego no puede ser contradicción.
Por otra parte, para que exista contradicción es necesario dos proposiciones, p y ¬p unidas mediante un conjuntor. Yo sólo veo p. Lo mires por donde lo mires, las paradojas no son contradiccón. Si afirmas lo contrario estás insinuando que las contradiciones son posibles y reales.
Es como yo veo el asunto.
08/05/2015
La proposición es ante todo la proposición mental. Un conjunto de palabras no tiene porqué ser una proposición mental. Como dice Aristóteles, no es necesario que se piense todo lo que se dice.
Sin duda que «Esta proposición es falsa» existe como conjunto de palabras. Pero si existiese como proposición mental, sería verdadera una contradicción, lo cual es imposible.
La contradicción consistiría en que «Esta proposición es falsa» y «Esta proposición no es falsa» serían ambas verdaderas.
Porque si la primera es verdadera, la segunda a la vez es verdadera y falsa.
Por tanto, «Esta proposición es falsa» no corresponde a ninguna proposición mental.
Saludos cordiales.
08/05/2015
Y si «Esta proposición es falsa» es falsa, entonces es verdadera, y «Esta proposición no es falsa» es verdadera y falsa a la vez.
Saludos cordiales.
09/05/2015
Si es evidente que no puede ser verdadera y te empeñas en decir que es verdadera ¿quién introduce la contradicción?
Si es evidente que no puede ser falsa y te empeñas en decir que es falsa ¿quién introduce la contradicción?
Si ante un enunciado indecidible, te empeñas en hacerlo decidible ¿quién se contradice?
09/05/2015
Por otra parte, te recuerdo que estamos hablando de proposiciones recursivas que hace de ellas algo más que una simple fórmula en la mente; al hablar de ella misma la convierte inmediatamente en un hecho del mundo.
No es ni verdadera ni falsa, porque tiene dos interpretaciones (es proposición y hecho) y siendo el enunciado recursivo, las dos interpretaciones se referencian. En cuanto declaras su verdad en una, te ves obligado a declarar inmediatamente su falsedad en la otra (y viceversa). Lo explica muy bien Gödel en su artículo “sobre sentencias indecibles…” (cito de memoria)
17/12/2015
Tengo una duda tal vez un poco tonta.
Pensé en la siguiente analogía:
En el juego «piedra papel y tijeras» se tienen algunas reglas para dos jugadores A y B, piedra vence a tijera, tijera a papel y papel a piedra.
De donde se deduce el valor de la proposición «El jugador A gana».
Entonces cuando surge la situación Piedra-Piedra. No se puede asignar un valor de verdadero o falso a «El jugador A gana».
Si las reglas son los axiomas¿Este es un caso donde se aplica el teorema?
15/01/2016
Feliz año a todos.
Ivan, no vale porque dicho ejemplo carece de recursividad. Recuerda que los teoremas de incompletud de Gödel hacen referencia a sistemas omega-consistentes que cuenten con la posibilidad de proposiciones recurrentes.
En los sistemas axiomáticos normales, un enunciado pertenece al sistema si es un enunciado bien formado (EBF). Si un enunciado pertenece al sistema, su negación (enunciado contradictorio) también formará parte del sistema. Ahora bien, sólo uno de ellos será demostrable en el sistema y por tanto podremos decidir la verdad y la falsedad de ambos (suponiendo que el sistema sea consistente).
Ejemplo: en el caso de tu ejemplo decidimos que «el jugador A gana» es falso porque su contraria es demostrable en el sistema que has propuesto (Es fácil comprobar que «el jugador A no gana» es verdadero, por tanto, su contraria es falsa).
Justamente esto que podemos hacer en el ejemplo que propones (decidir la verdad de una proposición, o bien la de su contraria) es justamente lo que no podemos hacer en los sistemas que admiten la recursividad. En estos no somos capaces de demostrar la verdad de ninguno de los enunciados que forman el par (matizo, podemos demostrarlo sólo en sistemas no consistentes o contradictorios).
Perdona el retraso, pero es que acabo de ver tu pregunta ahora mismo.
03/09/2016
Me imagino que alguien me pidiera consejo; dice: «He construido una proposición (la designaré por ‘P’) en el simbolismo de Russell y mediante ciertas definiciones y transformaciones se la puede interpretar de modo que diga: ‘P no es demostrable en el sistema de Russell’. ¿No he de decir ahora de esa proposición que, por una parte, es verdadera, mientras que, por otra, es indemostrable? Pues, suponiendo que fuera falsa, ¡entonces es verdad que es demostrable! Y esto no puede ser. Y si está demostrada, entonces está demostrado que ella no es demostrable. De modo que no puede ser más que verdadera pero indemostrable».
03/09/2016
Wittgenstein, hay dos opciones, o la proposición es verdadera pero indemostrable, o tanto ella como su negación son demostrables. Ninguna de las dos opciones contradice tu razonamiento. En el primer caso estaríamos ante un sistema incompleto, y en el segundo en un sistema inconsistente.
Me imagino que lo que hace que esto sea difícil de entender es la segunda opción, tal vez un poco anti-intuitiva para quienes no están acostumbrados a las sutilezas de la lógica formal (es decir, casi todo el mundo).
Tal vez los teoremas de incompletitud de Gödel no darían pie a tanto debate si cuando se hace divulgación sobre ellos se formularan con un lenguaje más llano, aunque eso suponga dejar cosas en el tintero o admita matizaciones.
Por ejemplo, si dijéramos que Gödel demostró que «todo sistema axiomático lo suficientemente complejo es incapaz de probar su propia consistencia», mucha más gente entendería, más o menos, lo que afirman los teoremas de Gödel.
25/07/2017
Perdon, pero me lio entre el teorema de completitud de Godel y el de incompletitud, no percibo la diferencia. Alguna lectura recomendada?
05/10/2017
Tienes las obras completas de Gödel traducidas por Mosterín en Alianza editorial, pero son de difícil lectura. No recomiendo su lectura a quien no esté muy puesto en lógica.
A modo de explicación rápida: El teorema de completud es aplicable sólo a la lógica de primer orden. Viene a decir que estos sistemas son completos. El teorema de incompletud sólo es aplicable a un tipo concreto de lógica de segundo orden (metalenguaje si eres de letras): los sistemas recursivos omega-consistentes (sistemas autoreferenciales que prueban su propia consistencia). Viene a decir que estos sistemas o son incompletos o son contradictorios (=inconsistentes).
05/10/2017
No, no es eso.
Voy a poner en práctica mi propio consejo de explicar las cosas en lenguaje más llano.
Dejándome algún detalle en el tintero, un sistema lógico formal es un conjunto de axiomas y unas reglas de inferencia (unas reglas que nos dicen como razonar a partir de las premisas).
El teorema de completitud afirma que el sistema lógico formal «desnudo» (sin más axiomas que los púramente lógicos) es completo.
El problema surge cuando nuestro sistema lógico «desnudo» lo vestimos con los axiomas necesarios para describir la aritmética de los números naturales. En este caso Gödel probó que existen afirmaciones que no se pueden probar ni refutar… eso… o bien hemos construido un sistema inconsistente al añadir los nuevos axiomas.
06/10/2017
Acepto tu corrección, Sive, la lógica de segundo orden no es metalenguaje en absoluto, aunque en algunos casos especiales (como el del que estamos discutiendo) se le puede asemejar en parte (y sólo en parte).
Pero te recuerdo a la vez, que el problema no está en «los axiomas necesarios para describir la aritmética de los números naturales», sino en la recursividad. El propio Gödel compara la indecibilidad de ciertos teoremas con la antinomia del mentiroso, que carece de cualidades numéricas.
19/02/2019
Por favor, alguien que me responda de los genios que leo allí: dentro de las otras cosas sobre el tal teorema, ¿si lo de Gödel se demuestra, entonces la realidad existe? Esto, luego de compararlo con lo que dice Wittgenstein.