Numeración de Gödel: codificación aritmética de símbolos, fórmulas y funciones
Numeración de Gödel: descubre la codificación aritmética de símbolos, fórmulas y funciones, su relación con el teorema de incompletitud y la computabilidad.
En la teoría de los números formales, una numeración de Gödel es una función que asigna a cada símbolo y fórmula de un lenguaje formal un único número natural llamado número de Gödel (GN). El concepto fue utilizado por primera vez por Kurt Gödel para la demostración de su teorema de incompletitud. La idea básica es la aritmetización de la sintaxis: transformar objetos sintácticos (símbolos, términos, fórmulas, demostraciones) en números para poder razonar sobre ellos dentro de la propia teoría de números.
Una numeración de Gödel puede interpretarse como una codificación en la que se asigna un número a cada símbolo de una notación matemática, y un flujo de números naturales puede entonces representar alguna forma o función. Una numeración del conjunto de funciones computables puede entonces ser representada por un flujo de números de Gödel (también llamados números efectivos). El teorema de equivalencia de Rogers establece los criterios por los que esas numeraciones del conjunto de funciones computables son numeraciones de Gödel, es decir, que cualquier numeración "efectiva" será equivalente a otra por una biyección computable.
Métodos habituales de codificación
Hay varias maneras de construir una numeración de Gödel; las más comunes explotan propiedades aritméticas básicas para garantizar unicidad y decodificabilidad:
- Codificación por potencias de primos. Se asigna un número natural distinto a cada símbolo (por ejemplo, "(" ↦ 1, ")" ↦ 2, "¬" ↦ 3, "→" ↦ 4, "x" ↦ 5, ...). A una secuencia finita de símbolos s1, s2, ..., sn se le asocia el número gn = 2^{c(s1)} · 3^{c(s2)} · 5^{c(s3)} · ... · p_n^{c(sn)}, donde p_i es la i-ésima prima y c(si) es el código del símbolo si. La unicidad viene de la factorización prima (teorema fundamental de la aritmética), y permite decodificar la secuencia recuperando los exponentes.
- Funciones de emparejamiento y tuplas. Se usan funciones computables como la función de Cantor o emparejamientos recursivos para combinar varios números en uno solo de forma reversible y efectiva. Estas codificaciones suelen ser más compactas y fáciles de manejar en pruebas metamatemáticas.
- Otras variantes. Existen codificaciones que priorizan la eficiancia, la simplicidad o propiedades recursivas concretas (por ejemplo, que las relaciones sintácticas se vuelvan primitivo-recursivas).
Propiedades deseables
- Injectividad. Distintos objetos sintácticos deben recibir distintos números de Gödel.
- Decodificabilidad efectiva. Debe existir un procedimiento efectivo (computable) que, dado un número, recupere el símbolo o la secuencia codificada.
- Representabilidad aritmética. Las relaciones sintácticas importantes (p. ej. "x es una fórmula", "y es una demostración de x", "z resulta de sustituir t por v en x") deben poder ser expresadas por predicados aritméticos sencillos, preferentemente primitivo-recursivos o recursivos, para que la teoría numérica pueda hablar sobre sintaxis.
- Equivalencia efectiva. Diferentes numeraciones «efectivas» suelen ser equivalentes en el sentido de que existe una biyección computable que transforma una numeración en otra (esto es lo que formaliza el teorema de equivalencia de Rogers).
Aplicaciones y papel en la prueba de Gödel
La numeración de Gödel es la herramienta que permitió a Gödel transformar afirmaciones meta-matemáticas sobre fórmulas y demostraciones en afirmaciones aritméticas sobre números. Gracias a una numeración adecuada, conceptos como "x es demostrable" o "x es la codificación de una fórmula que afirma algo sobre su propio número de Gödel" se pueden expresar dentro de la teoría aritmética. Esto facilita la construcción de sentencias autorreferenciales mediante el lema diagonal (o de autorreferencia) y conduce a la formulación de sentencias que dicen, en esencia, "esta sentencia no es demostrable", que es la raíz del teorema de incompletitud.
Ejemplo sencillo
Supongamos un alfabeto reducido con códigos: "(" ↦ 1, ")" ↦ 2, "¬" ↦ 3, "→" ↦ 4, "x" ↦ 5. La fórmula "x→(¬x)" se traduce en la secuencia de códigos [5,4,1,3,5,2] y su número de Gödel mediante potencias de primos sería 2^5 · 3^4 · 5^1 · 7^3 · 11^5 · 13^2. Este número es único para esa secuencia y puede ser factorizado para recuperar la fórmula original.
Variantes modernas y consideraciones prácticas
En trabajos contemporáneos se eligen codificaciones que faciliten pruebas sobre propiedades recursivas: se busca que las relaciones sintácticas sean primitivo-recursivas o al menos recursivas. En teoría de la computación y verificación formal también se usan numeraciones y codificaciones análogas para representar programas, pruebas y entradas en sistemas automáticos. Aunque la codificación por potencias de primos es conceptualmente simple, en la práctica suelen preferirse emparejamientos y codificaciones más compactas y manejables.
Resumen: Una numeración de Gödel es una función efectiva que asigna números naturales únicos a símbolos y objetos sintácticos de un lenguaje formal. Gracias a ella se puede transformar el estudio de la sintaxis en el estudio de propiedades aritméticas, lo que hizo posible la formalización y la demostración del teorema de incompletitud de Gödel y sigue siendo fundamental en lógica matemática, teoría de la computación y teoría de la demostración.
Definición
Dado un conjunto contable S, una numeración de Gödel es una función inyectiva
f : S → N {\displaystyle f:S\to \mathbb {N} } } 
siendo tanto f como f - 1 {\displaystyle f^{-1}} 
(la inversa de f) son funciones computables.
Ejemplos
Notación base y cadenas
Uno de los esquemas de numeración de Gödel más sencillos se utiliza a diario: La correspondencia entre los números enteros y sus representaciones como cadenas de símbolos. Por ejemplo, la secuencia 2 3 se entiende, por un conjunto particular de reglas, como el número veintitrés. Del mismo modo, las cadenas de símbolos de un alfabeto de N símbolos pueden codificarse identificando cada símbolo con un número de 0 a N y leyendo la cadena como la representación de base N+1 de un número entero.
Preguntas y respuestas
P: ¿Qué es una numeración de Gödel?
R: Una numeración de Gödel es una función que asigna un número natural único a cada símbolo y fórmula de un lenguaje formal, llamado número de Gödel (GN).
P: ¿Quién utilizó por primera vez el concepto de numeración de Gödel?
R: Kurt Gödel utilizó por primera vez el concepto de numeración de Gödel para la demostración de su teorema de incompletitud.
P: ¿Cómo podemos interpretar la numeración de Gödel?
R: Podemos interpretar la numeración de Gödel como una codificación en la que a cada símbolo de una notación matemática se le asigna un número, y un flujo de números naturales puede representar alguna forma o función.
P: ¿Cómo llamamos a los números naturales asignados por una numeración de Gödel?
R: Los números naturales asignados por una numeración de Gödel se llaman números de Gödel o números efectivos.
P: ¿Qué afirma el teorema de equivalencia de Rogers?
R: El teorema de equivalencia de Rogers establece los criterios por los que aquellas numeraciones del conjunto de funciones computables son numeraciones de Gödel.
P: ¿Qué representa una serie de numeraciones de Gödel?
R: Una numeración del conjunto de funciones computables se puede representar por una corriente de números de Gödel.
P: ¿Por qué es importante la numeración de Gödel en la teoría formal de números?
R: La numeración de Gödel es importante en la teoría formal de números ya que proporciona una forma de representar fórmulas y funciones matemáticas como números naturales, lo que permite demostrar teoremas importantes como el teorema de incompletitud.
Buscar dentro de la enciclopedia