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.