En lógica matemática , una numeración de Gödel es una función que asigna a cada símbolo y fórmula bien formada de algún lenguaje formal un número natural único , llamado número de Gödel . El concepto fue desarrollado por Kurt Gödel para la prueba de sus teoremas de incompletitud . (Gödel 1931)
Una numeración de Gödel puede interpretarse como una codificación en la que a cada símbolo de una notación matemática se le asigna un número , tras lo cual una secuencia de números naturales puede entonces representar una secuencia de símbolos. Estas secuencias de números naturales pueden volver a representarse mediante números naturales únicos, lo que facilita su manipulación en las teorías formales de la aritmética.
Desde la publicación del artículo de Gödel en 1931, el término "numeración de Gödel" o "código de Gödel" se ha utilizado para referirse a asignaciones más generales de números naturales a objetos matemáticos.
Gödel señaló que cada enunciado dentro de un sistema puede representarse mediante un número natural (su número de Gödel ). La importancia de esto era que las propiedades de una afirmación, como su verdad o falsedad, serían equivalentes a determinar si su número de Gödel tenía ciertas propiedades. Las cifras involucradas pueden ser muy grandes, pero esto no es una barrera; lo único que importa es que esos números puedan construirse.
En términos simples, ideó un método mediante el cual cada fórmula o enunciado que se puede formular en el sistema obtiene un número único, de tal manera que las fórmulas y los números de Gödel se pueden convertir mecánicamente de un lado a otro. Hay muchas maneras de hacer esto. Un ejemplo sencillo es la forma en que se almacena el inglés como una secuencia de números en las computadoras usando ASCII . Dado que los códigos ASCII están en el rango de 0 a 127, basta con rellenarlos con 3 dígitos decimales y luego concatenarlos:
x=y => y=xestá representada por120 061 121 032 061 062 032 121 061 120 .Gödel utilizó un sistema basado en la factorización prima . Primero asignó un número natural único a cada símbolo básico en el lenguaje formal de la aritmética con el que estaba tratando.
Para codificar una fórmula completa, que es una secuencia de símbolos, Gödel utilizó el siguiente sistema. Dada una secuencia de números enteros positivos, la codificación de Gödel de la secuencia es el producto de los primeros n primos elevados a sus valores correspondientes en la secuencia:
Según el teorema fundamental de la aritmética , cualquier número (y, en particular, un número obtenido de esta forma) puede factorizarse de forma única en factores primos , por lo que es posible recuperar la secuencia original a partir de su número de Gödel (para cualquier número dado n de símbolos a codificar).
Gödel utilizó específicamente este esquema en dos niveles: primero, para codificar secuencias de símbolos que representan fórmulas, y segundo, para codificar secuencias de fórmulas que representan pruebas. Esto le permitió mostrar una correspondencia entre enunciados sobre números naturales y enunciados sobre la demostrabilidad de teoremas sobre números naturales, la observación clave de la demostración. (Gödel 1931)
Hay formas más sofisticadas (y más concisas) de construir una numeración de Gödel para secuencias .
En la numeración de Gödel específica utilizada por Nagel y Newman, el número de Gödel para el símbolo "0" es 6 y el número de Gödel para el símbolo "=" es 5. Así, en su sistema, el número de Gödel de la fórmula "0 = 0" es 2 6 × 3 5 × 5 6 = 243.000.000.
Son posibles infinitas numeraciones de Gödel diferentes. Por ejemplo, suponiendo que hay K símbolos básicos, se podría construir una numeración de Gödel alternativa mapeando de manera invertible este conjunto de símbolos (a través de, digamos, una función invertible h ) al conjunto de dígitos de un sistema de numeración biyectivo de base K. Una fórmula que consta de una cadena de n símbolos se asignaría entonces al número
En otras palabras, al colocar el conjunto de K símbolos básicos en algún orden fijo, de modo que el -ésimo símbolo corresponda únicamente al -ésimo dígito de un sistema numérico biyectivo de base K , cada fórmula puede servir simplemente como el propio numeral de su propio número de Gödel.
Por ejemplo, la numeración aquí descrita tiene K=1000.
Se puede utilizar la numeración de Gödel para mostrar cómo las funciones definidas por la recursividad del curso de valores son, de hecho, funciones recursivas primitivas .
Una vez que se establece una numeración de Gödel para una teoría formal, cada regla de inferencia de la teoría se puede expresar como una función de los números naturales. Si f es la aplicación de Gödel y r es una regla de inferencia, entonces debería haber alguna función aritmética g r de números naturales tal que si la fórmula C se deriva de las fórmulas A y B mediante una regla de inferencia r , es decir
entonces
Esto es cierto para la numeración utilizada por Gödel y para cualquier otra numeración en la que la fórmula codificada pueda recuperarse aritméticamente a partir de su número de Gödel.
Así, en una teoría formal como la aritmética de Peano , en la que se pueden hacer afirmaciones sobre los números y sus relaciones aritméticas entre sí, se puede utilizar una numeración de Gödel para hacer afirmaciones indirectas sobre la teoría misma. Esta técnica permitió a Gödel demostrar resultados sobre las propiedades de consistencia y completitud de los sistemas formales .
En teoría de la computabilidad , el término "numeración de Gödel" se utiliza en entornos más generales que el descrito anteriormente. Puede referirse a:
Además, el término numeración de Gödel se utiliza a veces cuando los "números" asignados son en realidad cadenas, lo cual es necesario cuando se consideran modelos de computación como las máquinas de Turing que manipulan cadenas en lugar de números. [ cita necesaria ]
Los conjuntos de Gödel se utilizan a veces en la teoría de conjuntos para codificar fórmulas y son similares a los números de Gödel, excepto que se utilizan conjuntos en lugar de números para realizar la codificación. En casos simples, cuando se usa un conjunto hereditariamente finito para codificar fórmulas, esto es esencialmente equivalente al uso de números de Gödel, pero algo más fácil de definir porque la estructura de árbol de las fórmulas puede modelarse mediante la estructura de árbol de los conjuntos. Los conjuntos de Gödel también se pueden utilizar para codificar fórmulas en lenguajes infinitos .
