Autor Tema: Teorema de Gödel

0 Usuarios y 2 Visitantes están viendo este tema.

18 Junio, 2009, 03:14 pm
Respuesta #100

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Gustavo, me refería a decir algo sobre que en el esquema de inducción 'P' está por cualquier predicado monádico expresable en el lenguaje del sistema.

Dices, por otra parte, que el teorema de Gödel se aplica a cualquier sistema capaz de demostrar los enunciados finitarios verdaderos ¿equivale esa capacidad a que contenga a la aritmética primitiva recursiva (PRA) de Skolem, que carece de cuantificadores?

Sin embargo, sé que el sistema Q de Robinson (que carece del esquema de inducción pero contiene cuantificación existencial) está también sujeto al teorema de Gödel porque en él están representadas todas las funciones computables. Creo que siempre he pensado que Q era una extensión conservadora de PRA y que PRA es el sistema más básico al que se aplica el teorema de Gödel. Pero ahora no estoy seguro.

En general: ¿hay un sistema que sea el sistema más débil al que se aplica el teorema de Gödel?

Es decir: ¿hay un sistema S tal que cualquier otro sistema al que se aplique el teorema de Gödel contiene a S?

Gracias.

19 Junio, 2009, 04:57 am
Respuesta #101

Gustavo Piñeiro

  • Visitante
Hola,

Antes que nada, quiero hacer un comentario general acerca de todo lo que he venido escribiendo. En una de las presentaciones del libro "Gödel para Todos" (el cual, de alguna manera, vengo parafraseando en muchos de los comentarios que escribí) Guillermo Martínez decía que la intención del libro es contar el Teorema de Gödel del modo más sencillo posible sin que deje de ser el Teorema de Gödel.

Se estaba refiriendo con esto a un cuentito muchas veces repetido que relata que una persona sin conocimientos de Física le pide a un físico que le explique qué dice la Teoría de la Relatividad. El físico se lo cuenta refiriéndose a la transformada de Lorentz, etc. etc., pero el otro le dice que no entendió nada. Entonces el físico simplifica un poco la explicación, pero el oyente sigue sin entender. Así sigue simplificando la explicación, cada vez eliminando tecnicismos, hasta que el otro finalmente dice: "ahora entendí", a lo que el físico responde: "sí, pero eso ya no era la Teoría de lla Relatividad".

La intención de "Gödel para Todos" es relajar los tecnicismos tanto como sea posible para facilitar la comprensión, pero de modo que lo que se enuncie y demuestre no deje de ser el Teorema de Gödel.

En cierto modo es lo que he venido haciendo aquí. Trato de hacer hincapié en ciertas ideas clave y de relajar los tecnicismos tanto como sea posible sin caer en el error.  Por eso no hablo de "predicados monádicos", sino de "fórmulas con una variable libre" o de "funciones proposicionales" y escribo \( s.t \) en lugar de \( f_2^2(t_1,t_2) \), etc. Me parece adivinar que esta actitud mía te provoca, LauLuna, algunos "chisporroteos" porque estás acostumbrado a un lenguaje más formal, y es por eso que, antes, ofrecí ceder este "púltpito" a quien quisiera manejarlo con más rigor.

En ese mismo espíritu hablo de "enunciado finitario" cuando la condición más exacta es: si \( R(x,y) \) es una relación recursiva entonces existe una fórmula \( B(x,y) \) en el lenguaje de la teoría tal que si \( R(n,m) \) es verdadero entonces \( B(n,m) \) es demostrable y si \( R(n,m) \) es falso entonces \( -B(n,m) \) es demostrable (y todavía me estoy salteando la distinción entre números y numerales). En otras palabras, toda relación recursiva debe ser definible en la teoría. Condición ésta que, en efecto, cumple la teoría Q.

Dado que \( B(n,m) \) y \( -B(n,m) \) son enunciados finitarios, podemos despachar todo lo anterior diciendo que todo enunciado finitario es demostrable.

Dices, por otra parte, que el teorema de Gödel se aplica a cualquier sistema capaz de demostrar los enunciados finitarios verdaderos ¿equivale esa capacidad a que contenga a la aritmética primitiva recursiva (PRA) de Skolem, que carece de cuantificadores?

Sinceramente, no lo sé. Es una buena pregunta.

En general: ¿hay un sistema que sea el sistema más débil al que se aplica el teorema de Gödel?

Es decir: ¿hay un sistema S tal que cualquier otro sistema al que se aplique el teorema de Gödel contiene a S?

Ésta es una pregunta cuya respuesta venimos persiguiendo desde hace bastante tiempo. Hay indicios que apuntan a que la respuesta es "no". En la literatura, ese papel minimal parece que se le atribuye a la teoría Q. Varios libros enuncian el teorema de Gödel como "toda extensión consistente de Q es incompleta", aunque, claro, no dicen que Q sea realmente minimal.

Saludos,

<<                >>

19 Junio, 2009, 12:15 pm
Respuesta #102

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
No, Gustavo, nada de "chisporroteos"; sólo es que, desde fuera, me planteo a veces si la gente entenderá bien lo que se está diciendo; por ejemplo, si sabrán el papel que hace 'P' en el esquema de inducción, si cuando dices 'demostrables' (a propósito de la consistencia) va a quedar claro para todos que hablas de demostrables en el sistema formal o alguien puede pensar que se trata de demostrable en algún sentido más general o vago, etc.

Sé que a ti te toca la labor más ardua con mucho y creo que todos te agradecemos enormemente la atención que nos dedicas, pero tampoco está mal que si pensamos (con razón o sin ella) que algo puede no haber quedado lo suficientemente claro, te lo hagamos saber.

Ten en cuenta que parece que mucha gente está siguiendo este tema y, sin embargo, la mayoría de los que lo siguen no preguntan nada; conjeturo que a veces temen estar preguntando una tontería o estar preguntando una cosa que se ha aclarado en un mensaje anterior y ya van unos cuantos, no es fácil revisarlos todos), o algo así.

Entonces, esa labor de llamar la atención sobre tales puntos puede ser complementaria con la tuya y puede ayudar a que este hilo cumpla todavía mejor su propósito, que era en principio el de aclarar cualquier duda que alguien pudiese tener respecto del teorema de Gödel.

Espero que esas intervenciones mías no te hayan molestado.
 
Un saludo

19 Junio, 2009, 12:45 pm
Respuesta #103

Gustavo Piñeiro

  • Visitante
Hola,

pero tampoco está mal que si pensamos (con razón o sin ella) que algo puede no haber quedado lo suficientemente claro, te lo hagamos saber.

Por supuesto.

Entonces, esa labor de llamar la atención sobre tales puntos puede ser complementaria con la tuya y puede ayudar a que este hilo cumpla todavía mejor su propósito, que era en principio el de aclarar cualquier duda que alguien pudiese tener respecto del teorema de Gödel.

Totalmente de acuerdo.

Espero que esas intervenciones mías no te hayan molestado.

Absolutamente no.

Saludos,

19 Junio, 2009, 01:11 pm
Respuesta #104

Gustavo Piñeiro

  • Visitante
Teorema (Gödel, 1931): Si un sistema recursivo de axiomas para la aritmética verifica que:
1) Es omega-consistente.
2) Todo enunciado finitario es demostrable.
Entonces el sistema es incompleto, es decir, existe un enunciado P tal que ni P ni -P son demostrables en el sistema.


Aquí, finalmente, el Teorema de Gödel. Antes de adentrarnos en la demostración conviene detenerse en algunas reflexiones.

1. El enunciado original de Gödel no es exactamente el que he dado más arriba. En su artículo de 1931 Gödel da algunos axiomas que garantizan la hipótesis de que todo enunciado finitario sea demostrable (en particular, incluía el esquema de inducción, que es el axioma 7 de la lista de axiomas de Peano que dí antes) y el enunciado de Gödel habla de todo sistema de axiomas que contenga a esos que él dio.

El enunciado que yo he dado parece "mejor" en el sentido de que se pide una condición más general, que incluye a más sistemas que el de Gödel (pues puede haber sistemas en los que todo enunciado finitario sea demostrabe, pero que no incluya todos los axiomas dados por Gödel). El de Gödel es, por otra parte, mejor en el sentido siguiente: el enunciado del teorema que yo he dado deja abierta la pregunta ¿habrá algún sistema recursivo de axiomas que cumpla que todo enunciado finitario sea demostrable? Gödel responde a esa cuestión dando explícitamente un tal sistema.

2. En 1936 John B. Rosser modificó la demostración de Gödel de modo que el teorema se transformó en:

Teorema (Rosser, 1936): Si un sistema recursivo de axiomas para la aritmética verifica que:
1) Es consistente.
2) Todo enunciado finitario es demostrable.
3) Todo enunciado de la forma \( \forall{x}(x\leq{n}\vee n\leq{x}) \) es demostrable, donde n es un numeral cualquiera y \( x\leq{y} \) debe tomarse como una abreviatura de \( \exists{z}(x + z = y) \).
4) Todo enunciado de la forma \( \forall{x}(x\leq{n}\Rightarrow (x=0 \vee \ldots \vee x = n)) \) es demostrable, donde n es un numeral cualquiera.
Entonces el sistema es incompleto, es decir, existe un enunciado P tal que ni P ni -P son demostrables en el sistema.


(La diferencia esencial es que se cambia "omega-consistente" por "consistente".)

En la versión original de Rosser las hipótesis 2), 3) y 4) se reemplazan por el hecho de que el sistema contiene los axiomas propuestos por Gödel. Los enunciados mencionados en 3) y 4) no son finitarios en el sentido que hemos definido (verificables en una catidad finita de pasos), pero sí lo son en el sentido más amplio que usaba Hilbert ("intuitivamente verdaderos").

3. Se puede probar además que existe un enunciado P cuyo significado se puede interpretar como: "el sistema de axiomas es consistente" y que es indecidible (es decir, ni P ni -P son demostrable en el sistema). Ésta afirmación es el llamado Segundo Teorema de Gödel.

4. Panu Raatikainen, en un paper sobre las consecuencias filosóficas del Teorema de Gödel, escribe:

"It is widely thought that Gödel’s theorems gave a death blow to Hilbert’s program. Whether Gödel’s theorems really demonstrated that it is impossible to carry out Hilbert’s program is controversial. This is partly because there is not complete clarity as to what exactly constitutes Hilbert’s program, and what views are truly essential for it. Furthermore, some of Hilbert’s key concepts are somewhat vague. Nevertheless, I think that there are good reasons to think that Hilbert's mature program of the 1920s was, in its original form and in its full generality, refuted by Gödel’s theorems."

Es decir, es controvertido si el teorema de Gödel refuta el Programa de Hilbert, en parte porque no queda claro cuáles eran los conceptos clave de ese programa.

Creo que Panu se refiere a la idea a la de Hilbert de incluir dentro de la categoría de "finitarios" a los enunciados "intuitivamente evidentes" (Gödel intenta años después formalizar esta idea en su artículo "Sobre una extensión del punto de vista finitario"). Si por "finitario" (como hemos hecho aquí, y como se hace habitualmente) entendemos "verificable mecánicamente" entonces me parece que sí, que el Teorema de Gödel anula la posibilidad de completar el Programa de HIlbert.

5. Conviene observar que no toda teoría es incompleta. Por ejemplo, si del lenguaje eliminamos la operación de multiplicación (y dejamos sólo S y la suma) entonces la teoría así obtenida admite un sistema recursivo y completo de axiomas (Presburger, 1929).

<<                >>

19 Junio, 2009, 01:39 pm
Respuesta #105

Gustavo Piñeiro

  • Visitante
Otros comentarios:

6. Dijimos antes que se puede probar que todo sistema omega-consistente es consistente. Ahora bien, si P es un enunciado indecidible para el sistema podemos agregar a P o a -P como nuevo axioma y en ambos casos tendremos un sistema consistente. Sin embargo, sólo uno de los dos será omega-consistente (el otro será consistente, pero no omega-consistente).

7. De P y -P uno de ambos es verdadero. Así que una forma de ver el teorema de Gödel es ésta: bajo las hipótesis indicadas antes existe un enunciado verdadero pero no demostrable en el sistema.

19 Junio, 2009, 03:47 pm
Respuesta #106

Gustavo Piñeiro

  • Visitante
Bibliografía: el paper completo de Panu Raatikainen puede descargarse del blog http://godelparatodos.blogspot.com (véase la columna izquierda del blog). Allí mismo se pueden descargar (en castellano) "Acerca del Infinito" y "La fundamentación de la teoría de números", ambos de Hilbert, y la "conferencia Gibbs", conferencia de Gödel de 1951 sobre las consecuencias filosóficas de su teorema (a la cual alude Panu Raatikainen en su paper).

<<                >>

19 Junio, 2009, 08:04 pm
Respuesta #107

Cristian C

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 474
  • Karma: +0/-0
  • Sexo: Masculino
Recién descubro este hilo. Ya leeré con tiempo todo lo que han escrito.
Pero debo decir antes de eso que los esfuerzos de Gustavo por procurarnos la comprensión de los teoremas de Gödel son encomiables.

No solo ha escrito un libro sin el cuál jamás me hubiera animado con estos temas. No solo me ha respondido en el sitio del libro todo lo que he preguntado sino que además lo encuentro aquí explicando los detalles del tema a diestra y siniestra.

Creo que lo de Gustavo es generosidad, en todo su sentido.

Saludos.
Mi primer gran deslumbramiento matemático consistió en comprender que puede demostrarse que existen infinitos de diferente tamaño.
El segundo fue comprender que lo anterior, aun pese a ser correcto, carece de todo significado.

20 Junio, 2009, 08:15 pm
Respuesta #108

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Se me ocurre la siguiente pregunta: ¿es posible plantear el sistema de la aritmética de Peano sin axiomas lógicos, sólo con los axiomas aritméticos?

Quiero decir ¿es posible descargar toda la lógica en las reglas de inferencia?

Es usual añadir a los sistemas matemáticos los axiomas lógicos; así lo hace, por ejemplo, Mendelson en su famosa 'Introduction to Mathematical Logic'.

Pero T. Franzén, en el libro que cité en otro mensaje ('Inexhaustibility. A Non-Exhaustive Treatment') presenta la aritmética de Peano de primer orden sólo con los axiomas aritméticos. A cambio define una 'relación de deducibilidad' mediante 16 reglas del tipo:

Si de A se deducen p y q, entonces de A se deduce p&q.

Lo que pregunto entonces es: ¿puede eso dar lugar a un sistema al que se aplique el teorema de Gödel?

Un saludo

20 Junio, 2009, 10:41 pm
Respuesta #109

Gustavo Piñeiro

  • Visitante
Lo que pregunto entonces es: ¿puede eso dar lugar a un sistema al que se aplique el teorema de Gödel?
Un saludo

Si el conjunto de todos los enunciados deducibles es recursivamente numerable, entonces sí, se aplica el teorema de Gödel.