07/12/2019, 11:14:20 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a NUMERARIUS
 
 
Páginas: 1 ... 15 16 [17]   Ir Abajo
  Imprimir  
Autor Tema: Teorema de Gödel  (Leído 141524 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Elius
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 360



Ver Perfil WWW
« Respuesta #320 : 04/04/2017, 08:10:28 pm »

Gödel agrega 45 definiciones de propiedades y relaciones recursivas (más una que no es recursiva, la 46, Bew), que actúan en la práctica como si al sistema se le hubieran añadido axiomas para la división, la primalidad, la función factorial, la potencia, las dos inversas de la potencia, y varias más.

Están a partir de la página 8 en el documento que adjunto.

Estas fórmulas permiten que en el sistema se pueda expresar enunciados del metalenguaje natural, en castellano, como:

<< "ssss0 + sssssss0 = sssssssssss0  " es una fórmula demostrable>>.

La analogía es exacta, salvo que en lugar de citas textuales, Gödel hace citas codificadas en números.


"Ser demostrable" es expresable:

Hemos visto que "Ser un axioma" es expresable. Gracias al Principio Generador podemos deducir que "Ser una demostración" es también expresable. Con más precisión, la relación "x es el código de una demostración" es expresable.

Por otra parte, "Ser la última expresión en una sucesión de expresiones aritméticas" es también expresable. Esto se debe a que "y es el código de la última expresión en la sucesión de código x" equivale a que "la concatenación de los tres siguientes números, en ese orden: el código de [texx]\otimes{}[/texx],  el número y, el código de [texx]\otimes{}[/texx], es sufijo de x".

Como consecuencia de todo esto tenemos que la relación "x es el código de una demostración de la fórmula de código y" (es decir, "la fórmula de código y es la última en la demostración de código x") es expresable. Dado que usarenos muchas veces esta relación, la indicaremos como Dem(x, y).

Destaco un hecho: Dem(x, y) es la abreviatura de una larga fórmula escrita en el lenguaje formal, en la que x e y son las únicas variables libres, cuyo significado es: "x es el código de una demostración de la fórmula de código y".

Al hablar de "significado" podría llegar a entenderse que hemos introducido un concepto no fiinitario, pero esto es sólo aparente porque la condición "x es el código de una demostración de la fórmula de código y" puede traducirse a condiciones puramente sintácticas entre los números x e y, verificables todas ellas mecánicamente en una cantidad finita de pasos.

Es decir, existe un algoritmo que, dados los números n y m, puede verificar en una cantidad finita de pasos si [texx]Dem(\overline{n}, \overline{m})[/texx] se cumple o no. (Donde [texx]\overline{n}[/texx] y [texx]\overline{m}[/texx] son los numerales correspondientes a los números n y m.)

"y es el código de una fórmula demostrable" se puede expresar entonces como [texx]\exists{x}Dem(x,y)[/texx] (es decir, "existe una demostración de la fórmula de código y"). Por lo tanto "Ser el código de una fórmula demostrable" es expresable.

Nota: Que [texx]x[/texx] es el código de una demostración, que [texx]y[/texx] es el código de una  de una fórmula, y que [texx]y[/texx] es el código de la última expresión en la sucesión de código [texx]x[/texx] son todas propiedades recursivas, por lo que el hecho de que sean expresable se puede deducir del teorema general que dice que toda propiedad recursiva es expresable. Sin embargo, por sí sola, la propiedad "y es el código de una fórmula demostrable" no es recursiva (aunque sí expresable).

Nos habíamos propuesto el objetivo de probar que "Ser demostrable" es expresable y lo hemos logrado. Habíamos dicho, a modo de ejemplo, que queríamos que el lenguaje formal fuera capaz de decir "1 + 1 = 2 es demostrable". En efecto, si llamamos [texx]n_0[/texx] al código de S0 + S0 = SS0 entonces "1 + 1 = 2 es demostrable" equivale a [texx]\exists{x}Dem(x,y/\overline{n_0})[/texx].

Nota: Hemos probado que "Ser una fórmula demostrable" es expresable ¿Qué pasa con los enunciados? Recordemos que los enunciados son casos particulares de fórmulas y volvamos a "1 + 1 = 2 es demostrable", que se traduce como [texx]\exists{x}Dem(x,y/\overline{n_0})[/texx]. En realidad esta traducción dice, correctamente, "[texx]\overline{n_0}[/texx] es el código de una fórmula demostrable" y con eso es sificiente a todos los efectos ya que, fórmula o enunciado, lo que nos interesa decir es que "1 + 1 = 2 es demostrable". Por eso en el título de este comentario puse que "Ser demostrable" es expresable, sin indicar si me refería a fórmulas o a enunciados.


* Godel_original.pdf (220.42 KB - descargado 118 veces.)
En línea

Elius
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 360



Ver Perfil WWW
« Respuesta #321 : 04/04/2017, 08:45:41 pm »

Como cualquiera puede comprobar en la demostración que hace Gustavo, el enunciado G no tiene ningún número de Gödel de una sentencia básica. Son todas sentencias del metalenguaje interno.

El final de la demostración.

En todo lo que sigue, x es la variable [texx]v_|[/texx].

Definimos P(z) como la fórmula [texx]-\exists{y}Dem(y,z)[/texx]. (Recordemos que [texx]Dem(y,z)[/texx] 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 [texx]\forall{z}(z=d(x)\Rightarrow{P(z)})[/texx].

Sea n = cód(Q(x)). Entonces [texx]d(n) = c\'od(Q[\overline{n}])[/texx]. 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. [texx]Q[\overline{n}][/texx]
2. [texx]Q(x/\overline{n})[/texx]
3. [texx]\forall{z}(z=\overline{m}\Rightarrow{P(z)})[/texx]
4. [texx]P[\overline{m}][/texx]
5. [texx]P(x/\overline{m})[/texx]

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

Vamos a demostrar que ni G ni -G son demostrables.

Recordemos que hemos supuesto que se ha dado un sistema omega-consistente de axiomas aritméticos. (Que sea omega-consistente implica que es consistente.)

Si G es demostrable, entonces (por las equivalencias que mencionamos antes) [texx]Q[\overline{n}][/texx] es demostrable. Recordemos que el código de [texx]Q[\overline{n}][/texx] es m.

Sea k el código de una demostración de [texx]Q[\overline{n}][/texx], entonces [texx]Dem(\overline{k},\overline{m})[/texx] es un enunciado verdadero. La palabra "verdadero" se usa aquí en el sentido finitista, ya que [texx]Dem(\overline{k},\overline{m})[/texx] es un enunciado que expresa una propiedad de k y m que es verificable en una cantidad finita de pasos.

Como [texx]Dem(\overline{k},\overline{m})[/texx] es un enunciado finitista verdadero, entonces (por hipótesis) es demostrable. En consecuencia (por el tecnicismo que vimos antes) [texx]\exists{y}Dem(y,\overline{m})[/texx] es demostrable. Pero entonces -G es demostrable (ya que [texx]\exists{y}Dem(y,\overline{m})[/texx] es equivalente sintácticamente a -G). Esto contradice que el sistema es consistente, luego G no es demostrable.

Si -G es demostable entonces, por la consistencia del sistema, G no es demostrable. Luego, para todo k, [texx]-Dem(\overline{k},\overline{m})[/texx] es un enunciado finitista verdadero y, por lo tanto, demostrable. Por la omega-consistencia entonces [texx]\exists{y}Dem(y,\overline{m})[/texx] no es demostrable. Entonces -G no es demostrable. Esto contradice la hipótesis inicial. Por lo tanto, -G no es demostrable.

Vimos así que G no es demostrable, y que -G tampoco es demostrable. El sistema es, entonces, incompleto, Q.E.D.

En línea

Elius
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 360



Ver Perfil WWW
« Respuesta #322 : 04/04/2017, 08:52:53 pm »

Primero construye una fórmula abierta, que interpretada en castellano sería:

G(x): "La sustitución de la variable 'x' en el número de fórmula x no es demostrable."

Luego efectúa la sustitución de la variable libre (la x que no tiene comillas simples) por el número de Gödel de G(x).

G: "La sustitución de la variable 'x' en el número de fórmula #G(x) no es demostrable."

El resultado es un enunciado del meta lenguaje que tiene como argumento otro enunciado del meta lenguaje. No hay ningún enunciado del lenguje objeto, el básico, compuesto sólo de ecuaciones diofánticas eventualmente cuantificadas, o una combinación booleana de ellas.

Es un enunciado vacío. Su argumento es una operación (instanciación de variable) con el número de una fórmula abierta como argumento. Por supuesto es indemostrable, porque depende de la demostración de G(x).

Como G(x) es una fórmula abierta, sólo sería demostrable si se pudiera aplicar la regla de generalización.






En línea

Páginas: 1 ... 15 16 [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!