Autor Tema: Teorema de Gödel

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

11 Julio, 2009, 04:28 pm
Respuesta #160

Gustavo Piñeiro

  • Visitante
Un comentario sobre la última parte de la demostración: ¿Dónde está la autorreferencia?

Hemos llamado m al código de \( Q[\overline{n}] \) y el enunciado G es \( -\exists{y}Dem(y,\overline{m}) \). Por lo tanto G dice "\( Q[\overline{n}] \) no es demostrable". Pero \( Q[\overline{n}] \) es equivalente a G, luego G es una afirmación de la que se deduce que ella misma no es demostrable.


11 Julio, 2009, 04:31 pm
Respuesta #161

Gustavo Piñeiro

  • Visitante
Si el sistema de axiomas es omega-consistente entonces G es un enunciado verdadero y no demostrable. Pero si el sistema no es consistente, entonces G es un enunciado falso y demostrable (y -G es verdadero y también demostrable).

12 Julio, 2009, 03:41 am
Respuesta #162

Gustavo Piñeiro

  • Visitante
La versión de Rosser:

En 1936 John B. Rosser modificó la demostración de Gödel para que valiera para un sistema consistente, en lugar de un sistema omega-consistente. Veamos cómo lo hizo (para abreviar, esta vez omitiré algunos tecnicismos).

Definamos la función neg(x) del siguiente modo: neg(x) es la concatenación del código de "-" (símbolo de negación) con x. Si n es el código de una fórmula P entonces neg(n) es el código de -P. Es claro que neg es expresable.

Definamos P(z) como:

\( \forall{u}(Dem(u,z)\Rightarrow{\exists{w}(Dem(w,neg(z))\wedge w\leq{u})}) \)

Como antes, definimos Q(x) como:

\( \forall{z}(z=d(x)\Rightarrow{P(z)}) \)

Sea n = cód(Q(x)), luego \( d(n) = c\'od(Q[\overline{n}]) \).
Llamemos m = d(n).

Igual que hicimos antes, se prueba que \( Q[\overline{n}] \) es equivalente a \( P(x/\overline{m}) \).

Llamemos R al enunciado \( P(x/\overline{m}) \), es decir R es:

\( \forall{u}(Dem(u,\overline{m})\Rightarrow{\exists{w}(Dem(w,neg(\overline{m}))\wedge w\leq{u})}) \)

Podemos traducir a R como: "dada cualquier demostración de \( Q[\overline{n}] \) (que es un enunciado equivalente al propio R) existe una demostración de \( -Q[\overline{n}] \) que tiene un código menor que la demostración dada".

Más fácil: dada cualquier demostración de \( Q[\overline{n}] \) existe una demostración más corta de su negación.

Suponiendo que el sistema de axiomas es consistente, vamos a probar que ni R ni -R es demostrable.

Si R es demostrable, sea k el código de una demostración de k. Entonces \( Dem(\overline{k},\overline{m}) \) es un enunciado finitario verdadero y, por ende, demostrable.

Como R es demostrable, por aplicación del esquema lógico que permite reemplazar la variable u por el término \( \overline{k} \) tenemos que:
 
\( Dem(\overline{k},\overline{m})\Rightarrow{\exists{w}(Dem(w,neg(\overline{m}))\wedge w\leq{\overline{k}})}) \) es demostrable.

Por aplicación de la regla de modus ponens:

\( \exists{w}(Dem(w,neg(\overline{m}))\wedge w\leq{\overline{k}}) \) es demostrable.

Este último enunciado equivale a:

\( Dem(0,neg(\overline{m}))\vee Dem(\overline{1},neg(\overline{m}))\vee \ldots \vee Dem(\overline{k},neg(\overline{m})) \), que es también demostrable. Llamémoslo T.

Ahora bien, como el sistema es consistente entonces -R no es demostrable. Luego, \( -Dem(0,neg(\overline{m})) \), \( -Dem(\overline{1},neg(\overline{m})) \), \( -Dem(\overline{2},neg(\overline{m})) \),... son todos enunciados finitarios verdaderos y en consecuencia demostrables.

En consecuencia: \( -Dem(0,neg(\overline{m}))\wedge -Dem(\overline{1},neg(\overline{m}))\wedge  \ldots \wedge -Dem(\overline{k},neg(\overline{m})) \) es un enunciado finitista verdadero y demostrable. Pero este enunciado es la negación de T, luego el sistema no sería consistente. Por lo tanto, R no puede ser demostrable.

(Al agregar el inciso \( w\leq{\overline{k}} \) al existencial \( \exists{w}Dem(w,neg(\overline{m})) \) el enunciado se vuelve equivalente a la disyunción de una cantidad finita de enunciados y es por eso que ya no es necesaria la hipótesis de la omega-consistencia.)

Falta ver que -R no es demostrable. Supongamos que sí lo fuera y sea k el código de una demostración de -R.

Entonces \( Dem(\overline{k},neg(\overline{m})) \) es demostrable.

Luego,\( \exists{w}Dem(w,neg(\overline{m})) \) es demostrable.

Luego, \( \overline{k}\leq u\Rightarrow (\exists{w}Dem(w,neg(\overline{m}))) \) es demostrable y también es demostrable \( \overline{k}\leq u\Rightarrow \exists{w}(w\leq u) \).

En consecuencia, \( \overline{k}\leq u\Rightarrow (\exists{w}(Dem(w,neg(\overline{m}\wedge w\leq u)))) \) es demostrable.

Por otra parte, por la consistencia del sistema, R no es demostrable. De ello puede deducirse que:

\( u\leq \overline{k}\Rightarrow -Dem(u,\overline{m}) \) es demostrable.

Finalmente, entre las hipótesis de la versión de Rosser del teorema habíamos supuesto que \( \overline{k}\leq u\vee u\leq \overline{k} \) es demostrable. Se deduce así que:

\( -Dem(u,\overline{m})\vee \exists{w}(Dem(w,neg(\overline{m}\wedge w\leq u))) \)

es demostrable. Pero este enunciado es sintácticamente equivalente a R. Luego R sería demostrable, lo que contradice la hipótesis de la consistencia del sistema. Concluimos así que -R no es demostrable. Una vez más, Q.E.D.

Como antes, si el sistema es consistente, R es un enunciado verdadero y no demostrable. Pero si el sistema no es consistente entonces R es falso y demostrable.

<<                >>

12 Julio, 2009, 08:22 pm
Respuesta #163

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
He fijado el presente hilo para que quede fácil de encontrar a todo el que lo busque  ;)

12 Julio, 2009, 09:33 pm
Respuesta #164

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Gustavo, dices que por hipótesis el sistema demuestra los enunciados finitistas verdaderos.

Como la demostración ha sido larga, es muy posible que no recuerde bien pero ¿por qué hipótesis? Quizá por esta:

Citar
Recordemos que hemos supuesto que se ha dado un sistema omega-consistente de axiomas aritméticos.

Pero ¿hemos demostrado que todo sistema aritmético omega-consistente demuestra todos los enunciados finitistas verdaderos? Tal vez sí pero no lo recuerdo.

Creo que me he perdido algo.

12 Julio, 2009, 09:48 pm
Respuesta #165

Gustavo Piñeiro

  • Visitante
Pero ¿hemos demostrado que todo sistema aritmético omega-consistente demuestra todos los enunciados finitistas verdaderos? Tal vez sí pero no lo recuerdo.

No lo hemos demostrado y en realidad no es cierto. Me refiero a las hipótesis del teorema, cuyo enunciado es: Todo sistema recursivo y omega-consistente de axiomas para el que todo enunciado finitista verdadero es demostrable, es incompleto.

<<                >>

12 Julio, 2009, 11:59 pm
Respuesta #166

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Me refiero a las hipótesis del teorema, cuyo enunciado es: Todo sistema recursivo y omega-consistente de axiomas para el que todo enunciado finitista verdadero es demostrable, es incompleto.

Claro, ese era el tipo de sistemas para el que hacíamos la demostración.

Gracias.

22 Julio, 2009, 04:26 pm
Respuesta #167

Cristian C

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 474
  • Karma: +0/-0
  • Sexo: Masculino
Dice Gustavo:

Citar
En todo lo que sigue, x es la variable \( v_| \).

Definimos P(z) como la fórmula \( -\exists{y}Dem(y,z) \). (Recordemos que \( Dem(y,z) \) expresa la relación "y es el código de una demostración de la fórmula de código z".)

Definimos Q(x) como \( \forall{z}(z=d(x)\Rightarrow{P(z)}) \).

Sea n = cód(Q(x)). Entonces \( d(n) = c\'od(Q[\overline{n}]) \). Llamamos m = d(n).

Los siguientes enunciados son equivalentes entre sí (esta equivalencia es sintáctica e implica que cualquiera de ellos es demostrable si y sólo si cualquiera de los otros lo es):

1. \( Q[\overline{n}] \)
2. \( Q(x/\overline{n}) \)
3. \( \forall{z}(z=\overline{m}\Rightarrow{P(z)}) \)
4. \( P[\overline{m}] \)
5. \( P(x/\overline{m}) \)

Llamemos G al enunciado \( P(x/\overline{m}) \), es decir, \( -\exists{y}Dem(y,\overline{m}) \).

En la equivalencia de los 5 enunciados me está costando probar que alguno de los dos primeros es equivalente a alguno de los otros tres. He reescrito algunas de las definiciones y teoremas desde la definición de \( P[t] \), pero aún así no logro situarme. ¿alguien podrá ayudarme?

Por cierto, la palabra "tecnicismo" no logra transmitir la elegancia e ingenio que hay detrás de esas soluciones. Me ha gustado mucho esta demostración que ha puesto Gustavo.

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.

22 Julio, 2009, 07:15 pm
Respuesta #168

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Cristian, para darte cuenta de la equivalencia de las dos primeras fórmulas con la tercera no tienes más que recordar cómo han sido definidos Q(x) y m.

La equivalencia entre las tres primeras fórmulas es por definición: son tres maneras de llamar a la misma fórmula en el lenguaje del sistema.

Para la equivalencia entre la tercera y la cuarta, date cuenta de que la tercera fórmula viene a decir:

'si un número es el código de la diagonalización de (la fórmula cuyo código es) n entonces P vale de ese número';

es decir, dice que P vale de la diagonalización de n; y la diagonalización de n es m; luego la tercera fórmula equivale a P(m) (tomo 'm' como su propio numeral).

En realidad, sólo tienes que pasar de

'para todo x, si x=m, entonces P(x)'

a

'P(m)'.

El sistema descrito por Gustavo es claramente capaz de hacer esta deducción.

23 Julio, 2009, 01:47 am
Respuesta #169

Cristian C

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 474
  • Karma: +0/-0
  • Sexo: Masculino
Gracias LauLuna, veré si encuentro el camino para \( Q[\overline{n}] \) equivalente a \( P[\overline{m}] \)


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.