10/12/2019, 01:20:44 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1] 2 3 ... 17   Ir Abajo
  Imprimir  
Autor Tema: Teorema de Gödel  (Leído 141876 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Numerarius
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 319


Ver Perfil
« : 02/06/2009, 05:58:15 pm »

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).
En línea

LauLuna
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

España España

Mensajes: 541


Ver Perfil WWW
« Respuesta #1 : 04/06/2009, 05:10:54 pm »

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.
En línea
Gustavo Piñeiro
Visitante
« Respuesta #2 : 05/06/2009, 10:10:07 am »

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.

<<                >>
En línea
mario
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.302



Ver Perfil
« Respuesta #3 : 05/06/2009, 11:12:54 am »

Bienvenido, Gustavo.
 :guiño:

En línea
LauLuna
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

España España

Mensajes: 541


Ver Perfil WWW
« Respuesta #4 : 05/06/2009, 01:51:47 pm »

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
En línea
Gustavo Piñeiro
Visitante
« Respuesta #5 : 05/06/2009, 05:45:30 pm »

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.
En línea
Gustavo Piñeiro
Visitante
« Respuesta #6 : 05/06/2009, 06:14:18 pm »

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.
En línea
LauLuna
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

España España

Mensajes: 541


Ver Perfil WWW
« Respuesta #7 : 06/06/2009, 06:33:42 am »

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.

En línea
Fernando Revilla
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 10.550


Las matemáticas son demasiado humanas (Brouwer).


Ver Perfil WWW
« Respuesta #8 : 06/06/2009, 07:53:40 am »

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 [texx]\mathcal{G}[/texx] 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.    
En línea

argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.282

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #9 : 06/06/2009, 03:35:32 pm »

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
En línea

Gustavo Piñeiro
Visitante
« Respuesta #10 : 06/06/2009, 05:00:09 pm »

Estimado argentinator,

Acerca de la cita de Hilbert, se refiere a lo siguiente: en el momento en que Gödel demostró su teorema (lo demostró en 1930 y lo publicó en 1931) todavía no se había dado una definición precisa de "método finitario", por lo que no quedaba claro si el teorema de Gödel se aplicaba a todos los métodos finitarios posibles. El mismo Gödel comenta esta circunstancia en su artículo, diciendo que tal vez había métodos permitido por el programa de Hilbert que su demostración no llegaba a abarcar.

Cuando, en 1936-1937, Church y Turing definen rigurosamente el concepto de algoritmo, quedó claro entonces que la demostración de Gödel sí se aplica a cualquier método finitario y que el programa de Hilbert era imposible de realizar. Gödel apunta esta circunstancia en una posdata que agrega a su artículo original (y que aparece en las ediciones actuales del artículo.)

Acerca del libro, la demostración que allí se da se ajusta a las ideas originales de Gödel, con algunas modificaciones introducidas posteriormente por Raymond Smullyan, las que facilitan algunos detalles técnicos sin modificar la idea original.

Existen, en efecto, demostraciones alternativas del teorema basadas en máquinas de Turing, pero no es una de ellas la que se desarrolla en el libro. Una demostración de ese estilo puede verse en: http://eltopologico.blogspot.com/2005/12/gdel-y-turing-parte-1.html

Saludos!

G.P.

<<                >>
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.282

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #11 : 06/06/2009, 05:15:25 pm »


Existen, en efecto, demostraciones alternativas del teorema basadas en máquinas de Turing, pero no es una de ellas la que se desarrolla en el libro. Una demostración de ese estilo puede verse en: http://eltopologico.blogspot.com/2005/12/gdel-y-turing-parte-1.html


OK. Entonces no sé cómo se me metió en la cabeza que ustedes usaban teoremas basado en máquinas de Turing.
A lo mejor leí algún párrafo sobre máquinas de Turing y me quedó dando vueltas en la cabeza una conclusión errónea.

Lo de los métodos finitarios ha sido más que claro.

En línea

Numerarius
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 319


Ver Perfil
« Respuesta #12 : 06/06/2009, 05:37:12 pm »

Es curioso. Gregory Chaitin (que al parecer es un lógico bastante distinguido) escribió sobre el teorema de Gödel lo siguiente:

It was love at first sight! Mad love, crazy love[...]There was only one small, tiny problem, fortunately, which was that for the life of me I couldn't understand Gödel's proof of this wonderful metamathematical result. It's called that because it's not a mathematical problem result, it's a theorem about mathematics itself, about the limitations of mathematical methods

 I wasn't an idiot, so why couldn 't I understand Gödel's proof? Well, I could follow it step by step, but it  was like trying to mix oil and water. My mind  kept resisting. In other words, I just plain didn't like Godel's proof of his faboulous result. His original proof seemed, too fragile! It didn't seem to get to the heart of the matter, because it was far from clear how prevalent inclompleteness might in fact be.


(Gegory Chaitin, Meta Math. The Quest for Omega. Random House. Toronto( Canadá), 2005, pags. 26, 27).

Por cierto, este mismo autor afirma que prefiere la versión de la incompletud demostrada por Turing. Lo que demostró Turing se podría explicar (aproximadamente) así: no existe ningún procedimiento para verificar si un programa P con un dato k  contiene un bucle infinito (o alternativamente, si una máquina de Turing T, con un dato k no parará nunca). Esto se llama el "problema de la parada" ("The halting problem").
En línea

LauLuna
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

España España

Mensajes: 541


Ver Perfil WWW
« Respuesta #13 : 07/06/2009, 06:31:34 am »

Efectivamente, Hilbert no había dejado claro lo que se debía entender por 'método finitario'. Cuando Church y Turing formalizaron el concepto de computable, se tendió a pensar que había que entender lo finitario como lo computable o recursivo.

Como todas las funciones recursivas están representadas en la aritmética cuya consistencia se quiere probar, esta interpretación implicaba la imposibilidad del programa de Hilbert.

A pesar de eso, Gödel propuso en 1958 una ampliación del concepto de finitario ("Sobre una ampliación todavía no utilizada del punto de vista finitario" en Dialectica 12, 280-287); aceptando esa ampliación puede probarse la consistencia de la aritmética intuicionista que Gödel mismo había probado en 1932 equivalente a la aritmética clásica.

En cuanto a la cita de Chaitin. Hace tiempo planteé en otro hilo algo parecido y precisamente relacionado con la prueba de Gödel. Uno puede seguir la prueba paso a paso y entenderla, y luego quedarse pensando: bueno ¿qué es exactamente lo que sucede aquí?. Es decir, uno intenta captar la esencia de la prueba, el paso crucial, el hecho fundamental detrás de ella, algo que permita apoderarse intelectualmente del asunto. Y eso no es tan fácil.

Chaitin lo intentó formalizando el concepto de 'contenido de información' y reproduciendo el resultado de incompletitud sobre la base de que ningún sistema de axiomas puede demostrar que una fórmula contiene más información que los axiomas (esta descripción es sólo una aproximación). Es como si le pidieses a los axiomas que encontrasen la primera fórmula que ellos no pueden demostrar, que está más allá de su alcance; lógicamente, no podrán encontrarla, si son consistentes. Así que Chaitin dio una versión 'cuantitativa' del resultado de Gödel.

Para mí el hecho fundamental que hace posible la prueba de Gödel es la circunstancia de que la naturaleza recursiva de los sistema formales axiomáticos permite establecer un isomorfismo entre su estructura y ciertas estructuras aritméticas. Esto hace a su vez posible que los sistemas formales que contienen la aritmética (o una parte suficiente de ella: la aritmética recursiva) sean capaces de tratar parte de su propia metateoría. Es decir, esto hace que estos sistemas se vuelvan en cierto sentido autorreferentes. Y llegados aquí es donde entran en juego los métodos basados en las paradojas, claro.

¿Cuál diríais cada uno de vosotros que es el hecho fundamental que hace incompleta la aritmética y hace posible el resultado de Gödel? Porque esto de elegir un 'hecho fundamental' es muy subjetivo, depende de la forma personal que cada uno tiene de organizar las ideas.
En línea
Gustavo Piñeiro
Visitante
« Respuesta #14 : 07/06/2009, 09:04:11 am »

En el libro Gödel para Todos sostenemos la tesis (y ése es uno de los aportes originales que el libro intenta hacer al tema) de que el hecho fundamental que está detrás de la prueba de Gödel es que la operación de concatenar símbolos es expresable en la aritmética.

Me explico: Cuando se define el lenguaje formal de la aritmética, primero se indican los símbolos que se van a usar (por ejemplo [texx] \forall{} [/texx], [texx] \Rightarrow{} [/texx], etc.) Las expresiones del lenguaje se obtienen concatenando los símbolos entre sí (es decir, pegándolos). Por ejemplo, [texx] \forall{x} [/texx] se obtiene concatenando el símbolo [texx] \forall{} [/texx] con la variable [texx]x[/texx].

Existe una concatenación similar entre los números, al concatenar el 2 y el 3 obtenemos el número 23. En el libro damos una definición abstracta de la operación de concatenación (esencialmente que sea una operación isomorfa a la concatenación de símbolos) y vemos que ésta no es la única concatenación posible.

Cuando se define la numeración de Gödel, asignamos un número a cada símbolo y a la concatenación de dos o más símbolos le asignamos la concatenación de sus números correspondientes. Por ejemplo, si a [texx] \forall{} [/texx] le corresponde el 2 y a la variable [texx]x[/texx] le corresponde el 3, entonces a [texx] \forall{x} [/texx] le corresponderá el 23.

En su paper de 1931 Gödel mismo lo hace de esta manera (aunque sin ser conciente de eso). Él usa una concatenación basada en la descomposición en primos de los números enteros.

Como la concatenación es expresable en la aritmética entonces todas las operaciones sintácticas en el lenguaje se pueden traducir a operaciones expresables en la aritmética y en consecuencias las condiciones "Ser el número de Gödel de una fórmula" (resp. "de un enunciado", "de una demostración" y "de un teorema") son expresables en la aritmética y la prueba del teorema de Gödel puede llevarse adelante.

De hecho, probamos en el lbro que en cualquier teoría en la que pueda definirse una concatenación abstracta vale el equivalente del teorema de Gódel y damos, además, condiciones algebraicas que permiten verificar la existencia de una tal concatenación.

Un problema aún abierto es si la existencia de una concatenación es equivalente a la incompletitud. Nuestra conjetura es que no, pero no hemos podido dar un contraejemplo que zanje la cuestión.

<<                >>
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.282

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #15 : 07/06/2009, 01:26:49 pm »

Aprovecho para preguntar ¿qué es una teoría?
En línea

LauLuna
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

España España

Mensajes: 541


Ver Perfil WWW
« Respuesta #16 : 07/06/2009, 04:15:40 pm »

Argentinator, técnicamente (en Teoría de Modelos) una teoría es un conjunto C de sentencias en un lenguaje lógico formal con la condición de que C esté cerrado bajo la relación de consecuencia lógica: para todo p y q, si p pertenece a C y q es consecuencia lógica de p, q pertenece a C.

Pero en un sentido más amplio es usual llamar también teorías a los sistemas formales axiomáticos. En algunos de estos sistemas el conjunto de los teoremas es efectivamente una teoría, particularmente en los sistemas de primer orden: como la lógica de primer orden es completa (Gödel 1930), toda consecuencia lógica de los axiomas es también un teorema del sistema. Pero en algunos de ellos, como la aritmética de Peano de segundo orden, el conjunto de los teoremas no es una teoría en el sentido más estricto, porque no toda consecuencia lógica de los axiomas es un teorema.

Como sabes, los sistemas formales axiomáticos están compuestos por axiomas o esquemas axiomáticos y reglas de inferencia. El conjunto de los axiomas puede ser infinito (sobre todo cuando se emplean esquemas axiomáticos) pero ha de ser recursivamente enumerable porque lo esencial es que el conjunto de los teoremas sea recursivamente enumerable, sin eso no se puede hablar de un sistema formal en sentido estricto (aunque tales sistemas en sentido más amplio también existen).

Gustavo, no entiendo muy bien lo de la concatenación. Imagino que no siempre se podrán expresar las fórmulas como números a través de la simple concatenación. Por ejemplo, si los símbolos primitivos son cien, no puedo asociarles números naturales del 0 al 99 y luego representar las fórmulas mediante ssimple concatenación porque el número 19 representaría tanto al vigésimo símbolo como a la concatenación de los símbolos segundo y décimo.

Evidentemente podríamos inventar más símbolos para los números y expresarlos en base 100, y tal vez haya algín otro modo de hacer posible la gödelización por simple concatenación ¿Pero es realmente esencial la posibilidad de concatenar o basta con que haya una manera de representar los símbolos, las fórmulas y las derivaciones como números, aunque no pueda hacerse por simple concatenación?

De todas maneras, como no he leído el libro, sólo intuyo confusamente lo que dices: ¿sugerís los autores que lo que posibilita el teorema no es la estructura y naturaleza de los números mismos sino la naturaleza de nuestra manera de representarlos? No sé si estoy entendiendo bien.

Un saludo

En línea
Gustavo Piñeiro
Visitante
« Respuesta #17 : 07/06/2009, 05:42:37 pm »

Explicaré mejor la cuestión de la concatenación. Empiezo por la definición: una concatenación en un conjunto [texx]D\subseteq{} N[/texx] con dos átomos (que llamaré [texx]a[/texx] y [texx]b[/texx]) es una operación binaria (que indicaré [texx]\circ{}[/texx]) tal que:

1) Los átomos están en [texx]D[/texx]. La concatenación de dos elementos de [texx]D[/texx] está en [texx]D[/texx].
2) La operación es asociativa.
3) Todo elemento de [texx]D[/texx] es, o bien un átomo, o bien la concatenación de una cantidad finita de átomos.
4) La descomposición en átomos es única (la unicidad incluye a los átomos que aparecen y al orden en que están escritos).

Ejemplos de concatenación:

1) Sea [texx]D[/texx] el conjunto de todos los números (enteros positivos) cuya escritura en base 10 contiene solamente las cifras 1 y 2. Estas cifras son los átomos y concatenar es escribr un número a continuación del otro.

Como dice LauLuna esta concatenación no es intrínseca y depende de la escritura de los números. Una concatenación que sí es intrínseca es la siguiente:

2) Sea [texx]D[/texx] el conjunto de todos los enteros mayores que 1 que cumplen estas condiciones:

a) No son divisibles por el cubo de un primo (podríamos llamarlos números libres de cubos).
b) Son múltiplos de 2.
c) Si [texx]p[/texx] y [texx]q[/texx] son primos con [texx]p < q[/texx] y el número es divisible por [texx]q[/texx] entonces también es divisible por [texx]p[/texx].

La definición de la concatenación la daré a través de un ejemplo, creo que se entenderá bien:

La concatenación entre el número [texx]2\cdot{}3\cdot{}5[/texx] y [texx]2^2\cdot{}3^2\cdot{}5^2\cdot{}7[/texx] es [texx]2\cdot{}3\cdot{}5\cdot{}7^2\cdot{}11^2\cdot{}13^2\cdot{}17[/texx] (obsérvense los exponentes).

Tomemos ahora un lenguaje formal cualquiera para la aritmética (que tendrá una cantidad a lo sumo numerable de símbolos, los cuales suponemos que están ordenados según algún criterio). Dada una concatenación cualquiera con dos átomos, definimos una codificación de Gödel del siguiente modo:

Al primer símbolo del lenguaje le corresponde el número [texx]a\circ{}b[/texx].
Al segundo le corresponde [texx]a\circ{}b\circ{}b[/texx]
Al tercero le corresponde [texx]a\circ{}b\circ{}b\circ{}b[/texx]

Y así sucesivamente.

A la concatenación de dos o más símbolos le corresponde la concatenación de sus correspondientes números de Gödel.

Para codificar sucesiones de fórmulas, Raymond Smullyan usa la convención (que nosotros adoptamos) de incorporar un símbolo adicional para separar entre sí las las fórmulas de la sucesión.

A partir de aquí se puede desarrollar la prueba del teorema Gödel.

<<                >>
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.282

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #18 : 07/06/2009, 05:49:20 pm »

técnicamente (en Teoría de Modelos) una teoría es un conjunto C de sentencias en un lenguaje lógico formal con la condición de que C esté cerrado bajo la relación de consecuencia lógica: para todo p y q, si p pertenece a C y q es consecuencia lógica de p, q pertenece a C.


Lo que deseo es entender exactamente el objeto de estudio que estamos discutiendo.
Estoy acostumbrado a los sistemas axiomáticos, los conozco bastante porque me he estado peleando con ellos para entender cómo es que se construye la teoría de conjuntos.
Pero me tiene muy confundido el hecho de que se esté trabajando en el terreno de la metamatemática.
¿Los teoremas de Godel son metamatemáticos? Por lo que sé del tema, sí lo son.
Luego, en ese caso, ¿cuáles son las reglas del juego?

Dijiste algo de un ''conjunto de sentencias'', pero asumo que el término conjunto no se refiere a lo que se entiende por ''conjunto'' dentro de la teoría de conjuntos.
Después mencionaste un sistema lógico formal, pero no entiendo cómo puede uno estar seguro de qué es un objeto de ese tipo. ¿Hay definiciones más precisas de todo esto?
Porque mis dudas creo que empiezan por ahí.
No estoy convencido de si está bien definido el objeto de estudio, o sea, si está bien precisado aquello de qué estamos hablando.

Sin eso, no sé si pueda avanzar en la prueba de Godel, porque no me termina de cerrar qué es aquello de lo que se habla, ni cual es la hipótesis, ni cuál es la tesis, ni cuáles son las reglas válidas de inferencia.
Como no hay reglas, parece que todo el mundo está de acuerdo en que deben usarse fórmulas lógicas finitas, y que uno pueda seguir en su construcción paso a paso, sin duda alguna.
Eso al menos lo comprendo, pero quisiera que ustedes me digan exactamente en qué terreno nos movemos.

-----------

En cuanto a lo de la concatenación, bueno, tengo una percepción más filosófica que técnica, porque aún no entiende los detalles de todo esto.
Pero me parece que la operacion de concatenar, que es algo que Hilbert ya se creía autorizado a hacer, involucra la posibilidad de poner uno al lado de otro infinitos signos, o al menos, una cantidad no limitada de signos.
Eso vendría a decir que tengo una ''memoria'' (digamos, la de una computadora) con suficiente capacidad de almacenamiento, o sea, capacidad no finita.
Además, esas celdas de memoria están ordenadas según el orden de los números naturales, porque los signos se escriben uno a la derecha del otro, siguiendo ''un buen orden''.
Así que en realidad el esquema de los números naturales ya lo traemos incorporado incluso antes de haberlo construido como parte de alguna teoría lógica.
Mi conclusión es que el sistema de los naturales ya es parte de nuestro propios esquema de pensamiento, y que cuando construimos la teoría de los números naturales tenemos la ilusión de que estamos construyendo las cosas desde cero,
pero en realidad estamos reflejando algo ya existente en nuestra propia mentalidad.
Las cosas ''ya existentes'' son como ''axiomas''. Recordemos que Euclides asumía hechos ''naturales'' en su teoría, pero que con el tiempo hubo que formalizar esas ''creencias'' de Euclides y explicitarlas como axiomas de la geometría.
Tengo la sospecha de que con los números naturales nos pasa algo parecido a nosotros, ahora en el siglo 21.
Usamos ciertos ''axiomas'' sin darnos cuenta.

¿Qué construcciones u operaciones se asumen como válidas, y cuáles son no válidas?


En línea

Gustavo Piñeiro
Visitante
« Respuesta #19 : 07/06/2009, 09:33:51 pm »

Argentinator tiene razón: si la intención de este hilo es entender la demostración del Teorema de Gödel, entonces el modo correcto de empezar es enunciando el teorema.

Antes del enunciado en sí, es necesario hacer alguna aclaración filosófica (en relación a lo que también decía argentinator). Ni Hlbert ni Gödel creían que los axiomas creaban los números naturales "desde cero". De hecho, Hilbert consideraba imposible el intento de Frege y Russell de definir a los números naturales desde la lógica y la teoría de conjuntos, pues consideraba (y en esto coincidía con los intuicionistas) que la secuencia natural es esencial a nuestro pensamiento y, de hecho, el lenguaje mismo implica la idea de secuencia.

La idea general de Hilbert era dar métodos "seguros" (es decir, que garantizaran la no aparición de paradojas) para determinar si una afirmación aritmética es "verdadera" (siendo este último un término problemático y aún a definir).

En "Acerca del infinito" Hilbert propone que representemos a los números naturales mediante palotes: |, ||, |||, etc. Algunas afirmaciones aritméticas, dice Hilbert, son en realidad afirmaciones empíricas, cuya verdad o falsedad puede verificarse mecánicamente en una cantidad finita de pasos.

Un ejemplo es 2 + 3 = 5 que, traducida a palotes, dice que al concatenar dos palotes con tres palotes se obtienen cinco palotes. A estas afirmaciones empíricas las llamaremos aquí finitarias.

En realidad Hilbert extendía esta condición de finitaria a otras afirmaciones que, aunque no verificables empíricamente, eran intuitivamente evidentes, tales como el esquema de inducción.

Podemos entonces hablar de la verdad o falsedad de afirmaciones finitarias. ¿Qué pasa con las afirmaciones no finitarias? Hilbert dice que no está claro qué significa decir que es "verdadera" o "falsa" una afirmación no verificable empíricamente (ni ecintuitivamente evidente) y trata de reemplazar el concepto semántico de "verdad" por los conceptos sintácticos de "consistencia" y "demostrabilidad".

Tomemos un conjunto de axiomas formado por enunciados finitarios. Un enunciado P es demostrable a partir de esos axiomas si existe una sucesión finita de enunciados que termina en P y en el que cada enunciado es, o bien un axioma, o bien se obtiene de enunciados anteriores por aplicación de las reglas de inferencia. (Habitualmente estas reglas de inferencia son: modus ponens y generalización.)

Los axiomas, además, deben ser elegidos de modo tal que se cumpla esta condición: dado un enunciado cualquiera debe ser posible verificar mecánicamente en una cantidad finita de pasos si ese enunciado es, o no, un axioma. Enunciaremos esta condición diciendo que el conjunto de axiomas es recursivo. (Esta condición limita de tal modo los conjuntos posibles de axiomas que no es necesario recurrir a la teoría de conjuntos par definir qué es un "conjunto de axiomas".)

La propuesta de programa de Hilbert era encontrar un conjunto recursivo de axiomas tal que:

1) El conjunto de axiomas fuera consistente (es decir, dado cualquier enunciado P, nunca sucedería que P y su negación fueran a la vez demostrables).
2) El conjunto de axiomas fuera completo (es decir, dado cualquier enunciado P, o bien él o bien su negación sería demostrable).
3) Fuera posible demostrar la condición 1) mediante demostraciones "seguras" (para ello, decía Hilbert, debería desarrollarse una teoría de la demostración o metamatemática).

El enunciado del Teorema de Gödel, tal como Gödel lo enunció, es:

Teorema: Si un conjunto recursivo de axiomas cumple:

1) El sistema es [texx]\omega [/texx]-consistente. (Más abajo explico´qué es esto.)
2) Todo enunciado finitario es demostrable.

Entonces es incompleto. Es decir, existe un enunciado P tal que ni P ni su negación son demostrables.
Además (y éste es el llamado Segundo Teorema de Gödel) el hecho de que el sistema es consistente es expresable y no demostrable en el sistema.

(Cuando digo sistema es que incluyo a las reglas de inferencia, si éstas son fijadas de antemano, como habitualmente se hace, entonces "sistema de axiomas" y "conjunto de axiomas" son virtualmente sinónimos).

Un sistema de axiomas es [texx]\omega [/texx]-consistente si para toda fórmula [texx]P(x)[/texx] sucede que si [texx]P(n)[/texx] es demostrable para todo [texx]n[/texx] entonces [texx]\exists{x}-P(x)[/texx] (donde [texx]-P(x)[/texx] es la negación de [texx]P(x)[/texx]) no es demostrable.

(Puede probarse que todo sistema [texx]\omega [/texx]-consistente es consistente, pero no vale la recíproca.)

En 1936 John B. Rosser modificó la demostración de Gödel de modo que la hipótesis de ser [texx]\omega [/texx]-consistente se pudo reemplazar por la de ser consistente.

<<                >>
En línea
Páginas: [1] 2 3 ... 17   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!