Autor Tema: Cómo encajar la sentencia INCOMPLETABLE de Gödel en un marco realm. consisten

0 Usuarios y 1 Visitante están viendo este tema.

17 Julio, 2020, 06:58 pm
Leído 695 veces

Elius

  • Aprendiz
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
Abstracto.
La razón por la cual todo intento de solucionar la incompletitud con el agregado de nuevos axiomas ha fracasado, es que una extensión de Rosser [1936] al teorema de Gödel [1931] establece que es posible construir una sentencia indecidible, no sólo para los sistemas equivalentes a Principia Mathematica de Whitehead y Russell con los axiomas de Peano, sino para cualquier extensión consistente de ellos. Y esto es así porque en cada extensión existirá un predicado de demostrabilidad, y será representable la función diagonal, que permite la auto aplicación sintáctica (auto referencia en la interpretación estándar). Pero esa función produce códigos de fórmulas incompletables (porque su desarrollo apunta a una secuencia infinita de fórmulas) en cualquier teoría de primer orden con axiomas equipotentes con los de Peano.
Que una sentencia sea verdadera en el modelo estándar no implica que sea completa (en un sentido que definiremos sintácticamente), puesto que cualquier malformación puede figurar como argumento de un predicado de no demostrabilidad, y así formar parte de una sentencia verdadera. También es posible construir infinitas sentencias trivialmente verdaderas, pero indecidibles, usando funciones definidas en forma circular, sin auto referencia.

Dejo el artículo, que está también publicado en Academia.edu:
Español
https://www.academia.edu/s/bbf03e2e87?source=link
Inglés
https://www.academia.edu/s/e7b9ad8ed8?source=link

17 Julio, 2020, 09:06 pm
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 1,699
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
He estado mirando un poco el artículo. Me cuesta entender la notación y la nomenclatura así que no sé si he entendido bien lo que quieres decir. ¿A qué te refieres exactamente con "variable dependiente" en una fórmula? No me queda muy clara la definición de fórmula completable. Si entiendo bien, es algo así como una fórmula equivalente a otra donde no aparezcan numerales que sean códigos de fórmulas (no terminales). Pero, ¿no puedes conseguir esto siempre sustituyendo un numeral \( n \) por un término del tipo \( m+k \)? Quizás no lo esté entendiendo bien.

Por otro lado, si he entendido bien la idea es que la sentencia de Gödel no es admisible (en cierto sentido) porque involucra un numeral que es el código de Gödel de sí misma. Pero a mí esto me parece mezclar sintaxis con semántica. Si yo te doy una sentencia en que aparece un numeral, ¿cómo sabes si lo estoy pensando como un código de Gödel de una fórmula o no? Quizás doy una sentencia que tiene un interés claro como enunciado de teoría de números pero por casualidad aparece el código de Gödel de una fórmula.

Un ejemplo: por el teorema de Matiyasevich la sentencia de Gödel es equivalente a la sentencia que expresa que una cierta ecuación diofántica (que se puede escribir explícitamente) no tiene solución. Yo creo que preguntarse si una ecuación diofántica tiene o no solución es un enunciado con un interés aritmético claro. ¿Cómo tratas esto? ¿Justificas de alguna manera que existen ecuaciones diofánticas de las que no es "lícito" preguntarse si tienen o no solución?

Por último, otra duda/comentario. ¿Existe algún algoritmo para determinar si una sentencia dada es o no completable? Dicho de otra manera, ¿es el conjunto de las sentencias completables recursivo? Porque si no, la utilidad de este concepto a la hora de tratar la incompletitud de un sistema axiomático sería bastante limitada, ya que al enfrentarte a una sentencia dada no tendrías manera de saber si es incompletable (y por tanto "no interesante") o no.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

18 Julio, 2020, 05:57 am
Respuesta #2

Elius

  • Aprendiz
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
Hola, gracias por leer el artículo y responder en forma muy interesante.
Te pido que me indiques qué libro tiene una notación y terminología que te satisfaga, para poder entendernos mejor. Habitualmente uso las de la memoria original de Gödel, Mendelson y Boolos. Pero si me indicas algún otro, veo si lo consigo.

Saludos.

18 Julio, 2020, 08:58 am
Respuesta #3

geómetracat

  • Moderador Global
  • Mensajes: 1,699
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Creo que me podría apañar con la notación de Mendelson y Boolos. Parte del problema es que tengo estas cosas de números de Gödel e incompletitud un poco oxidadas.

Con lo que más problemas terminológicos tengo es con lo de "variables dependientes". La única distinción que estoy acostumbrado a ver es entre variables libres y ligadas (por un cuantificador), pero me parece que no te refieres a eso. Me gustaría entender bien la definición de fórmula completa/completable, para lo cual parece importante entender qué es exactamente una "variable dependiente".

La ecuación más bonita de las matemáticas: \( d^2=0 \)

19 Julio, 2020, 06:16 pm
Respuesta #4

Elius

  • Aprendiz
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
He estado mirando un poco el artículo. Me cuesta entender la notación y la nomenclatura así que no sé si he entendido bien lo que quieres decir. ¿A qué te refieres exactamente con "variable dependiente" en una fórmula? No me queda muy clara la definición de fórmula completable. Si entiendo bien, es algo así como una fórmula equivalente a otra donde no aparezcan numerales que sean códigos de fórmulas (no terminales). Pero, ¿no puedes conseguir esto siempre sustituyendo un numeral \( n \) por un término del tipo \( m+k \)? Quizás no lo esté entendiendo bien.

Una variable es dependiente si está ligada por un cuantificador existencial y con cláusula de unicidad (valor único). Es la forma habitual de definir funciones, y en el sistema formal que nos ocupa, representar en el lenguaje formal las funciones recursivas. No pueden ser instanciadas, sino calculadas.

Es crucial para la noción de fórmula completa, pues en ésta todas las variables dependientes han sido reemplazadas por el valor calculado.

Una fórmula completable es aquella que tiene variables dependientes, pero es posible calcularlas dando algún valor a las variables independientes (libres o cuantificadas universalmente).

La fórmulas completas son recursivas, ya que simplemente se trata de verificar si no tiene variables dependientes, para lo cual se puede usar función beta.

Las fórmulas completables son aquellas que tienen variables dependientes, y pueden ser reemplazadas usando también la función beta.

Las fórmulas incompletables son aquellas que tienen un desarrollo infinito. Son detectables porque no son recursivas, ya sea porque tienen cuantificadores no acotados, o porque existe un problema de circularidad. En este último caso, es posible detectar el caso más simple, cuando para un valor del argumento, la definición de la función invoca nuevamente a la misma con el mismo argumento. Si la circularidad es más amplia, hay un problema similar al del Halting Problem.

   
Pero, ¿no puedes conseguir esto siempre sustituyendo un numeral n por un término del tipo m+k?

No, si se trata de una variable dependiente, o hay una función de desarrollo infinito.

Por otro lado, si he entendido bien la idea es que la sentencia de Gödel no es admisible (en cierto sentido) porque involucra un numeral que es el código de Gödel de sí misma. Pero a mí esto me parece mezclar sintaxis con semántica. Si yo te doy una sentencia en que aparece un numeral, ¿cómo sabes si lo estoy pensando como un código de Gödel de una fórmula o no? Quizás doy una sentencia que tiene un interés claro como enunciado de teoría de números pero por casualidad aparece el código de Gödel de una fórmula.

La sintaxis y la semántica están en el planteo mismo del problema que hace Gödel. En algunos casos están bien delimitadas, y en otros casos están, a mi criterio, mezcladas y confundidas. Cuando planteo que es una fórmula no completamente bien formada, es porque implica un desarrollo infinito en cualquier *interpretación* que se haga de los números de Gödel. Esto es semántica, pero bien delimitada y necesaria porque si un sistema formal carece de interpretaciones posibles no es consistente.
Respecto de si sabemos o no que un numeral es el código de una fórmula, eso ya cae dentro de la criptografía. Puede darse, tal vez, pero las hipótesis que plantea Gödel no preven tales extremos.

Un ejemplo: por el teorema de Matiyasevich la sentencia de Gödel es equivalente a la sentencia que expresa que una cierta ecuación diofántica (que se puede escribir explícitamente) no tiene solución. Yo creo que preguntarse si una ecuación diofántica tiene o no solución es un enunciado con un interés aritmético claro. ¿Cómo tratas esto? ¿Justificas de alguna manera que existen ecuaciones diofánticas de las que no es "lícito" preguntarse si tienen o no solución?

He leído el paper de Martin Davis (que participó, junto a Julia Robinson, Hillary Putnam y otros en la obtención de los resultados que usa Matiyasevich) sobre el décimo problema de Hilbert, y considero que se usan los resultados de Gödel para establecer el resultado final, pero no se obtienen nuevas evidencias para aclarar o ampliar los de Gödel.
En 1934, Gödel dictó una serie de conferencias en el IAS de Princeton, que yo cito en el artículo. La octava se titula "Equivalentes diofánticos de sentencias indecidibles".
Por supuesto que hay ecuaciones diofánticas que no tienen solución alguna, porque todas las soluciones posibles son racionales, reales o complejas. Pero no es algo "indecidible". Lo sepamos o no, tienen solución o no la tienen, y hay una afirmación sobre la ecuación que será verdadera o falsa y eventualmente comprobable, aunque no haya un método general para conocerla. Es diferente al caso de la sentencia indecidible, que no puede tener respuesta consistente alguna. Gödel no construye la ecuación diofántica "indecidible", se limita a "demostrar" su existencia. Y Matiyasévich tampoco la construye, se limita a usar el argumento de Gödel.

No sé si la sentencia de Gödel es "inadmisible". Como involucra conceptos y posturas filosóficas, y un paradigma tomado de la física cuántica (el principio de incertidumbre de Heisenberg, la interpretación de Copenhage y todo eso), seguramente a muchas personas les resultará útil y esclarecedora. Lo que pretendo mostrar es que es un laberinto muy interesante, hasta estéticamente (Douglas Hofstadter lo compara con Escher y con Bach), pero que no es forzoso caer en él. Es posible evitarlo, y seguir con una lógica más cercana a las realidades cotidianas.

20 Julio, 2020, 09:50 am
Respuesta #5

geómetracat

  • Moderador Global
  • Mensajes: 1,699
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Una variable es dependiente si está ligada por un cuantificador existencial y con cláusula de unicidad (valor único). Es la forma habitual de definir funciones, y en el sistema formal que nos ocupa, representar en el lenguaje formal las funciones recursivas. No pueden ser instanciadas, sino calculadas.

Vale, es decir que si tienes una variable cuantificada existencialmente en una sentencia y la teoría prueba que ésta es única, entonces la sustituyes por el único numeral. Creo que para que esto funcione bien hay que pedir que la teoría sea \( \omega \)-consistente, por eso.

Citar
Es crucial para la noción de fórmula completa, pues en ésta todas las variables dependientes han sido reemplazadas por el valor calculado.

Una fórmula completable es aquella que tiene variables dependientes, pero es posible calcularlas dando algún valor a las variables independientes (libres o cuantificadas universalmente).

La fórmulas completas son recursivas, ya que simplemente se trata de verificar si no tiene variables dependientes, para lo cual se puede usar función beta.

Las fórmulas completables son aquellas que tienen variables dependientes, y pueden ser reemplazadas usando también la función beta.

Las fórmulas incompletables son aquellas que tienen un desarrollo infinito. Son detectables porque no son recursivas, ya sea porque tienen cuantificadores no acotados, o porque existe un problema de circularidad. En este último caso, es posible detectar el caso más simple, cuando para un valor del argumento, la definición de la función invoca nuevamente a la misma con el mismo argumento. Si la circularidad es más amplia, hay un problema similar al del Halting Problem.
   
Vale, pero hay circunloquios para hablar del código de la sentencia de Gödel sin nombrarlo ni que sea una función. Por ejemplo, imagina que tienes una ecuación \( \phi(t)=0 \) cuyos coeficientes no son códigos de fórmulas incompletas cuyas soluciones son \( \sharp G \) y \( \sharp G' \) donde \( G' \) es una sentencia lógicamente equivalente a \( G \), pero distinta de \( G \). Entonces,
\( \exists z (\phi(z)=0 \wedge \neg Bew(z)) \)
es lógicamente equivalente a la sentencia de Gödel pero no aparece el número de una sentencia de Gödel por ninguna parte. Además, no puedes sustituir la \( z \) por un numeral porque no es única.
Es un ejemplo de que pueden pasar muchas cosas en una fórmula y te puedes inventar varias maneras de hablar de números sin nombrarlos.

La función beta tampoco la entiendo mucho. Por un lado, tal como se define parece que dado un código de Gödel de una fórmula busca Diag(y) y entonces hace lo que dice la definición. Esto hace que si tienes una fórmula obtenida del teorema del punto fijo, la función beta diverja.
Pero para definirla usas Diag(y) que es una fórmula fija. ¿Qué pasa si usas una fórmula distinta para definir Diag(y)? ¿La función beta ya no la detecta?
Por otro lado, dices "la auto referencia del teorema del punto fijo conduce a la inconsistencia del sistema formal". No lo entiendo y afirmo que no es verdad. Si lo fuera, todas las teorías aritméticas serían inconsistentes, pues en todas puedes usar el teorema del punto fijo. En cualquier caso, se ve que \( \beta \) aplicada a fórmulas obtenidas con el TPF diverge, pero eso no es ningún problema en funciones recursivas.

Citar
La sintaxis y la semántica están en el planteo mismo del problema que hace Gödel. En algunos casos están bien delimitadas, y en otros casos están, a mi criterio, mezcladas y confundidas. Cuando planteo que es una fórmula no completamente bien formada, es porque implica un desarrollo infinito en cualquier *interpretación* que se haga de los números de Gödel. Esto es semántica, pero bien delimitada y necesaria porque si un sistema formal carece de interpretaciones posibles no es consistente.
A ver, el teorema de Gödel puede que mezcle sintaxis y semántica en su interpretación y motivación, pero es sintáctico y todo lo constructivo que puede ser. Es decir, Gödel construye una sentencia \( G \) explícita, que afirma un cierto enunciado aritmético, de la que se puede calcular explícitamente su código de Gödel. Y dadas una supuesta demostración de \( G \) o de \( \neg G \) en el sistema formal tienes un procedimiento explícito para deducir una contradicción en la teoría formal. Puedes programar a un ordenador para que lo compruebe. No se le puede pedir nada más a la prueba de Gödel.

El principal problema que veo al tema este de las fórmulas completables, al margen de los problemas técnicos que pueda tener, que podrían ser solventables, es el siguiente. Si yo tengo una fórmula en la que aparece el código de la sentencia de Gödel, automáticamente será incompletable, aunque exprese identidades aritméticas y no lo piense como código. Es decir, habrá números proscritos. Por ejemplo, si el código de la sentencia de Gödel es \( 1254 \) la sentencia \( 1254 + 1 = 1255 \) sería incompletable. Pero no veo por qué esa sentencia debería ser más problemática que \( 1+1=2 \).

Citar
Respecto de si sabemos o no que un numeral es el código de una fórmula, eso ya cae dentro de la criptografía. Puede darse, tal vez, pero las hipótesis que plantea Gödel no preven tales extremos.
Hombre, criptografía no, una vez tienes la construcción de los códigos de Gödel hay un algoritmo sencillo para obtener la fórmula a partir del número.
Pero a lo que me refería es a lo que ponía antes: hay muchas fórmulas en las que aparece el código de la sentencia de Gödel, pero en realidad solo nos molestan unas pocas. Porque si no, hay "números proscritos" (que encima cambian si cambias la codificación) y eso no parece una buena idea a la hora de hacer aritmética.

Citar
Por supuesto que hay ecuaciones diofánticas que no tienen solución alguna, porque todas las soluciones posibles son racionales, reales o complejas. Pero no es algo "indecidible". Lo sepamos o no, tienen solución o no la tienen, y hay una afirmación sobre la ecuación que será verdadera o falsa y eventualmente comprobable, aunque no haya un método general para conocerla. Es diferente al caso de la sentencia indecidible, que no puede tener respuesta consistente alguna.
No, no, es exactamente el mismo caso que la sentencia de Gödel. Por supuesto que una ecuación diofántica o tiene soluciones o no (en el modelo estándar de los naturales), pero aquí no hablamos de lo que es verdad en los naturales sino de lo que es demostrable en una teoría aritmética. En este caso, hay una ecuación diofántica que no tiene soluciones en los naturales pero la teoría aritmética no es capaz de demostrarlo. En el caso de la sentencia de Gödel, es verdadera en el modelo estándar de los números naturales pero la teoría no es capaz de demostrarlo. No entiendo lo de "no hay respuesta consistente". Una teoría consistente ni demuestra ni refuta la sentencia de Gödel, igual que una teoría consistente ni demuestra ni refuta la existencia de soluciones de la ecuación diofántica.

Citar
Gödel no construye la ecuación diofántica "indecidible", se limita a "demostrar" su existencia. Y Matiyasévich tampoco la construye, se limita a usar el argumento de Gödel.
Hombre, no la construye explícitamente en el sentido de que no da la fórmula con sus numeritos, pero las demostraciones son totalmente constructivas y la puedes obtener explícitamente de ahí. De hecho me parece que alguien se dedicó a obtenerla explícitamente en el caso de ZFC.

Citar
No sé si la sentencia de Gödel es "inadmisible". Como involucra conceptos y posturas filosóficas, y un paradigma tomado de la física cuántica (el principio de incertidumbre de Heisenberg, la interpretación de Copenhage y todo eso), seguramente a muchas personas les resultará útil y esclarecedora. Lo que pretendo mostrar es que es un laberinto muy interesante, hasta estéticamente (Douglas Hofstadter lo compara con Escher y con Bach), pero que no es forzoso caer en él. Es posible evitarlo, y seguir con una lógica más cercana a las realidades cotidianas.

En esto precisamente es en lo que tengo más dudas. Todo intento de evitarla sentencia de Gödel también debería evitar otros problemas indecidibles de naturaleza puramente aritmética, como el tema de si una determinada ecuación diofántica tiene o no solución.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

20 Julio, 2020, 09:54 pm
Respuesta #6

Elius

  • Aprendiz
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
A ver, el teorema de Gödel puede que mezcle sintaxis y semántica en su interpretación y motivación, pero es sintáctico y todo lo constructivo que puede ser. Es decir, Gödel construye una sentencia \( G \) explícita, que afirma un cierto enunciado aritmético, de la que se puede calcular explícitamente su código de Gödel. Y dadas una supuesta demostración de \( G \) o de \( \neg G \) en el sistema formal tienes un procedimiento explícito para deducir una contradicción en la teoría formal. Puedes programar a un ordenador para que lo compruebe. No se le puede pedir nada más a la prueba de Gödel.
El teorema V, en la pág. 606 y 607 en la edición de van Heijenoort, establece que toda función recursiva primitiva es representable en el sistema formal. Esto es imprescindible para la demostración, y establece una semántica.
La elección de la correspondencia entre caracteres alfanuméricos y números de Gödel es también semántica.
No es que esto la invalide, sólo estoy diciendo que el uso que hago yo de la semántica se basa en la semántica establecida por el propio Gödel.
Luego apela a la semántica para dar relevancia a su resultado, diciendo que es verdadera en el modelo estándar. Porque si no fuera así, la sentencia que construyó no le importaría a nadie, porque nadie entiende más allá de que hay una sentencia indemostrable cuya interpretación es que hay otra sentencia indemostrable, y así siguiendo ad infinitum. Pero la verdad a la que se refiere es superficial: es verdad que una sentencia que implica su contraria no es demostrable, pero ¿eso es todo? ¿qué relación o propiedad numérica demuestra más allá de la trivialidad de decir que una sentencia contradictoria es indemostrable si el sistema es consistente?
Pero yendo a la incompletabilidad, es una malformación estructural. Cada fórmula y número de fórmula está bien formada/o, pero la estructura es circular.
Entonces la sentencia es simplemente descartable aunque sea superficialmente verdadera, como esas verdades triviales que menciono en el artículo, que afirman la indemostrabilidad de una malformación.
Igualmente el sistema es incompleto porque no puede demostrar la mala formación, salvo que se pueda descartar la función diagonal porque produce anidamientos infinitos.

Luego sigo con otros puntos.
 



21 Julio, 2020, 12:30 am
Respuesta #7

Elius

  • Aprendiz
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
El teorema V, en la pág. 606 y 607 en la edición de van Heijenoort, establece que toda función recursiva primitiva es representable en el sistema formal. Esto es imprescindible para la demostración, y establece una semántica.
En el libro de Mendelson (4ta. edición) está en la pág. 187, Proposition 3.24.

21 Julio, 2020, 09:14 am
Respuesta #8

geómetracat

  • Moderador Global
  • Mensajes: 1,699
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
El teorema V, en la pág. 606 y 607 en la edición de van Heijenoort, establece que toda función recursiva primitiva es representable en el sistema formal. Esto es imprescindible para la demostración, y establece una semántica.
La elección de la correspondencia entre caracteres alfanuméricos y números de Gödel es también semántica.
No es que esto la invalide, sólo estoy diciendo que el uso que hago yo de la semántica se basa en la semántica establecida por el propio Gödel.
Sí, estoy de acuerdo. La crítica que hago no es por las definiciones, que al margen de si el argumento es técnicamente correcto, estoy de acuerdo en que son igual de sintácticas que las de Gödel, sino en que tal como yo lo veo hay dos opciones: o cualquier fórmula en que aparezcan números que por casualidad son códigos de Gödel de aplicaciones del teorema de punto fijo son incompletables y por tanto, entiendo que son proposiciones "indeseables" en cierto modo (cosa que para mí es inaceptable pues como ya dije es equivalente a decir que hay números "indeseables" en aritmética) o bien necesitas introducir un criterio "semántico" cuando te enfrentas a una fórmula incompletable para saber si es inocente (como \( 1254+1=1255 \)) o si es una malvada sentencia que pretende expresar algo sobre el sistema formal.
En resumen, mi problema es más "filosófico" que matemático. Lo que dudo, al margen de la corrección técnica del argumento, es que la idea general sea satisfactoria.

Citar
Luego apela a la semántica para dar relevancia a su resultado, diciendo que es verdadera en el modelo estándar. Porque si no fuera así, la sentencia que construyó no le importaría a nadie, porque nadie entiende más allá de que hay una sentencia indemostrable cuya interpretación es que hay otra sentencia indemostrable, y así siguiendo ad infinitum. Pero la verdad a la que se refiere es superficial: es verdad que una sentencia que implica su contraria no es demostrable, pero ¿eso es todo? ¿qué relación o propiedad numérica demuestra más allá de la trivialidad de decir que una sentencia contradictoria es indemostrable si el sistema es consistente?
Tal como lo dices parece que el primer teorema de incompletitud de Gödel sea una chorrada. Yo lo veo muy diferente. De hecho, para mí que la senrencia de Gödel sea verdadera en el modelo natural es en cierta manera anecdótico, si fuera \( \neg G \) la verdadera todo funcionaría igual. La verdadera importancia de la sentencia de Gödel es que es un ejemplo explícito de sentencia que puedes construir en cualquier sistema formal (suficientemente potente) tal que \( \not\vdash_T G \) y \( \not\vdash_T \neg G \). Este es un resultado magnífico porque te dice que ningún sistema formal será lo suficientemente potente para decidir todas las sentencias aritméticas. Que sea verdadera o falsa en el modelo natural es irrelevante: es un resultado sobre las limitaciones de los sistemas formales. Dices "¿qué relación o propiedad numérica demuestra más allá de la trivialidad de decir que una sentencia contradictoria es indemostrable si el sistema es consistente?". Pero esto no es de lo que trata el teorema de Gödel. La sentencia \( 0=1 \) es contradictoria con los axiomas de la aritmética de Peano y por tanto es indemostrable. ¡Pero su negación sí es demostrable!
La sentencia de Gödel es muy distinta de este ejemplo en varios aspectos. Primero, el resultado clave es que ni \( G \) ni \( \neg G \) son demostrables si el sistema es consistente (esto no es estrictamente cierto, hay el rollo de la \( \omega \)-consistencia, pero puedes sustituir en todo lo que diré la sentencia de Gödel por la de Rosser). Pero es que, además, esto implica que ¡ni \( G \) ni \( \neg G \) son contradictorias! Puedes añadir \( G \) como axioma al sistema formal y seguir teniendo un sistema consistente. Y lo mismo si añades \( \neg G \) en lugar de \( G \). En el segundo caso, como estamos añadiendo como axioma una sentencia falsa en el modelo natural, el modelo natural dejará de ser modelo de los axiomas del sistema, pero el sistema formal seguirá siendo consistente.

Al margen de esto, que haya sentencias tales que ni ella ni su negación sean demostrables es un resultado importante y nada trivial. La prueba es que nadie lo hizo antes de Gödel y además hay muchos sistemas axiomáticos interesantes matemáticamente que son completos (como la geometría sintética).

Citar
Pero yendo a la incompletabilidad, es una malformación estructural. Cada fórmula y número de fórmula está bien formada/o, pero la estructura es circular.
Entonces la sentencia es simplemente descartable aunque sea superficialmente verdadera, como esas verdades triviales que menciono en el artículo, que afirman la indemostrabilidad de una malformación.
Igualmente el sistema es incompleto porque no puede demostrar la mala formación, salvo que se pueda descartar la función diagonal porque produce anidamientos infinitos.

Pero es que la diferencia con las dos fórmulas que pones al final:
\( \neg Bew(\sharp Form(\sharp malform)) \)
\( Bew(\sharp Form(\sharp Form(\sharp malform))) \)
donde \( malform \) es una fórmula mal formada cualquiera, es que aparte de ser verdaderas (como \( G \)) en el modelo natural, estas son demostrables (a diferencia de \( G \)).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

21 Julio, 2020, 04:20 pm
Respuesta #9

Elius

  • Aprendiz
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
Sí, estoy de acuerdo. La crítica que hago no es por las definiciones, que al margen de si el argumento es técnicamente correcto, estoy de acuerdo en que son igual de sintácticas que las de Gödel, sino en que tal como yo lo veo hay dos opciones: o cualquier fórmula en que aparezcan números que por casualidad son códigos de Gödel de aplicaciones del teorema de punto fijo son incompletables y por tanto, entiendo que son proposiciones "indeseables" en cierto modo (cosa que para mí es inaceptable pues como ya dije es equivalente a decir que hay números "indeseables" en aritmética) o bien necesitas introducir un criterio "semántico" cuando te enfrentas a una fórmula incompletable para saber si es inocente (como \( 1254+1=1255 \)) o si es una malvada sentencia que pretende expresar algo sobre el sistema formal.
Bertrand Russell, con su teoría de los tipos, intentaba excluir las sentencias auto referentes de su sistema, sólo para evitar las consecuencias que tuvo su paradoja, que destruyó por contradictoria la teoría de Frege. Pero muchos interpretaron que había una especie de esañamiento filosófico en esta restricción, y salieron en defensa de la autoreferencia. No se trataba de eso, Russell quería solamente evitar las contradicciones.
Yo no digo que las sentencias incompletables sean "indeseables" en un sentido absoluto y general, sólo digo que son un anidamiento potencialmente infinito de códigos de fórmulas anidadas.
Si esos mismos números aparecen en otro contexto, pueden simplemente no tener una referencia respecto de sentencias lógicas, o pueden tenerla sin regresión infinita, como sucede con cualquier procedimiento matemático o algoritmo de informática. Y en ese caso no veo ninguna objeción.

21 Julio, 2020, 04:52 pm
Respuesta #10

Elius

  • Aprendiz
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
En resumen, mi problema es más "filosófico" que matemático. Lo que dudo, al margen de la corrección técnica del argumento, es que la idea general sea satisfactoria.
No creo de ninguna manera que el teorema de incompletitud sea intrascendente. Aún mirándolo como una especie de nueva y sofisticadísima paradoja, hay que pensar que las paradojas de Zenón de Elea tuvieron de la cabeza a filósofos y matemáticos durante más de 2000 años. Sólo se resolvió su misterio cuando aparecieron las teorías sobre las series infinitas en el siglo XIX.
Lo que intento mostrar es algo más amplio que lo que se ve en el artículo, y es lo siguiente: el teorema de incompletitud es el predecesor, y en cierto modo equivalente al teorema de la irresolubilidad del Halting Problem de Turing. Este último trata sobre sus máquinas virtuales, Gödel sobre las funciones recursivas. Incluso hay teoremas donde está muy clara esa similitud, ver Mendelson (4ta. ed.), pág. 325 en adelante, "Unsolvable Problems". Se trata de una anomalía del sistema formal para tratar las funciones recursivas, especialmente con respecto a los desarrollos infinitos y la circularidad. El sistema falla porque la sentencia indecidible es incompletable, como la máquina universal de Turing falla en detectar auto-referencia y circularidad. No hay una sentencia "correcta" que el sistema no puede catalogar como teorema o anti teorema, de la misma manera que en Turing no hay una máquina "correcta" que la máquina universal no catalogue. Es en las máquinas anómalas donde falla.

 

21 Julio, 2020, 07:53 pm
Respuesta #11

geómetracat

  • Moderador Global
  • Mensajes: 1,699
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Sí, todos los resultados estos están bastante relacionados. Una manera general de verlo es que existen conjuntos recursivamente enumerables que no son recursivos. En efecto, el problema de la parada de Turing te dice que el conjunto de (números de) máquinas de Turing \( M_n \) para las que \( M_n(n) \) para no es recursivo (pero sí recursivamente enumerable: basta con ejecutar la máquina). De manera similar, la incompletitud de sistemas formales está relacionada con que el conjunto de números de sentencias demostrables en un sistema axiomático no es recursivo (pero sí recursivamente enumerable).

De hecho, ahora me he dado cuenta del siguiente argumento que implica que la clase de sentencias que son indecidibles en el sistema axiomático (no son ni demostrables ni refutables) no puede ser recursiva. Es decir, no puede haber ningún algoritmo que te diga si una fórmula es indecidible o no. En efecto, si existiera tal algoritmo existiría un algoritmo para saber qué sentencias son demostrables, que ya sabemos que no existe. Dada una sentencia cualquiera basta ejecutar el primer algoritmo para ver si es indecidible o no, y si sale que no es indecidible te basta con ir enumerando los teoremas del sistema axiomático hasta que salga la sentencia o su negación (una de las dos debe salir seguro porque sabes que no es indecidible).

Es un argumento interesante porque aunque no desmonta del todo lo que pretendes hacer sí muestra sus límites. Si das un criterio cualquiera comprobable algorítmicamente de fórmula "mala" que intente capturar las sentencias indecidibles, como tu noción de fórmula incompletable, o bien va a haber fórmulas indecidibles que no son "malas" o bien va a haber fórmulas "malas" que son decidibles.

Algo parecido se aplica a lo que dices al final sobre máquinas de Turing. La cuestión es que no hay un criterio operativo que te permita decidir si una máquina es "correcta" o "anómala".
La ecuación más bonita de las matemáticas: \( d^2=0 \)

21 Julio, 2020, 10:39 pm
Respuesta #12

manooooh

  • Matemático
  • Mensajes: 2,989
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Qué interesante debate están armando :aplauso: :aplauso:. Vaya por delante que mezcla distintas ramas de la matemática y computación, lo cual hace que sea más que interesante.

Tengo una duda más bien básica, espero que puedan entenderla. Cuando hablan de "Puedes programar a un ordenador para que haga tal demostración", ¿se debe interpretar metafóricamente o literalmente?

Porque claro, nunca estuve en contacto con un algoritmo así pero ni de cerca (a duras penas puedo entender los algoritmos de ordenación como bubble sort, entre otros), pero claro, ¿cómo se determina el tiempo computacional? ¿Cuáles son las entradas y qué se espera por salida? ¿Se tratan de algoritmos teóricos (de ahí su "tiempo computacional exponencial/polinomial/logarítmico") o ya están puestos en marcha?

Saludos

22 Julio, 2020, 12:31 am
Respuesta #13

geómetracat

  • Moderador Global
  • Mensajes: 1,699
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Tengo una duda más bien básica, espero que puedan entenderla. Cuando hablan de "Puedes programar a un ordenador para que haga tal demostración", ¿se debe interpretar metafóricamente o literalmente?

Bueno, lo que dije es que puedes programar un ordenador para comprobar tal demostración. Hablaba metafóricamente, pero realmente puedes programarlo si quieres, no debería ser muy difícil. A lo que me refería es que si me das una demostración en el sistema formal de \( G \) puedo decirte como alargarla hasta la demostración de una contradicción.

Citar
Porque claro, nunca estuve en contacto con un algoritmo así pero ni de cerca (a duras penas puedo entender los algoritmos de ordenación como bubble sort, entre otros), pero claro, ¿cómo se determina el tiempo computacional? ¿Cuáles son las entradas y qué se espera por salida? ¿Se tratan de algoritmos teóricos (de ahí su "tiempo computacional exponencial/polinomial/logarítmico") o ya están puestos en marcha?
Todos los algoritmos de los que he hablado en el último mensaje son teóricos. Es decir, lo único que me interesa es si existe o no un algoritmo para resolver un problema determinado, no me importa su complejidad, podría tardar más tiempo que la edad del universo.

Hay varios niveles de análisis de algoritmos. El más general es el que corresponde a la teoría de la recursión (o teoría de la computabilidad). Esta teoría se preocupa (al menos en primer instancia) de determinar los problemas que son resolubles algorítmicamente y los que no, sin preocuparse por el tiempo de ejecución, limitaciones de memoria o detalles de implementación. Es lo que es teóricamente posible, disponiendo de tiempo y memoria infinitos.
Un segundo nivel corresponde a la teoría de la complejidad. Esta estudia clases de complejidad computacional de algoritmos atendiendo al tiempo necesario de ejecución o al espacio necesario, pero siempre a "gran escala". Por ejemplo, estudia las clases P, NP, etc. Pero no se preocupa de encontrar cotas precisas, da igual que un algoritmo sea \( O(n^2) \) o \( O(n^3) \), basta con que sea computable en tiempo polinomial.
Por último está la algorítmia o el análisis de algoritmos, que se dedica a encontrar los mejores algoritmos posibles para resolver un problema y a encontrar cotas (si puede ser óptimas) sobre el tiempo de ejecución. Aquí es donde entran los algoritmos de ordenación y sus cotas que mencionas.

Pero como ya he dicho, a efectos lógicos solamente importa el primer nivel (si algo es resoluble algorítmicamente o no).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

23 Julio, 2020, 01:42 am
Respuesta #14

Elius

  • Aprendiz
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
Tengo una duda más bien básica, espero que puedan entenderla. Cuando hablan de "Puedes programar a un ordenador para que haga tal demostración", ¿se debe interpretar metafóricamente o literalmente?
Hola, manooooh.
Hay muchos algoritmos, de dos tipos: verificadores de demostraciones, y los que intentan encontrar una demostración. Por supuesto, el "demostrador" siempre tiene que estar complementado por un verificador.
Los verificadores son muy buenos. Pero los "demostradores" no son muy eficaces, porque usan búsquedas sofisticadas, pero no matemáticamente probadas para encontrar deducciones.
Los algoritmos pueden ser impresionantes, como para ganarle al ex campeón mundial de ajedrez Garry Kasparov, o al campeón de Go, pero no encontrando demostraciones. Ni qué hablar de proponer y probar un teorema.
Es que para eso tiene que haber previamente un procedimiento de decisión creado matemáticamente: Hilbert planteó esto, y es lo que se conoce como el Entscheidungsproblem, problema de la decisión: https://plato.stanford.edu/entries/computability/.
Church y Turing demostraron que no era posible un procedimiento así para la lógica de primer orden, y Gödel para la aritmética de Peano. Pero lo que resulta un poco exagerado es que luego de esto, pocos matemáticos quisieron dedicarse a buscar procedimientos de decisión en campos más acotados. Si se restringe la lógica a predicados de dos variables, por ejemplo (la aritmética usa sólo el predicado de igualdad, dos variables), o la aritmética sin todas las operaciones que agrega Gödel, podría haberlo.

23 Julio, 2020, 11:25 am
Respuesta #15

geómetracat

  • Moderador Global
  • Mensajes: 1,699
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Pero lo que resulta un poco exagerado es que luego de esto, pocos matemáticos quisieron dedicarse a buscar procedimientos de decisión en campos más acotados. Si se restringe la lógica a predicados de dos variables, por ejemplo (la aritmética usa sólo el predicado de igualdad, dos variables), o la aritmética sin todas las operaciones que agrega Gödel, podría haberlo.

Sobre la decidibilidad de fragmentos de la lógica de primer orden, recordaba que había resultados clásicos (de antes del resultado de Church y Turing, creo) de decidibilidad de algunos fragmentos (sólo con predicados monádicos, o sentencias que en su forma prenexa solamente pueden aparecer cuantificadores \( \exists^* \forall^* \)).

Me he dedicado a buscar un poco por internet cómo está la cosa hoy en día y parece que se ha hecho mucho desde tiempos de Gödel y ahora se entiende bastante bien qué fragmentos son decidibles y cuáles no. He encontrado un libro de 1997, "The classical decision problem" de Börger, Grädel y Gurevich, que está dedicado a explicar todos estos resultados.
Incluso he encontrado una tesis doctoral de 2019 que trata de estos temas:
http://people.mpi-inf.mpg.de/~mvoigt/files/Dissertation_with_hyperref.pdf
Es decir, que parece que es un tema en lo que se sigue haciendo investigación.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

23 Julio, 2020, 10:17 pm
Respuesta #16

Elius

  • Aprendiz
  • Mensajes: 372
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
    • Bypassing Gödel
Muy buena información, geómetracat.
Sí, sabía de algunas investigaciones, pero el libro que mencionas es muy valioso. La tesis también es interesante.
En la universidad Humboldt de Berlín el Dr. Timm Lampert está desarrollando un FOL-Decider, procedimiento de decisión para la lógica de orden 1, desafiando a Church y Turing:
http://www2.cms.hu-berlin.de/newlogic/webMathematica/Logic/decide.jsp
Me pasó algunos papers por si quería colaborar, pero la notación que emplea me resulta ilegible.