Numero De goDel
Páginas: 8 (1976 palabras)
Publicado: 17 de abril de 2012
NÚMERO DE GÔDEL
En teoría de los números un número de Gödel es una función que asigna a cada símbolo y fórmula de un lenguaje formal un número único, denominado Número de Gödel (GN). El concepto fue utilizado por primera vez por Kurt Gödel para la demostración del teorema de Incompletitud de Gödel.
* La enumeración de un conjunto de funciones computables se denomina también enumeración deGödel o enumeración efectiva. Una enumeración de Gödel se puede interpretar como un lenguaje de programación donde los números de Gödel están asignados a cada función computable igual que los programas de cálculos de los valores para la función en este lenguaje de programación. |
Los números de Gödel se construyen con referencia a símbolos de cálculo proposicional y la aritmética formal. Cadasímbolo se asigna primero a un número natural, por tanto:
Símbolos lógicos | Números 1:12 |
¬ | 1 ("no") |
| 2 ("para todos") |
| 3 ("si, entonces") |
| 4 ("o") |
| 5 ("y") |
( | 6 |
) | 7 |
S | 8 ("es el sucesor de") |
0 | 9 |
= | 10 |
. | 11 |
+ | 12 |
Símbolos proposicionales | Números más grandes que 10 y divisibles por 3 |
P | 12 |
Q | 15 |
R | 18 |
S | 21|
Variables individuales | Nombres más grandes que 10 con resto 1 cuando se dividen por 3 |
v | 13 |
x | 16 |
y | 19 |
Símbolos de predicado | Nombres más grandes que 10 con resto 2 cuando se dividen por 3 |
E | 14 |
F | 17 |
G | 20 |
Y así para todos los símbolos posibles. La sintaxis del cálculo proposicional asegura que no hay ambigüedad entre el símbolo "P" y el símbolo "+"aunque ambos estén asignados al número 12.
El teorema de Gödel
La forma de codificar de Gödel es muy interesante.. Escribir una fórmula lógica es permutar una serie de signos en una serie de espacios, de forma que Gödel atribuye un número a cada signo y un número a cada espacio que ocupa el signo. Para los espacios o lugares que ocupan los signos se utilizan los números primos. 2 para elprimer lugar, 3 para el segundo, 5 para el tercero, etc. Para los signos números convencionales. Por ejemplo 59 para “f1”, 3 para”(“, 15 para “x1”, 5 para “)”. Así “f1” se codifica con el número 2^59. Que quiere decir “f1 en el primer lugar”. Tengamos por ejemplo
“f1(x1)”
f1 en el 1º lugar= 2^59
( enel 2º lugar= 3^3
x1 en el 3º lugar=5^15
) en el 4º lugar= 7^5
El número que surge demultiplicar (2^59 · 3^3 · 5^15 · 7^5) es el número de Gödel de la fórmula “f1(x1)”.
Hay otra manera menos complicada de poner los números de Gödel. Por ejemplo, supongamos que “a” se traduce como 123, e “=” como 111. Entonces, “a = a” se traduciría como:
123111123
Como se ve, ésta es una forma de reducir todas las fórmulas lógicas, y con ello todas las verdades de la aritmética a números. Perolas verdades de la aritmética tratan sobre números, y estas mismas verdades están codificadas por números. Supongamos que la fórmula 123 dice que “1=0”. (Obviamente, esto es una falsedad). Tengamos, ahora, la fórmula
“a no es un teorema en el sistema de Gödel”
Cuando en esta fórmula el signo a es sustituido por el número 123, tenemos una afirmación ambigua, ya que dice a la vez:
“123 no esun teorema en el sistema de Gödel” y “1=0 no es un teorema en el sistema de Gödel”.
Ahora se trata de construir una cadena que se refiera a sí misma[1]. Por ejemplo, tengamos la siguiente fórmula, donde S0 significa el sucesor de 0, o sea 1:
a = S0
Esta fórmula lleva el número 262,111,123,666. Bueno, pues sustituyamos a por el número 262,111,123,666.
La fórmula quedará así:SSSSSSSSS……SSSSS0= S0 262,111,123,666 eses
Esto demuestra que se puede introducir el número de Gödel de una fórmula dentro de la propia fórmula.
Esto lleva a Gödel a construir un extraña fórmula. Esa fórmula afirma (aproximadamente) lo siguiente:
“La fórmula que lleva el número 15215 no es demostrable”
Pero esa misma fórmula, en la demostración de Gödel, lleva el número 15215. Naturalmente es...
En teoría de los números un número de Gödel es una función que asigna a cada símbolo y fórmula de un lenguaje formal un número único, denominado Número de Gödel (GN). El concepto fue utilizado por primera vez por Kurt Gödel para la demostración del teorema de Incompletitud de Gödel.
* La enumeración de un conjunto de funciones computables se denomina también enumeración deGödel o enumeración efectiva. Una enumeración de Gödel se puede interpretar como un lenguaje de programación donde los números de Gödel están asignados a cada función computable igual que los programas de cálculos de los valores para la función en este lenguaje de programación. |
Los números de Gödel se construyen con referencia a símbolos de cálculo proposicional y la aritmética formal. Cadasímbolo se asigna primero a un número natural, por tanto:
Símbolos lógicos | Números 1:12 |
¬ | 1 ("no") |
| 2 ("para todos") |
| 3 ("si, entonces") |
| 4 ("o") |
| 5 ("y") |
( | 6 |
) | 7 |
S | 8 ("es el sucesor de") |
0 | 9 |
= | 10 |
. | 11 |
+ | 12 |
Símbolos proposicionales | Números más grandes que 10 y divisibles por 3 |
P | 12 |
Q | 15 |
R | 18 |
S | 21|
Variables individuales | Nombres más grandes que 10 con resto 1 cuando se dividen por 3 |
v | 13 |
x | 16 |
y | 19 |
Símbolos de predicado | Nombres más grandes que 10 con resto 2 cuando se dividen por 3 |
E | 14 |
F | 17 |
G | 20 |
Y así para todos los símbolos posibles. La sintaxis del cálculo proposicional asegura que no hay ambigüedad entre el símbolo "P" y el símbolo "+"aunque ambos estén asignados al número 12.
El teorema de Gödel
La forma de codificar de Gödel es muy interesante.. Escribir una fórmula lógica es permutar una serie de signos en una serie de espacios, de forma que Gödel atribuye un número a cada signo y un número a cada espacio que ocupa el signo. Para los espacios o lugares que ocupan los signos se utilizan los números primos. 2 para elprimer lugar, 3 para el segundo, 5 para el tercero, etc. Para los signos números convencionales. Por ejemplo 59 para “f1”, 3 para”(“, 15 para “x1”, 5 para “)”. Así “f1” se codifica con el número 2^59. Que quiere decir “f1 en el primer lugar”. Tengamos por ejemplo
“f1(x1)”
f1 en el 1º lugar= 2^59
( enel 2º lugar= 3^3
x1 en el 3º lugar=5^15
) en el 4º lugar= 7^5
El número que surge demultiplicar (2^59 · 3^3 · 5^15 · 7^5) es el número de Gödel de la fórmula “f1(x1)”.
Hay otra manera menos complicada de poner los números de Gödel. Por ejemplo, supongamos que “a” se traduce como 123, e “=” como 111. Entonces, “a = a” se traduciría como:
123111123
Como se ve, ésta es una forma de reducir todas las fórmulas lógicas, y con ello todas las verdades de la aritmética a números. Perolas verdades de la aritmética tratan sobre números, y estas mismas verdades están codificadas por números. Supongamos que la fórmula 123 dice que “1=0”. (Obviamente, esto es una falsedad). Tengamos, ahora, la fórmula
“a no es un teorema en el sistema de Gödel”
Cuando en esta fórmula el signo a es sustituido por el número 123, tenemos una afirmación ambigua, ya que dice a la vez:
“123 no esun teorema en el sistema de Gödel” y “1=0 no es un teorema en el sistema de Gödel”.
Ahora se trata de construir una cadena que se refiera a sí misma[1]. Por ejemplo, tengamos la siguiente fórmula, donde S0 significa el sucesor de 0, o sea 1:
a = S0
Esta fórmula lleva el número 262,111,123,666. Bueno, pues sustituyamos a por el número 262,111,123,666.
La fórmula quedará así:SSSSSSSSS……SSSSS0= S0 262,111,123,666 eses
Esto demuestra que se puede introducir el número de Gödel de una fórmula dentro de la propia fórmula.
Esto lleva a Gödel a construir un extraña fórmula. Esa fórmula afirma (aproximadamente) lo siguiente:
“La fórmula que lleva el número 15215 no es demostrable”
Pero esa misma fórmula, en la demostración de Gödel, lleva el número 15215. Naturalmente es...
Leer documento completo
Regístrate para leer el documento completo.