Epistemowikia
Revista «Hiperenciclopédica» de Divulgación del Saber
Segunda Época, Año VII
Vol. 6, Núm. 4: de octubre a diciembre de 2012 (en curso)
Epistemowikia es parte de
Logotipo de CALA Virtual
CALA → ALA | Communitas | Evolvere
Editio | Epistemowikia | Exercitatio | Fictor | Flor
Epistemowikia no se hace responsable ni se identifica necesariamente con el contenido ni las opiniones expresadas por sus colaboradores.
La Universidad de Extremadura no se hace en ningún caso responsable de los contenidos publicados en Epistemowikia.
La Asociación Conocimiento Comunal (CONOMUN) no se hace en ningún caso responsable de los contenidos publicados por terceros.
[editar] Inicio | La revista | Índex | Hemeroteca | Búsquedas | Quiénes somos | Contacto | Publica

Numeración de Gödel

De Epistemowikia

Tabla de contenidos

Introducción

La numeración de Gödel, dentro de la lógica matemática, se corresponde con una función que asigna un único número natural a cada uno de los símbolos y fórmulas bien formadas de un determinado lenguaje formal. A este número único se le denomina Número de Gödel y fue utilizado en una primera instancia para la comprobación del Teorema de Incompletitud de Gödel por él mismo.

Una numeración de Gödel puede ser interpretada como una codificación en la que un número es asignado a cada símbolo de una notación matemática, después de la cual una secuencia de números naturales puede entonces representar una secuencia de cadenas. Estas secuencias de números naturales pueden ser a su vez representadas por números naturales individuales, facilitando así su manipulación en teorías formales de la aritmética.


Por tanto, su definición es la siguiente:

Sea S un conjunto numerable, entonces una numeración de Gödel es una función f:S \to \mathbb{N} en la que f y su inversa son ambas funciones computables.


Desde el año 1936, en el que Gödel publicó su artículo, este término ha venido usándose para una gran variedad de asignaciones de objetos matemáticos a números naturales.

Codificación de Gödel

Gödel usó un sistema de numeración basado en la descomposición de factores primos; primeramente asignó un único número natural a cada símbolo básico en el lenguaje formal de la aritmética en cuestión con la que estaba tratando.

Con el fin de codificar una fórmula de forma completa, la cual se corresponde con una secuencia de símbolos, Gödel usó el siguiente sistema:

Dada una secuencia de enteros positivos x1x2x3...xn, la codificación de Gödel de la secuencia es el producto de los n primeros números primos elevados a los correspondientes valores de la secuencia, es decir: 

            Codificacion (x_{1} x_{2} x_{3} ... x_{n}) = 2^{x_{1}}*3^{x_{2}}*5^{x_{3}}*...*p_{n}^{x_{n}}

Según el Teorema fundamental de la aritmética, cualquier número obtenido por este método puede ser descompuesto en factores primos de forma única, de tal forma que es posible recuperar la secuencia original desde su número de Gödel de forma efectiva.

Gödel usó este esquema expresamente a dos niveles: el primero, para codificar secuencias de símbolos que representan fórmulas, y el segundo para codificar secuencias de fórmulas que representan demostraciones. Esto le permitió mostrar una correspondencia entre declaraciones sobre números naturales y declaraciones acerca de la probabilidad de los teoremas sobre números naturales.

Hay formas más sofisticadas y a su vez más concisas para construir una numeración de Gödel para secuencias aparte de la comentada.

Falta de unicidad

La numeración de Gödel no es única, la idea general es convertir fórmulas en números naturales.

Por ejemplo, supongamos que hay K símbolos básicos, una alternativa a la numeración de Gödel podría ser construida convirtiendo cada uno de los símbolos básicos en un dígito de un sistema numérico de base K a través de una función de correspondencia h, entonces, una fórmula que se corresponde con una cadena de n símbolos s1s2s3...sn podría ser convertida al número siguiente: 

    h(s_1) \times K^{(n-1)} + h(s_2) \times K^{(n-2)} + \cdots + h(s_{n-1}) \times K^1 + h(s_n) \times K^0

Aplicación a la aritmética formal

Una vez que la numeración de Gödel está establecida para una teoría formal, cada regla de inferencia de dicha teoría puede ser expresada como una función de números naturales.

Si f es la correspondencia de Gödel y si la fórmula C puede ser derivada de las fórmulas A y B a través de una regla de inferencia r, como por ejemplo: 

   A, B \vdash_r C

Entonces, habría una función aritmética gr de números naturales tal que: 

    g_r(f(A),f(B)) = f(C) \

Esto es cierto para la numeración de Gödel usada y para cualquier otro tipo de numeración donde las fórmulas codificadas se pueden recuperar aritméticamente desde su número de Gödel.

De esta manera, en una teoría formal como la aritmética de Peano en la que se pueden crear declaraciones sobre números y sus relaciones aritméticas de forma mutua, uno puede usar una numeración de Gödel para crear indirectamente declaraciones sobre su teoría. Esta técnica permitió a Gödel probar resultados acerca de la consistencia y la plenitud de las propiedades de los sistemas formales.

Generalizaciones

En la Teoría de la computabilidad, el término "Numeración de Gödel" se usa en entornos más generales que el que se ha descrito anteriormente. De este modo, puede referirse a:

1. Cualquier asignación de los elementos de un lenguaje formal a números naturales de forma que estos números pueden ser manipulados por un algoritmo para simular la manipulación de los elementos de un lenguaje formal.

2. De forma más general, una asignación de elementos desde un objeto matemático contable, como un grupo contable, a números naturales para permitir la manipulación algorítmica del objeto matemático.

El término numeración de Gödel es también usado algunas veces cuando los "números" asignados son realmente cadenas, siendo necesario por ejemplo cuando se consideran modelos de computación tales como las máquinas de Turing, que manipulan más cadenas que números.

Hay, por tanto, muchos significados para el término numeración de Gödel relacionados con las numeraciones de la clase de funciones computables.

Fuentes

Licencia









Esta obra se publica multilicenciadamente con las siguientes licencias. Por tanto, usted es libre de reproducir, distribuir, comunicar públicamente, interpretar y transformar, por cualquier medio, con o sin ánimo de lucro, la presente obra, en cualquier momento o lugar, licenciando o multilicenciando, según sea el caso, la obra original o la obra derivada, con una de las siguientes licencias o con un subconjunto de ellas:





Obtenido de "http://campusvirtual.unex.es/cala/epistemowikia/index.php?title=Numeraci%C3%B3n_de_G%C3%B6del"
Herramientas personales