Autor Tema: Teorema de Gödel

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

27 Junio, 2009, 06:48 pm
Respuesta #120

Gustavo Piñeiro

  • Visitante
Recordemos que nuestro objetivo es demostrar que "Ser el código de una fórmula demostrable" es una propiedad expresable en el lenguaje formal de la aritmética.

El concepto de "fórmula demostrable" se construye en pasos sucesivos:

1. Tenemos el símbolo para la constante: 0.
2. Tenemos símbolos para las variables.
3. Aplicando sucesivamente símbolos de función a las variables y a la constante obtenemos los términos.
4. Igualando dos términos obtenemos las fórmulas atómicas.
5. Aplicando sucesivamente las operaciones lógicas a las fórmulas atómicas obtenemos las fórmulas (en particular, los enunciados).
6. Aplicando el símbolo especial \( \otimes{} \) a las fórmulas obtenemos las sucesiones de fórmulas.
7. Una demostración es una sucesión de fórmulas que cumple determinadas condiciones sintácticas.
8. Una fórmula demostrable es la última fórmula de una demostración.

Para probar que "Ser el código de una fórmula demostrable" es expresable debemos remontar esa misma cadena de construcciones. Más específicamente, debemos probar que las siguientes propiedades son expresables:

0. Ser el código de una expresión. (Recordemos que "expresión" es cualquier secuencia finita de símbolos.)
1. Ser el código de la constante.
2. Ser el código de una variable.
3. Ser el código de un término.
4. Ser el código de una fórmula atómica.
5. Ser el código de una fórmula (en particular, de un enunciado).
6. Ser el código de una sucesión de fórmulas.
7. Ser el código de una demostración.
8. Ser el código de una fórmula que está al final de una demostración.

La idea general es que estas construcciones se obtienen mediante operaciones sintácticas y que la concatenación de números nos permite traducir esas operaciones sintácticas del lenguaje a operaciones numéricas (expresables en ese mismo lenguaje).

27 Junio, 2009, 07:07 pm
Respuesta #121

Gustavo Piñeiro

  • Visitante
Tres relaciones numéricas que nos serán de mucha utilidad son: prefijo, sufijo y parte.

Asumimos que todos los números se escriben en sl sistema binario sin cero.

Un número \( x \) es prefijo de \( y \) si \( x \) aparece al comienzo de la escritura de \( y \). Por ejemplo, 112 es  prefijo de 11222211 y también de 1121111. Todo número es prefijo de sí mismo.

Un número \( x \) es sufijo de \( y \) si \( x \) aparece al final de la escritura de \( y \). Por ejemplo, 112 es  sufijo de 1122112 y también de 1111112. Todo número es sufijo de sí mismo.

Un número \( x \) es parte de \( y \) si \( x \) aparece en algún lugar dentro la escritura de \( y \). Por ejemplo, 112 es parte de 11112122.

Es fácil ver que \( x \) es prefijo de \( y \) si y sólo si \( x = y \) o bien existe \( z \) tal que \( y \) es la concatenación de \( x \) y \( z \) en ese orden. Por lo tanto la relación "\( x \) es prefijo de \( y \)" es expresable.

De la misma manera se prueba que las relaciones "\( x \) es sufijo de \( y \)" y "\( x \) es parte de \( y \)" son también expresables.

30 Junio, 2009, 03:14 am
Respuesta #122

Gustavo Piñeiro

  • Visitante
"Ser el código de una expresión" es una propiedad expresable:

Esto se debe a que "x es el código de una expresión" equivale a la conjunción de:

1. 1 es prefijo de x.
2. 2 es sufijo de x.
3. 22 no es parte de x.
4. 111111111111112 no es parte de x. (En el número inicial el 1 aparece 14 veces.)

Nótese que si 111111111111112 no es parte de x (el 1 catorce veces) entonces un número con una cantidad mayor de unos (y un 2 al final) tampoco es parte de x.

En la condición 4 el 1 aparece 14 veces porque hay 13 símbolos en el lenguaje por lo que 111111111111112 (el 1 catorce veces) no es el código de un símbolo. Si el lenguaje tuviera n símbolos, en la condición 4 aparecería n + 1 veces la cifra 1. Si el lenguaje tuviera una cantidad infinita numerable de símbolos la condición 4 se omitiría.

30 Junio, 2009, 04:05 am
Respuesta #123

Gustavo Piñeiro

  • Visitante
"Ser el código de la constante 0" es una propiedad expresable:

El código de la constante 0 es 112, que es la escritura en binario sin cero del número 8. Luego "x es el código de la constante 0" equivale a "x = SSSSSSSS0" (donde la S se ha escrito 8 veces).

30 Junio, 2009, 07:49 pm
Respuesta #124

Gustavo Piñeiro

  • Visitante
"Ser el código de una variable" es una propiedad expresable:

Recordemos que los símbolos que usamos para escribir las variables, \( v \) y \( {}_| \), son, respectivamente, el 12º y 13º de nuestra lista y sus códigos, en consecuencia, son 1111111111112 y 11111111111112 (con 12 y 13 unos respectivamente).

Luego "x es el código de una variable" equivale a la conjunción de:

1. x es el código de una expresión.
2. El código de \( v \) es prefijo de x. (Es decir, la expresión de la que x es código comienza con \( v \).)
3. 211111111111112 (con 13 unos) es sufijo de x. (Es decir, la expresión de la que x es código termina con \( {}_| \).)
4. 212, 2112, 21112,..., 2111111111112 (la cantidad de unos va de uno a once) no son parte de x. (Es decir, en la expresión no aparece ningún otro símbolo más que \( v \) y \( {}_| \).)
5. 21111111111112 no es parte de x (el 1 aparece 12 veces). (Es decir, \( v \) aparece sólo una vez, al principio de la expresión.)

01 Julio, 2009, 06:58 pm
Respuesta #125

Gustavo Piñeiro

  • Visitante
"Ser el código de un término" es expresable:

Llegamos aquí a un punto delicado en la demostración.

Comencemos observando que la relación binaria "x es el código de un símbolo que aparece en la expresión de código y" es expresable porque equivale a la conjunción de:

1. y es el código de una expresión.
2. x = 12 o x = 112 o ... o x = 11111111111112. (En el último número la cifra 1 aparece 13 veces.)
3. x es un prefjo de y, o bien la concatenación de 2 con x es parte de y.

De ahora en adelante, para evitar que la notación oscurezca las ideas vamos a identificar a cada código con su expresión correspondiente y nos referiremos a relaciones entre expresiones en lugar de relaciones entre códigos de expresiones.

De esta manera, para decir que "x es el código de un símbolo que aparece en la expresión de código y" es expresable diremos que si s es un símbolo y E es una expresión entonces la relación "s aparece en E" es expresable. (Se trata del mismo concepto, sólo estamos aliviando un poco la escritura.)

Llamaremos expresión aritmética a una expresión en la que no aparezca el símbolo especial \( \otimes{} \). Es claro que "Ser una expresión aritmética" es expresable.

También es expresable la relación "H es una sucesión de expresiones aritméticas" ya que equivale a la conjunción de:

1. \( \otimes{} \) es prefijo de H.
2. \( \otimes{} \) es sufijo de H.
3. \( \otimes{}\otimes{} \) no es parte de H.

También es expresable la relación "E es una expresión aritmética que es miembro de la sucesión de expresiones aritméticas H" (o sea, la relación, "x es el código de una expresión aritmética que aparece en la sucesión de expresiones aritméticas que tiene código y" es expresable). Su expresión es la conjunción de:

1. E es una expresión aritmética.
2. H es una sucesión de expresiones aritméticas.
3. \( \otimes{} \)E\( \otimes{} \) es parte de H. (Traducido a una relación entre códigos: la concatenación del código de \( \otimes{} \) con x con el código de \( \otimes{} \) es parte de y.)

También es expresable: "E y F son miembros de H y alguna aparición de E en H precede a alguna aparición de F en H". La relación de precedencia se expresa diciendo que hay una parte de H que es una sucesión de expresiones aritméticas en la que \( \otimes{} \)E\( \otimes{} \) es un prefijo y \( \otimes{} \)F\( \otimes{} \) es un sufijo.

Continuará...

02 Julio, 2009, 01:33 am
Respuesta #126

Gustavo Piñeiro

  • Visitante
Continúo...

Recordemos que un término es una expresión que se obtiene a partir del 0 y de las variables por aplicaciones sucesivas de las tres operaciones sintácticas siguientes:

1. La operación que a partir de las expresiones E y F construye la expresión (E + F).
2. La operación que a partir de las expresiones E y F construye la expresión (E . F).
3. La operación que a partir de la expresión E construye la expresión S(E)  (donde S es el símbolo que representa a la función sucesor).

Veamos que las tres operaciones son expresables, es decir:

1. La función que, dados los códigos de las expresiones E y F, calcula el código de la expresión (E + F) es expresable. En efecto, esto se debe a que el código de (E + F) es la concatenación de los siguientes números (en el orden que se indican): el código del símbolo "(", el código de E, el código del símbolo "+", el código de F y el código del símbolo ")".

2. De forma similar se prueba que también es expresable la función que, dados los códigos de las expresiones E y F, calcula el código de la expresión (E . F).

3. Y de forma similar también es expresable la función que, dado el código de la expresión E, calcula el código de la expresión S(E).

Definición: Una sucesión generadora de términos es una sucesión de expresiones aritméticas tal que si E es una expresión de la sucesión entonces:

a) E es la constante 0 o es una variable. O bien,
b) Existen dos expresiones F y G que preceden a E en la sucesión tales que E = (F + G) (la igualdad debe entenderse en el sentido sintáctico, es decir, una igualdad símbolo a símbolo). O bien,
c) Existen dos expresiones F y G que preceden a E en la sucesión tales que E = (F . G). O bien,
d) Existe una expresión F que precede a E en la sucesión tal que E = S(F).

Es claro que una expresión es un término si y sólo se es la última expresión en una sucesión generadores de términos.

Vimos antes que:

1. "Ser una expresión aritmética" es expresable.
2. "Ser una variable o ser la constante 0" es expresable.
3. "Ser una sucesión de expresiones aritméticas" es expresable.
4. "Ser miembro de una sucesión de expresiones aritméticas" es expresable.
5. Dados dos miembros de una sucesión de expresiones aritméticas "Alguna aparición de uno de ellos precede en la sucesión a alguna aparición de la otra" es expresable.
6. Las operaciones que generan términos son expresables.
7. "Ser la última expresión en una sucesión de expresiones aritméticas" es expresable.

De todo esto se deduce que "Ser un término" es expresable.

02 Julio, 2009, 03:07 am
Respuesta #127

Gustavo Piñeiro

  • Visitante
Podemos generalizar de la siguiente manera el razonamiento que hicimos para probar que "Ser un término" es expresable:

Supongamos que tenemos ciertas expresiones aritméticas iniciales (que en el caso de los términos serían la constante 0 y las variables) y una cantidad finita de operaciones sintácticas permitidas (que no involucran al símbolo \( \otimes{} \)). Llamaremos expresión generada a cualquier expresión que, o bien es una expresión inicial, o bien se obtiene a partir de una cantidad finita de expresiones iniciales por aplicaciones sucesivas (una cantidad finita de veces) de las operaciones sintácticas permitidas. (Es fácil ver que toda expresión generada será necesariamente una expresión aritmética.)

En esta situación, así como antes hemos hablado de sucesiones generadoreas de términos podemos ahora hablar de sucesiones generadoras (o "sucesiones generadoras de expresiones generadas", si se me permite el trabalenguas).

Razonando como hicimos para los términos se puede probar que:

Principio de Generación: Si "Ser una expresión inicial" es expresable y también son expresables las operaciones sintácticas permitidas entonces "Ser una sucesión generadora" y "Ser una expresión generada" son también expresables.

(Este Principio de Generación es fundamental en la demostración y me atrevo a decir que, de una u otra forma, más explícitamente o menos explícitamente, aparece en todas las versiones de la demostración del Teorema de Gödel. En la demostración original de Gödel, el principio aparece en el hecho de que existe una función, que Gödel llama función \( \beta  \), que permite expresar sucesiones finitas de números.)

Recordemos que una fórmula atómica es una fórmula del tipo (t = s), donde t y s son términos. Dado que "Ser un término" es expresable, deducimos inmediatamente que "Ser una fórmula atómica" es expresable.

Por otra parte, las fórmulas se obtienen a partir de las fórmulas atómicas por aplicaciones sucesivas de los cuantificadores y conectivos lógicos. Aplicando a esta situación el Principio de Generación tenemos que "Ser una fórmula" es expresable.

02 Julio, 2009, 03:22 am
Respuesta #128

Gustavo Piñeiro

  • Visitante
Si tomamos como expresiones iniciales a los axiomas y como operaciones permitidas a las reglas de inferencia entonces las sucesiones generadoras son exactamente las demostraciones y las expresiones generadas son las fórmulas demostrables.

Es fácil ver, gracias a la concatenación, que las reglas de inferencia (pensadas como operaciones sintácticas) son expresables. Por lo tanto, si "Ser un axioma" fuera expresable el Principio de Generación nos diría que "Ser una demostración" y "Ser una fórmula demostrable" serían también expresables.

La pregunta es: ¿"Ser un axioma" es expresable? En el próximo comentario nos dedicaremos a responderla.

02 Julio, 2009, 04:07 am
Respuesta #129

Gustavo Piñeiro

  • Visitante
Antes de pasar a la cuestión de si "Ser un axioma" es expresable debemos hacer una pequeña digresión técnica acerca de las variables libres.

Notemos que la definición de "\( x \) aparece libre en la fórmula \( P \)" no es tan simple como decir que "\( x \) no esté precedida por el cuatificador \( \exists{x} \)" (recordemos que en nuestro lenguaje sólo usamos este cuantificador). Para convencernos de esto supongamos que \( P(x) \), \( Q(y) \) y \( R(x,y) \) sean fórmulas atómicas (es decir, sin cuantificadores) en las que aparecen solamente las variables indicadas en cada caso. Entonces:

En \( \exists{x}Q(y)\Rightarrow P(x) \) la variable \( x \) aparece libre.
En \( \exists{x}(Q(y)\Rightarrow P(x)) \) (agregamos solamente un par de paréntesis) la variable \( x \) aparece ligada ("ligada" es lo contrario de "libre").
En \( \exists{x}(Q(y)\Rightarrow P(x))\Rightarrow R(x,y) \) la variable \( x \) tiene una aparición ligada y otra libre.

En los tres casos \( x \) está precedida por el cuatificador \( \exists{x} \), pero la situación de \( x \) es distinta en cada fórmula.

Dejo como ejercicio para los lectores (ejercicio que se resuelve usando los métodos que hemos venido usando), por una parte dar una definición exacta de "\( x \) aparece libre en la fórmula \( P \)" y por otra parte escribir la demostración de que:

1. "Todas las apariciones de la variable x en la fórmula P son ligadas" es expresable (y, en consecuencia, también es expresable "Alguna aparición de x en P es libre").

2. La función que, dados el código de la fórmula P(x) y el código del término t, calcula el código de P(x/t), es expresable.

(A veces se deja como ejercicio a los lectores las demostraciones que son largas y tediosas de escribir con todo detalle. Debo ser honesto y advertirles que éste es precisamente el caso.)

<<                >>