Autor Tema: Teorema de Gödel

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

02 Junio, 2009, 10:58 pm
Leído 162615 veces

Numerarius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 312
  • Karma: +0/-0
  • Sexo: Masculino
Hablo este hilo para hablar sobre el teorema de Gödel.

Bueno. No sabía como empezar. Russell descubrió una paradoja en la teoría de conjuntos (ya saben, la del conjunto de todos los conjuntos que no pertenecen a sí mismos). (Las proposiciones que se refieren a sí mismas suelen ser paradójicas. Por ejemplo: "Esta proposición no habla sobre el teorema de Gödel" ó  "El menor número que no se puede definir con menos de 15 signos").

Russell escribió con Witehead los Principia Mathematica, para librar a la matemática de paradojas. El libro de Russell establecía una jerarquía de lenguajes, la teoría de tipos, para evitar las proposiciones autorreflexivas.

Sin embargo, Gödel encontró una proposición que era verdadera pero no era demostrable en el sistema. El sistema era incompleto. No contenía todas las verdades.

La proposición venía a decir "Esta proposición no es demostrable en el sistema" (es decir, recordaba a la paradoja de Russell). Para construir esta proposición, Gödel recurrió a la "numeración de Gödel" (ya veremos lo que era esto).

04 Junio, 2009, 10:10 pm
Respuesta #1

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 545
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Efectivamente, Gödel se inspiró en las paradojas. Escribió que cualquier paradoja epistémica podría utilizarse para establecer un teorema de limitación.

Además de en la paradoja de Russell se inspiró en las del Mentiroso y en la de Richard.

La relación de la fórmula G de Gödel (que viene a decir de sí misma que es indemostrable en el sistema) con el Mentiroso es obvia: el Mentiroso dice de sí mismo que no es verdadero, G dice de sí misma que, por la que al sistema se refiere, ella no es verdadera. Nótese que esta restricción nos hace pasar de una paradoja a un teorema de la aritmética.

Gödel se inspiró en la paradoja de Richard (que es muy parecida a la diagonal de Cantor) para su demostración informal que precede a la demostración propiamente dicha en el artículo de 1931.

Richard había propiesto en 1905 esta paradoja: enumeremos en orden alfabético todas las definiciones de números reales entre 0 y 1 en la enumeración E*. Esta enumeración debe ser posible porque las expresiones del castellano son enumerables. Sea pnm el n-ésimo dígito del m-ésimo número definido en E*. Sea entonces el número real P

0' p11 p22 p33 p44 ... pnn ...

Sumemos ahora 1 a cada dígito de la expansión decimal de P (entendiendo que 9+1 = 0). Acabamos de definir un número real que no está definido en E*. Luego parece que no hay una enumeración de todas las definiciones de reales entre 0 y 1.

Como veis es esencialmente la diagonal de Cantor.

Tomemos todos los predicados expresables en el lenguaje formal de la aritmética y formemos con ellos una enumeración E =<P1, P2, P3, ...>. Entonces hay un predicado equivalente a 'x es tal que Px(x) no es demostrable en el sistema'. Sea Pk ese predicado. Entonces Pk(k) viene a decir que el número k está asociado en E a un predicado Pk tal que Pk(k) no es demostrable en el sistema. Es decir, esa fórmula viene a decir de sí misma que no es demostrable en el sistema.

Como veis, es análogo a la diagonal de Cantor que inspiró a Richard. Y tiene también un cierto parecido con la paradoja de Russell.

Claro, quedaba demostrar que efectivamente existe una fórmula como Pk(k) expresable en el lenguaje formal del sistema de la aritmética, de manera que se pudoesen construir esas fórmulas (en cierto sentido) autorreferentes dentro del lenguaje de la aritmética.

Numerarius nos contará.

Animo a cualquiera a que plantee eso que siempre quiso saber y nunca se atrevió a preguntar sobre el teorema de Gödel. A ver que podemos hacer entre todos.

Un saludo.

05 Junio, 2009, 03:10 pm
Respuesta #2

Gustavo Piñeiro

  • Visitante
Hola,

Mi nombre es Gustavo Piñeiro y soy coautor del libro "Gödel para Todos". Acabo de registrarme en el foro, éste es mi primer mensaje aquí. Si me lo permiten, me gustaría ayudar en la comprensión del teorema de Gödel en lo (poco o mucho) que pueda.

Saludos,

G.P.

<<                >>

05 Junio, 2009, 04:12 pm
Respuesta #3

mario

  • Administrador
  • Mensajes: 1,533
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Bienvenido, Gustavo.
 ;)


05 Junio, 2009, 06:51 pm
Respuesta #4

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 545
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola, Gustavo.

Me alegro de que estés por aquí. El libro no ha llegado a España que yo sepa, de modo que no sé muy bien qué aspectos del teorema de Gödel tratáis en él.

Pero permíteme plantearte una cuestión para romper el hielo. Ya que Numerarius presentó el tema a través de las paradojas y yo continué por ahí, tal vez sea oportuno preguntarte:

¿Cuál crees que es la relación última (por así decirlo) entre el teorema de Gödel y las paradojas?

Un saludo

05 Junio, 2009, 10:45 pm
Respuesta #5

Gustavo Piñeiro

  • Visitante
Hola,

Es muy cercana la relación entre el Teorema de Gödel y las paradojas. Por ejemplo, Gödel mismo dice que se inspiró, para su demostración, en la paradoja del mentiroso. La paradoja puede resumirse en esta pregunta: ¿La afirmación "Esta afirmación es falsa" es verdadera o falsa?

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.

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

(En los Principia Methematica, Russell dice que todas las paradojas nacen de la autorreferencia y que ésta debe ser evitada en el lenguaje lógico. Gödel va más allá y usa la autorreferencia de modo no paradójico -inspirado en una paradoja, pero no paradójico en sí- para demostrar su teorema.)

Saludos!

G.P.

PD: Según nos han dicho en la editorial, el libro se publicaría en España hacia fin de año.

05 Junio, 2009, 11:14 pm
Respuesta #6

Gustavo Piñeiro

  • Visitante
Hola nuevamente!

Al releer los mensajes del foro descubro que he escrito casi lo mismo que Numerarius, perdón por la repetición innecesaria.

Acerca de la autorreferencia. Creo que la diferencia entre la autorreferencia de la paradoja del mentiroso y la autorreferencia no paradójica de la demostración de Gödel es que la primera es una autorreferencia semántica mientras que la otra es sintáctica.

Me explico: "Esta afirmación es falsa" refiere a la verdad de la afirmación, que es una cualidad semántica ya que depende de su significado.

En cambio, "Esta afirmación no es demostrable" se refiere a una cualidad sintáctica, ya que, en el contexto del Programa de Hilbert, el que una secuencia de enunciados constituya, o no, una demostración depende de características sintácticas de esos enunciados (es decir, que no toman en cuenta el significado de los símbolos).

Un ejemplo simpático que ilustra esta diferencia es el siguiente.
Consideremos la oración:

"Esta afirmación tiene cinco palabras"

Es una afirmación verdadera. Pero su negación:

"Esta afirmación no tiene cinco palabras"

también es verdadera ¿Cómo es posible que una afirmación y su negación sean ambas a la vez verdaderas?

Saludos!

G. P.

06 Junio, 2009, 11:33 am
Respuesta #7

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 545
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
La distinción que hace Gustavo Piñeiro entre autorreferencia semántica y autorreferencia sintáctica es fundamental, me alegro de verla reflejada aquí porque la experiencia me dice que no todo el mundo la tiene tan clara. Es fundamental para entender por qué el Mentiroso es una paradoja y en cambio la sentencia de Gödel no lo es. Me consta que mucha gente no termina de entender esto con toda claridad.

Me gustaría insistir en ella introduciendo la distinción entre proposición y oración (o sentencia). Una oración o sentencia es un objeto puramente sintáctico, una ristra de símbolos que un artefacto puramente mecánico (una máquina deTuring) podría reconocer y manipular. Por el contrario, una proposición es un objeto semántico, es lo que afirmamos o negamos a través de una oración.

Por ejemplo, las siguientes expresiones son oraciones diferentes pero expresan, cada una en su interpretación usual, la misma proposición:

'la nieve es blanca'
'la neige est blanche'
'snow is white'
'der Schnee ist weiss'

En cambio, una misma oración expresa a veces dos o más proposiciones distintas; por ejemplo, la oración:

'todas las plumas pesan'

referida una vez a plumas de ave y otra a plumas estilográficas.

Una oración o sentencia no tiene en sí misma ningún significado: lo adquiere solamente a través de una interpretación. Así las sentencias de la aritmética formal adquieren significado y pasan a expresar proposiciones aritméticas sólo a través de la interpretación adecuada. Los lenguajes naturales son en realidad lenguajes ya provistos de una interpretación. Los lenguajes formales necesitan que se los provea de una interpretación si es que queremos que sus fórmulas expresen proposiciones.

Por eso la sentencia indecidible de Gödel (la llamaré 'G') es una sentencia, una fórmula, una ristra de símbolos, que sólo se convierte en una proposición cuando es interpretada. Si es interpretada de la manera estándar, expresa una proposición aritmética equivalente a

P)               'G no es demostrable en el sistema S'

donde S es el sistema formal de la aritmética (podemos asumir que es la aritmética de Peano de primer orden).

Es importante darse cuenta de que P no habla de sí misma sino de G, es decir, habla de una ristra de símbolos y de una propiedad sintáctica de esa ristra de símbolos, a saber, no ser un teorema de S. Conviene igualmente darse cuenta de que S es equivalente a una máquina de Turing que genera un conjunto de fórmulas; llamemos TS a una máquina equivalente a S. Entonces P viene a decir que una cierta ristra de símbolos no es un output de TS. P es como la proposición que propone Gustavo:

'esta oración tiene cinco palabras'

Esa proposición no habla de sí misma sino sólo de la oración que la expresa y de una propiedad sintáctica de esa oración.

Si una oración determinada tiene o no cinco palabreas, es un hecho bien definido. Paralelamente, si una ristra de símbolos determinada G es o no un output de una máquina de Turing determinada TS, eso es un problema matemático bien definido (equivalente a un problema aritmético), sobre el que no cabe paradoja alguna. Por tanto, o bien P es verdadera o bien P es falsa: hay hechos objetivos, hechos matemáticos que la hacen bien verdadera, bien falsa.

Comparad esta situación con la del Mentiroso:

M)                 esta proposición es falsa

Según yo lo veo, M es vacía, no expresa proposición alguna, no se refiere a ningún hecho bien definido (matemático o no matemático); es fácil ver que M está aquejada de circularidad, igual que el Veraz:

V)                esta proposición es verdadera

Con todo esto contrasta P, que consiste en afirmar que una determinada ristra de símbolos G no es un output de una determinada máquina de Turing TS; aquí no hay circularidad ninguna, nos estamos refiriendo a hechos objetivos, determinados con total independencia de nuestras afirmaciones sobre ellos.

Esta es la diferencia entre una paradoja y una proposición matemática.

Claro que entonces cabe preguntar: si la sentencia de Gödel es tan nítidamente distinta de la paradoja del Mentiroso ¿qué es exactamente lo que tienen en común?

Un saludo.


06 Junio, 2009, 12:53 pm
Respuesta #8

Fernando Revilla

  • Es más fácil engañar a alguien que convencerle de que ha sido engañado.
  • Administrador
  • Mensajes: 11,405
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • Las matemáticas son demasiado humanas (Brouwer).
    • Fernando Revilla
Estoy siguiendo este debate con mucha atención, excelente. Espero que salga mucha luz de él. Como ya comenté en otro hilo en el que intervino LauLuna, he "devorado" hasta la saciedad la demostración del teorema de incompletitud de Gödel (Logic for mathematicians de A.G. Hamilton). No tengo ningún reparo a la misma ni me ha quedado duda técnica alguna.

El problema es la interpretación como ya comenté de la propia esencia aritmética de la fórmula bien formada \( \mathcal{G} \) de Gödel y seguro que han corrido ríos de tinta acerca de esto. Quizás sería bueno esperar a que el debate llegara a un punto en el que tal vez pudiera yo aportar algo que está relacionado con los procesos dinámicos asociados a los números naturales que menciono en mi firma. Ahora creo que sería desviar algo el debate y no sería oportuno.

Por lo pronto valgan estos primeros comentarios para reflejar que se ha elegido uno de los temas más excitantes intelectualmente. Es posible que sea largo. Estaremos atentos y aprendiendo.

Saludos.    

06 Junio, 2009, 08:35 pm
Respuesta #9

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,338
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Antes de comenzar a discutir cosas, y sobre  todo preguntar, ya que mis dudas en este tema son más que mis certezas, quiero contribuir con un comentario histórico.

En torno al año 1900 varios matemáticos se vieron envueltos en arduas discusiones sobre los fundamentos de las matemáticas.
Se distinguen Poincaré, Russel, Hilbert, Cantor, Brower, Frege, entre otros.

Tengo acá (en casa) una edición es español del libro Fundamentos de la Geometría, de David Hilbert, editado en Madrid por CSIC.
En este libro se presenta una larga introducción histórica que explica cómo es que Hilbert se terminó interesando por la geometría euclidiana. Al parecer había muchas cuestiones vagas en la matemática de aquel tiempo, y así Hilbert se dispuso a escribir un libro dando axiomas sólidos, completos e inambiguos para la geometría plana.
Al parecer Pasch era un antecedente en la sistematización de los resultados de la geometría a partir de axiomas,
sin embargo el mismo Pasch era filosóficamente anti-axiomas, debido a que él estaba convencido de que la geometría debía basarse en la evidencia empírica, la naturaleza, para elaborar sus principios o enunciados, o lo que fuere.
Hilbert se alejó filosóficamente de esa postura, ya que para él la intuición no era de fiar en este terreno,
y es así que elaboró un sistema lógico-deductivo de la geometría, en el que no hubiera lugar a conceptos intuitivos.
Todo en la teoría de Hilbert se enuncia con proposiciones, ristras de signos, deducciones formales, implicaciones lógicas.
Ningún dibujo o interpretación intuitiva es necesaria, aunque él los haya utilizado con fines pedagógicos.

En su libro, Hilbert se cuestiona acerca de la independencia de los axiomas de la geometría.
Para ello, lo que hace es tomar uno de los axiomas de la teoría, digamos A, y lo reemplaza por su negación -A.
Los demás axiomas se dejan sin tocar.
Queda formado un nuevo sistema axiomático, y él prueba en cada caso que el sistema está bien constituido, exhibiendo un modelo. Y más aún, dicho modelo es un ejemplo distinto a la geometría clásica, o sea una geometría no euclidiana.
Si el axioma A hubiese dependido del resto de la lista de axiomas, entonces no se habrían obtenido teoremas propios de una geometría distinta. (Pensemos por ejemplo en negar la propiedad arquimediana).

En otro capítulo Hilbert plantea el tema de la no-contradicción de los axiomas entre sí.
Para ello, Hilbert exhibe un ejemplo de sistema que cumple los axiomas de la geometría: el sistema de los números reales (o pares de números reales... en fin).
Con ello puede afirmar que los axiomas de la geometría euclidiana son no-contradictorios siempre y cuando el sistema de los números reales, o sea la Aritmética, sea un sistema no-contradictorio.

Si un sistema A de axiomas no conduce a enunciados contradictorios, o sea, no permite afirmar que P y no-P son verdaderas al mismo tiempo, entonces se dice que el sistema A es consistente.
Hilbert probó una consistencia de la geometría que depende, es relativa respecto, de la consistencia de la Aritmética.

En el libro hay unos apéndices dedicados exclusivamente a la cuestión de la consistencia de la Aritmética, el Infinito, y los Fundamentos de la Matemática.
Se ve allí cómo Hilbert fue construyendo su teoría de la Axiomática, en la cual pretende basar toda la matemática.
Aquí él dice que los enunciados matemáticos han de usar un número finito de signos gráficos y un número finito ellos se escriben en un papel para expresar los enunciados matemáticos. También han de ser finitas las cadenas de silogismos empleadas en una demostración, y observa irónicamente que nadie ha podido escribir una demostración con infinitos de ellos.

Aparece en Hilbert la exigencia de finitud en los fundamentos mismos de la lógica como parte de los requisitos de exactitud y rigor en el trabajo matemático. Habla de unas cosas que llama ''los que son'' y ''los que no son'', que nunca entendí bien a qué se refiere, pero puede apreciarse que acepta en gran parte las aportaciones de Russell y Zermelo a la lógica matemática y su axiomatización.

En todo caso, Hilbert insiste en que tanto la Aritmética y la Lógica deben axiomatizarse, y sus teoremas deben probarse con métodos finitarios. También dice que ambas deben axiomatizarse simultáneamente, debido a que en la misma lógica aparece la necesidad de operar con números.

En sus conferencias él afirma que está convencido de la consistencia de los axiomas que él propone en su teoría de la Axiomática.
Hilbert se ve inquietado por la necesidad de probar si todo enunciado es demostrable o no, y habla entonces de una teoría de la demostración. Él cree que su teoría abrirá paso a contestar todas las preguntas matemáticas, y que la aritmética es consistente.
Otro concepto de Hilbert es el de que la no-contradicción de un sistema axiomático de cierta entidad matemática es suficiente para considerar que existe dicha entidad, mientras que otros matemáticos exigen que se exhiba un modelo, o sea un ejemplo al menos, que satisfaga esos axiomas. Se pide así que la teoría sea no-vacía.

Una pregunta que me hago en este punto es, si acaso el hecho de que una teoría sea no-contradictoria es equivalente al hecho de que exista al menos un modelo para dicha teoría. Creo haber leído por ahí que esto es un teorema metamatemático, pero no recuerdo ahora. Si alguien lo sabe...

Hilbert también hablaba de la metamatemática, aquella teoría que se ocupa de estudiar a la matemática misma desde ''afuera'',
y se ocupa de definir y  probar cuestiones relacionadas a fórmulas lógicas, enunciados de sistemas de axiomas lógico-matemáticos, y por último discutir si dichos axiomas son consistentes (sin contradicción interna) y completos (dadas una afirmación A y su negación -A, dentro del sistema dado de axiomas, o bien A es demostrable o bien -A es demostrable).

Luego por los años 1930 Godel probó sus famosos teoremas, siempre bajo el supuesto de que se trabaja en el programa formalista de Hilbert, o quizá dentro del logicismo de Russell. Hilbert reaccionó diciendo:

"Me gustaría manifestar que la opinión temporalmente extendida, de que ciertos resultados de Godel implican que mi teoría de la demostración no es posible, ha resultado ser errónea. De hecho, esos resultados demuestran únicamente que para obtener una prueba adecuada de la consistencia uno debe utilizar el punto de vista finitario de una forma más afinada de la que se necesita cuando se trata el formalismo elemental."

Cualquier corrección o comentario a lo que he expuesto será bienvenida.

En todo caso, me gustaría que alguien explique esta última cita que puse de Hilbert, porque la verdad es que no la entiendo.
Y una vez explicada, si creen que es cierto o no lo que Hilbert dice allí sobre los teoremas de Godel.

Por lo demás, deseo comprender enunciados y pruebas de los resultados de Godel de principio a fin, así que no los voy a dejar en paz hasta que todos los cálculos estén claros como el agua.

Sin embargo, he notado que hay dando vueltas en torno al teorema de godel dos tipos de dificultad: una de carácter conceptual o filosófica (o más o menos), y otra de tipo técnico (las pruebas mismas, que son algo difíciles).
Esto que ustedes mencionan acerca de la circularidad, las paradojas, etc., no son conceptos que estén bien definidos en alguna parte. Si bien uno puede definir con precisión clase, conjunto, contradicción, número, etc., no me parece que haya una definición de paradoja. Mientras uno anda paseando por la metamatemática procura evitar las paradojas, pero no sé si hay modo de establecer de un modo más preciso (quizá ustedes sepan de alguno) qué clase de objetos son.
Está también la importante discusión sobre sintaxis (signos vacíos formales) y semántica (significado, interpretación de los signos), que si bien estoy convencido de entender la diferencia entre ambos, cuando quiero aterrizar en Godelandia veo que me confundo de nuevo, irremediablemente.

En cuanto a las dificultades técnicas de las pruebas, ya veremos cuáles surgen.
En principio sólo tengo a mano el libro de Martínez/Piñeiro, pero no sé si basarme en ese libro para la demostración del teorema de Godel porque según tengo entendido dan una prueba algo ''alternativa'', basada en las máquinas de Turing (Piñeiro acaba de decirme que me equivoqué en esto, la prueba que dan ellos sigue las líneas de la original de Godel).
O sea, no me molesta para nada que hagan la prueba así, pero quizá los otros foristas tengan a mano una prueba del teorema de Godel en un formato más parecido al original, y entonces no nos vamos a entender del todo.
Pero confío en el amigo Piñeiro para que me diga hasta donde puedo usar su libro sin riesgo a confundir los distintos tratamientos.
¿Algún PDF en internet con la prueba?

Saludos