Teorema de Gödel

[Sailor Starruler]

En el momento en qué en la teoría de primer orden de los números complejos (vease, por ejemplo, Gödel para todos), G.Martinez, G.Piñeiro, añadimos (los diferenciamos como subconjjunto dentro de los números complejos)  los números naturales, ¿estamos usando lógica de 2º orden, sea bien mediante sentencias tipo x=1 , x=1+1, x=1+1+1,etc...o mediante calculo diferencial?, y entonces le afecta el teorema de Gödel,sea cuál sea la forma de introducir los números naturales. ¿Es esto correcto?

[Sailor Starruler]

En el momento en qué en la teoría de primer orden de los números complejos (vease, por ejemplo, Gödel para todos), G.Martinez, G.Piñeiro, añadimos (los diferenciamos como subconjjunto dentro de los números complejos)  los números naturales, ¿estamos usando lógica de 2º orden, sea bien mediante sentencias tipo x=1 , x=1+1, x=1+1+1,etc...o mediante calculo diferencial?, y entonces le afecta el teorema de Gödel,sea cuál sea la forma de introducir los números naturales. ¿Es esto correcto?

[Garubi]

Creo que es una buena idea utilizar las expresiones regulares si se quieren abordar informáticamente los productos de Gödel desde el conjuntismo.

Un saludo.

[Sailor Starruler]

Hola

Supuesta la consistencia de una teoría aritmetica T, el teorema de Gödel (versión sintáctica) demuestra que el enunciado es verdadero pero no demostrable desde los axiomas. Sin embargo, no podemos afirmar que una sentencia es verdadera si no lo hemos demostrado. ¿En qué se basa (que obviamente no pueden ser los axiomas de T) la demostración de que es cierto dicha sentencia de Gödel?¿Es metamatemática?

[Cristian C]

Hola

Supuesta la consistencia de una teoría aritmetica T, el teorema de Gödel (versión sintáctica) demuestra que el enunciado es verdadero pero no demostrable desde los axiomas. Sin embargo, no podemos afirmar que una sentencia es verdadera si no lo hemos demostrado. ¿En qué se basa (que obviamente no pueden ser los axiomas de T) la demostración de que es cierto dicha sentencia de Gödel?¿Es metamatemática?

Hola Sailor Starruler. La respuesta a tu pregunta la dió Gustavo Piñeiro en la primer página de este hilo:

En su demostración, Gödel construye (dentro de la aritmética) una afirmación cuyo significado es: "Yo no soy demostrable". Si la afirmación es falsa, sería una falsedad demostrable. Luego, es verdadera y es entonces una verdad no demostrable.

Permiteme digerirla un poco.

1. Evidentemente, tanto los axiomas como los enunciados demostrables, afirman propiedades verdaderas de la Aritmética.

2. Supon que encuentras la manera de escribir una propiedad aritmética que es exactamente equivalente a una afirmación que dice "esta propiedad no es demostrable"

3. Independientemente de que esa afirmación sea o no demostrable, solo puede ser verdadera o falsa.

3.1 Si la afirmación "esta propiedad no es demostrable" es falsa, entonces esa afirmación es demostrable. Ergo, es falsa y demostrable (lo anoté en negrita). Entonces tienes una propiedad demostrable de la aritmética (ese enunciado), que es falsa. Lo que contradice 1.

3.2 Por lo tanto, el enunciado "esta propiedad no es demostrable" es verdadera, y por lo que ella misma afirma, no demostrable.

He allí el enunciado verdadero no demostrable por el que preguntas.

Respecto a la prueba de Gödel, Gustavo Piñeiro agrega:

La demostración en sí consiste esencialmente en ver que esa afirmación puede construirse dentro del lenguaje de la aritmética.

Es decir, el trabajo difícil ha sido lo que yo he anotado alegremente en 2.

Saludos.

[Sailor Starruler]

Gracias por las aclaraciones, pero no contestas a mi pregunta, yo se que (supuesta consistente la teoría) el enunciado es verdadero y no demostrable en los axiomas de dicha teoría.

Pero sabemos que es verdadera ,luego ha tenido que ser demostrada (no se puede saber de algo el ser verdadero si no hay una demostraciónotra cosa es que no pueda hacerse en ninguna axiomática), pero el proceso que tu describes se puede considerar una demostración, pero no se muy bien, si no se basa  en axiomas, en que se puede basar. ¿Es una demostración metamatematica?

[argentinator]

Lo que yo entiendo es lo siguiente:

* Dada una fórmula (en la lógica de 1er orden), ella es sólo una lista ordenada de símbolos.
* A ciertas fórmulas se les da un "calificativo", por ejemplo, el ser "bellas", el ser "demostrables" y el ser "verdaderas".
* Cada calificativo se lo define de un modo completamente diferente.
* En algunos casos ocurre que una fórmula es verdadera, pero no demostrable.

La noción de "demostrable" es algo que "se define explicitamente".
Gustavo ya ha dado la definición de "demostrable" a lo largo de todo este thread.
También ha dado la definición de "verdadero".

Ambas definiciones son bien distintas y no tienen por qué coincidir.

No hay que confundirlo con las nociones que uno pueda tener de qué cosas son demostrables y qué no.
Cuesta digerirlo, pero así es.

"Demostrable" es una noción sintáctica: quiere decir que, partiendo de ciertos fórmulas llamadas axiomas, aplicando ciertas reglas de transformación de unas sentencias en otras, se obtiene una nueva sentencia S. Así, S se dice "demostrable".
Si no hay modo de "transformar" los axiomas en el enunciado S, mediante las reglas de deducción previamente estipuladas, entonces el enunciado S es "no-demostrable".

Este tipo de tarea puede hacerse mecánicamente por una computadora, ya que consiste en la operación de tomar una "cadena de caracteres" (que en informática se llama STRING) y realizar operaciones allí para obtener otra "cadena de caracteres" distinta, a la cual he indicado con la letra S.
Si esto es posible de hacerse, S es demostrable.

Para la noción de verdadero se procede por un camino diferente. A ciertas fórmulas se les asigna un valor verdadero o falso, porque sí, por mero decreto. A partir de ahí se define recursivamente cuáles otras fórmulas serán verdaderas o falsas.
Toda tal fórmula tiene asociado un "valor de verdad".

Ocurre que, mientras hay fórmulas que no son demostrables, sin embargo tienen un valor de verdad asignado.

Esto ocurre porque la demostrabilidad y la verdad-falsabilidad se definen por vías diferentes.

Si revisás la construcción de Gustavo vas a ver claramente cómo define cada una.

Uno también podría usar palabras distintas: en vez de "demostrable" podría decir "verde" y en vez de verdad-falseable podría decir "violeta", y en ese caso el teorema de Godel diría esto:

* Existe una fórmula que es no-verde pero que es violeta.

Aquí ya deja de haber aparentes contradicciones entre lo demostrable y lo verdadero, porque hemos quitado del camino las palabras "demostrable" y "verdadero" las cuales tienen connotaciones subjetivas para nosotros, y hacen que nos confundamos.

[Elius]

Gracias por las aclaraciones, pero no contestas a mi pregunta, yo se que (supuesta consistente la teoría) el enunciado es verdadero y no demostrable en los axiomas de dicha teoría.

Pero sabemos que es verdadera ,luego ha tenido que ser demostrada (no se puede saber de algo el ser verdadero si no hay una demostraciónotra cosa es que no pueda hacerse en ninguna axiomática), pero el proceso que tu describes se puede considerar una demostración, pero no se muy bien, si no se basa  en axiomas, en que se puede basar. ¿Es una demostración metamatematica?

Cuando hablamos del lenguaje formal PA, usamos un meta lenguaje. En ese meta lenguaje se "demuestra" que no es posible "DEMOSTRAR" en PA la sentencia G, si PA es consistente. Y que G es VERDADERA lo sabemos porque en el modelo standard de PA (la aritmética común, no formalizada) se puede comprobar que la demostración EN PA de G implica la demostración EN PA de ~G, con lo cual PA sería inconsistente.

Cuando se habla de demostración, hay que tener en cuenta los niveles de lenguaje; y cuando se habla de verdad, cuál es el modelo al que es relativa esa verdad. En matemática "verdad" es siempre "verdad en un modelo".


Saludos!

 

[argentinator]

No son ciertas algunas cosas que has dicho. Si se ha determinado que cierta formula F es Verdadera, eso no es una demostracion de F.   

[argentinator]

Y tampoco es cierto que algo es verdadero si y solo si existe una demostracion de ese algo.

[argentinator]

Justamente me he tomado el trabajo de usar las palabras verde y violeta par que se entienda lo que es una demostracion. Las formulas no importa si las estas llamando verdes o 'demostrables'. Hay una definicion mecanica de 'verde'. Estas confundiendo ese 'verde' con otros tipos de conceptos que son distintos.

[Cristian C]

Gracias por las aclaraciones, pero no contestas a mi pregunta, yo se que (supuesta consistente la teoría) el enunciado es verdadero y no demostrable en los axiomas de dicha teoría.

Pero sabemos que es verdadera ,luego ha tenido que ser demostrada (no se puede saber de algo el ser verdadero si no hay una demostraciónotra cosa es que no pueda hacerse en ninguna axiomática), pero el proceso que tu describes se puede considerar una demostración, pero no se muy bien, si no se basa  en axiomas, en que se puede basar. ¿Es una demostración metamatematica?

Hola Sailor. Tu duda fue mi duda alguna vez.

Como sabes, un enunciado es demostrable en un sistema axiomático cuando se sigue de los axiomas mediante las reglas de inferencia (puede escribirse con mucha más técnica definiendo primero "demostración").

¿Qué significa entonces que un enunciado sea "verdadero"?

1. Como bien sospechas la definición de verdadero es metaaxiomática.
2. Para los fines del teorema de Gödel, basta seber con precisión qué significa que un "enunciado aritmético" sea verdadero (no nos interesa el caso "para todo enunciado")
3. La definición de enunciado aritmético verdadero es precisa y unívoca, pero no se puede anotar en tres líneas porque involucra una construcción recursiva sobre los objetos del lenguaje formal.
4. La definición precisa de enunciado aritmético verdadero, la desarrolla Gustavo Piñeiro en este mismo hilo, desde el mensaje #83 (pag.5) en adelante.

Una vez establecida la diferencia entre el concepto de enunciado demostrable y el de enunciado verdadero, hay que usar también el llamado Teorema de Corrección, que dice simplemente que si en un sistema axiomático los axiomas son verdaderos entonces todos los teoremas (enunciados demostrables en ese sistema) serán también verdaderos.
Es interesante mencionar este teorema trival porque Gödel probó, justamente, que la inversa no se verifica (existen enunciados verdaderos no demostrables)

Una cosa interesante:
A priori podría parecer que tanto el concepto de "enunciado aritmético verdadero" como el de "enunciado demostrable" son metaaxiomáticos. Pero esto no es así.

El concepto de "enunciado aritmético verdadero" es inevitablemente metaaxiomático. No hay forma de expresar que un enunciado aritmético es verdadero, dentro de la teoría axiomática.
En cambio sí hay formas de expresar dentro de la teoría axiomática que un enunciado es demostrable. Lograr expresar algo del tipo "E es un enunciado demostrable" como propiedad aritmética ha sido uno de los grandes logros de Gödel.

Espero que esto aclare tus dudas.

Saludos.

[Sailor Starruler]

Gracias por la respuesta, Cristian. He estado mirando lo escrito por Gustavo, pero no logro entre sus expertas afirmaciones la definición de demostrable. El resto de cosas las entiendo bien. Quizás es que yo incluyo en el proceso de demostración cualquier proceso que nos demuestre que una proposición es verdadera, aunque no sea a partir de los axiomas de la teoría. Precisamente ahi está mi duda. No obstante, creo que en el caso de la aritmetica de Peano, tenemos intuitivamente las propiedades de la suma (conmutativa, asociativa) y el producto (conmutativa, asociativa y distributiva sobre la suma), y es de ahi de donde viene la "demostración" en el sentido que le doy yo a la palabra

Saludos

[Óscar Matzerath]

Hola,

Una puntualización que suele ser fuente de muchos malentendidos:

Una vez establecida la diferencia entre el concepto de enunciado demostrable y el de enunciado verdadero, hay que usar también el llamado Teorema de Corrección, que dice simplemente que si en un sistema axiomático los axiomas son verdaderos entonces todos los teoremas (enunciados demostrables en ese sistema) serán también verdaderos.
Es interesante mencionar este teorema trival porque Gödel probó, justamente, que la inversa no se verifica (existen enunciados verdaderos no demostrables)

El teorema de corrección dice lo siguiente (sólo con sentencias para evitar complicaciones innecesarias): si entonces . Es decir, si existe una demostración de con premisas en , entonces todo modelo de es también modelo de , esto es, para todo estructura M, si todas las sentencias de son verdaderas en M, entonces también es verdadera en M. Hay que notar que esto es un teorema (trivial) de lógica de primer orden, y no hace ninguna referencia a la aritmética ni nada parecido, sirve para cualquier conjunto de sentencias de primer orden que se te ocurra.

Con esta forma, la inversa SÍ se verifica (también lo probó Gödel, en su tesis doctoral, un año antes de sus teoremas de incompletitud), y este es uno de los primeros resultados profundos de la lógica de primer orden: el teorema de completitud. Este teorema dice que si entonces , es decir, si para toda estructura M donde todas las sentencias de son verdaderas, también lo es, entonces existe una demostración de con premisas en .

Teniendo esto en cuenta, el hecho de que no exista una teoría completa y recursiva para la aritmética implica que cualquier axiomatización recursiva admite otras interpretaciones además de la natural, , donde la sentencia de Gödel es falsa. Por ejemplo, esto quiere decir que hay estructuras donde todos los axiomas de Peano son verdaderos, pero la sentencia de Gödel es falsa (este es el punto de partida de la teoría de los modelos no estándar de la aritmética de Peano).

Por último, en los teoremas de incompletitud de Gödel es importante fijarse en la palabra recursiva, que es esencial y es lo primero que se suele olvidar la gente a la hora de enunciarlo. Existe una axiomatización completa de la aritmética: simplemente tomando como axiomas todas las sentencias de primer orden que son verdaderas en el modelo estándar , lo que se conoce como la teoría de , . Por supuesto esta axiomatización no es recursiva, por lo que no incumple el teorema de incompletitud.

Saludos

[argentinator]

Off-topic: Este hilo tiene larga data, y en un principio tuvo como protagonista indiscutible a Gustavo,
quien se encargó de la tarea de dar toda la demostración, junto con todas las definiciones previas, con gran detalle.

No quiero menospreciar la participación de los demás, ya que releyendo el thread he visto aportes muy interesantes de varios foristas.

No obstante, estoy seguro que muchas personas estarán interesadas principalmente en la demostración que realizó Gustavo.
Por eso me tomé la libertad de poner al pie de varios mensajes de Gustavo unas flechitas que enlazan mensajes más o menos consecutivos de los que Gustavo escribió.

Las flechitas sólo funcionan "hacia adelante" por ahora, y no están en todos los posts, sino sólo los más relevantes sobre la demostración del Teorema de Godel.
Presionando en esas flechas "hacia la derecha" se irán abriendo ventanas con los sucesivos posts en que Gustavo desarrolló su demostración.

Gustavo: no te pedí permiso porque no quería molestarte con este asunto, que es más bien "administrativo", jeje.

Los enlaces funcionan yendo a partir del más antiguo post de Gustavo en este thread.

[Elius]

Hola,

Una puntualización que suele ser fuente de muchos malentendidos:

Una vez establecida la diferencia entre el concepto de enunciado demostrable y el de enunciado verdadero, hay que usar también el llamado Teorema de Corrección, que dice simplemente que si en un sistema axiomático los axiomas son verdaderos entonces todos los teoremas (enunciados demostrables en ese sistema) serán también verdaderos.
Es interesante mencionar este teorema trival porque Gödel probó, justamente, que la inversa no se verifica (existen enunciados verdaderos no demostrables)

El teorema de corrección dice lo siguiente (sólo con sentencias para evitar complicaciones innecesarias): si entonces . Es decir, si existe una demostración de con premisas en , entonces todo modelo de es también modelo de , esto es, para todo estructura M, si todas las sentencias de son verdaderas en M, entonces también es verdadera en M. Hay que notar que esto es un teorema (trivial) de lógica de primer orden, y no hace ninguna referencia a la aritmética ni nada parecido, sirve para cualquier conjunto de sentencias de primer orden que se te ocurra.

Con esta forma, la inversa SÍ se verifica (también lo probó Gödel, en su tesis doctoral, un año antes de sus teoremas de incompletitud), y este es uno de los primeros resultados profundos de la lógica de primer orden: el teorema de completitud. Este teorema dice que si entonces , es decir, si para toda estructura M donde todas las sentencias de son verdaderas, también lo es, entonces existe una demostración de con premisas en .

Teniendo esto en cuenta, el hecho de que no exista una teoría completa y recursiva para la aritmética implica que cualquier axiomatización recursiva admite otras interpretaciones además de la natural, , donde la sentencia de Gödel es falsa. Por ejemplo, esto quiere decir que hay estructuras donde todos los axiomas de Peano son verdaderos, pero la sentencia de Gödel es falsa (este es el punto de partida de la teoría de los modelos no estándar de la aritmética de Peano).

Por último, en los teoremas de incompletitud de Gödel es importante fijarse en la palabra recursiva, que es esencial y es lo primero que se suele olvidar la gente a la hora de enunciarlo. Existe una axiomatización completa de la aritmética: simplemente tomando como axiomas todas las sentencias de primer orden que son verdaderas en el modelo estándar , lo que se conoce como la teoría de , . Por supuesto esta axiomatización no es recursiva, por lo que no incumple el teorema de incompletitud.

Saludos

En otro hilo surgió exactamente este tema, porque la formulación que hace Óscar (que es por supuesto correcta, y acorde con el main stream del pensamiento matemático moderno) es fuertemente contraintuitiva, y shockea bastante a las mentalidades afines al  constructivismo (y por qué no, tal vez nostálgicas del intuicionismo).
La forma tradicional, que no ha dejado de ser correcta, es enunciar el teorema de completitud de Gödel de la siguiente manera:

Toda fórmula lógicamente verdadera es demostrable en el cálculo puro de predicados, y toda fórmula demostrable del cálculo puro de predicados es lógicamente verdadera.

Como corolario, toda fórmula que es consecuencia lógica, en un modelo M de la teoría T, de un conjunto de fórmulas Gamma, es demostrable en el lenguaje de la teoría T a partir de Gamma:

implica

(Hoy en día se demuestra esto primeramente, y se saca la formulación original de Gödel como corolario para el caso en que Gamma es vacío.)

En esta formulación (si se quiere, histórica), la sentencia indecidible de Gödel (llamémosla SIG) es verdadera en el modelo estándar, pero no es consecuencia lógica de los axiomas de Peano (llamémoslos Ax(PA)):

pero

Extensionalmente esto es posible, porque las sentencias de un determinado conjunto  pueden ser verdaderas en un modelo, pero ser independientes, es decir, no compartir ninguna relación.

Y por lo tanto



En modo alguno intento desautorizar o enmendar lo que planteó Óscar, sólo dar una formulación más tradicional, y a mi juicio, más cercana a la intuición.   .

Saludos!

[Gustavo Piñeiro]

Hola argentinator,

Tanto tiempo... "Pasaba" por el foro y vi este mensaje:

me tomé la libertad de poner al pie de varios mensajes de Gustavo unas flechitas que enlazan mensajes más o menos consecutivos de los que Gustavo escribió

Te agradezco mucho el trabajo que te has tomado.

Un saludo cordial,

G.P.

[argentinator]

Bueno, ya que lo de Godel nunca lo termino de entender, por lo menos hago trabajo de oficina, que eso sí me sale 

Y a ver si pasás más seguido.
Ya Ivorra me estuvo machacando con el asunto de qué diablos es la metamatemática, lo cual es fundamental para creerse estos resultados de Godel.

Más allá de si me creo o no el proceder de la metamatemática, ahora por lo menos entiendo mejor qué se acepta en ese terreno.

Estuve haciendo unos programitas con todo esto, pero me llevó trabajo meter los axiomas en el programa, y lo dejé. Sin embargo siempre está la oportunidad de retomar el asunto.

De paso aprovecho para promocionar el blog del libro, que la gente debiera visitar:

http://godelparatodos.blogspot.com/

Nos vemos

[Gustavo Piñeiro]

Hola de nuevo,

Sobre la metamatemática...

Debemos el concepto de metamatemática a Hilbert. Correspondiendo vagamente al venerable término "metafísica", la "metamatemática" vendría a ser una ciencia cuyo objeto habría de buscarse en el conjunto de la matemática. Ahora bien, esta metamatemática no sería una disciplina filosófica, a diferencia de la metafísica, sino matemática, una teoría matemática.
La dificultad que ofrece esta determinación de la metamatemática salta a la vista. Si la metamatemática es una teoría matemática cuyo objeto consiste en la totalidad de la matemática misma, habría de contenerse a sí misma como objeto. La dificultad se soluciona con sólo advertir que, en este contexto, las palabras "matemático" y "matemática" no se refieren a lo mismo. Se trata, más bien, de una teoría matemática constructiva que tiene como objeto a la matemática entera, en la medida que ésta se presenta como una teoría axiomática.

Paul Lorenzen (1971), Metamatemática, Editorial Tecnos, Madrid. (Las itálicas en la cita son del autor.)

Desde hace algún tiempo me ronda la idea de discutir en el foro una demostración diferente del Teorema de Gödel (diferente, quiero decir, de la que se muestra en este hilo). Es una demostración que desarrolla Raymond Smullyan en su libro "Para imitar a un pájaro imitador" y que creo que podría interesarte porque (hasta donde entiendo) los conceptos que involucra son más fáciles de programar que los que aparecen en la demostración clásica de Gödel.

Seguramente en unos días me atreveré a tomar aire y zambullirme en este proyecto.

Un saludo!

G.P. 

[Fernando Revilla]

Seguramente en unos días me atreveré a tomar aire y zambullirme en este proyecto.

Por supuesto que será bienvenido.

Un saludo.