Numeración de Gödel

Función en lógica matemática

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 su número de Gödel . El concepto fue desarrollado por Kurt Gödel para la demostración de sus teoremas de incompletitud . (Gödel 1931)

La 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 , tras lo cual una secuencia de números naturales puede representar una secuencia de símbolos. Estas secuencias de números naturales pueden representarse a su vez mediante números naturales individuales, lo que facilita su manipulación en 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.

Visión general simplificada

Gödel observó 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 un enunciado (como su verdad o falsedad) serían equivalentes a determinar si su número de Gödel tenía ciertas propiedades. Los números involucrados pueden ser muy grandes, de hecho, pero esto no es una barrera; todo lo que importa es que tales números puedan construirse.

En términos simples, ideó un método por 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 simple es la forma en que el inglés se almacena como una secuencia de números en las computadoras que utilizan ASCII . Como los códigos ASCII están en el rango de 0 a 127, es suficiente rellenarlos con 3 dígitos decimales y luego concatenarlos:

• La palabra foxy está representada por102 111 120 121 .
• La fórmula lógica x=y => y=xestá representada por120 061 121 032 061 062 032 121 061 120 .

Codificación de Gödel

Gödel utilizó un sistema basado en la factorización prima . Primero asignó un número natural único a cada símbolo básico del 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: ${\displaystyle (x_{1},x_{2},x_{3},...,x_{n})}$

${\displaystyle \mathrm {enc} (x_{1},x_{2},x_{3},\dots ,x_{n})=2^{x_{1}}\cdot 3^{x_{2}}\cdot 5^{x_{3}}\cdots p_{n}^{x_{n}}.}$

Según el teorema fundamental de la aritmética , cualquier número (y, en particular, un número obtenido de esta manera) puede ser factorizado 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 demostraciones. Esto le permitió demostrar una correspondencia entre afirmaciones sobre números naturales y afirmaciones 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 .

Ejemplo

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. Por lo tanto, en su sistema, el número de Gödel de la fórmula "0 = 0" es 2 ⁶ × 3 ⁵ × 5 ⁶ = 243.000.000.

Falta de singularidad

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 asignando de forma invertida este conjunto de símbolos (a través, por ejemplo, de una función invertible h ) al conjunto de dígitos de un sistema de numeración biyectivo de base K . Una fórmula que consista en una cadena de n símbolos se asignaría entonces al número ${\displaystyle s_{1}s_{2}s_{3}\dots s_{n}}$

${\displaystyle 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}.}$

En otras palabras, al colocar el conjunto de K símbolos básicos en un orden fijo, de modo que el -ésimo símbolo corresponda únicamente al -ésimo dígito de un sistema numeral biyectivo de base K , cada fórmula puede servir exactamente como el numeral mismo de su propio número de Gödel. ${\displaystyle i}$ ${\displaystyle i}$

Por ejemplo, la numeración descrita aquí tiene K=1000. ^[i]

Aplicación a la aritmética formal

Recursión

Se puede utilizar la numeración de Gödel para mostrar cómo las funciones definidas por la recursión del curso de valores son, de hecho, funciones recursivas primitivas .

Expresar afirmaciones y pruebas mediante números

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 función de Gödel y r es una regla de inferencia, entonces debería haber alguna función aritmética g _r de los 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

${\displaystyle A,B\vdash _{r}C,}$

entonces

${\displaystyle g_{r}(f(A),f(B))=f(C).}$

Esto es válido para la numeración que utilizó 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 le permitió a Gödel demostrar resultados sobre las propiedades de consistencia y completitud de los sistemas formales .

Generalizaciones

En teoría de la computabilidad , el término "numeración de Gödel" se utiliza en contextos más generales que el descrito anteriormente. Puede referirse a:

1. Cualquier asignación de los elementos de un lenguaje formal a números naturales de tal manera que los números puedan ser manipulados por un algoritmo para simular la manipulación de elementos del lenguaje formal. ^{[ cita requerida ]}
2. De manera más general, una asignación de elementos de un objeto matemático contable, como un grupo contable , a números naturales para permitir la manipulación algorítmica del objeto matemático. ^{[ cita requerida ]}

Además, el término numeración de Gödel se utiliza a veces cuando los "números" asignados son en realidad cadenas, lo que es necesario cuando se consideran modelos de computación como las máquinas de Turing que manipulan cadenas en lugar de números. ^{[ cita requerida ]}

Conjuntos de Gödel

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 utiliza un conjunto finito hereditario 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 se puede modelar mediante la estructura de árbol de los conjuntos. Los conjuntos de Gödel también se pueden utilizar para codificar fórmulas en lenguajes infinitarios .

Véase también

• Codificación de la iglesia
• Número de descripción
• Numeración de Gödel para secuencias
• Teoremas de incompletitud de Gödel
• Teorema de incompletitud de Chaitin

Notas

1. Para otro ejemplo, quizás más intuitivo, supongamos que tiene tres símbolos para codificar y elige la base 10 biyectiva por familiaridad (de modo que la enumeración comienza en 1, 10 se representa con un símbolo, por ejemplo, A, y el valor posicional se lleva en 11 en lugar de 10: el decimal 19 seguirá siendo 19, y lo mismo con 21; pero el decimal 20 será 1A ). Usando y la fórmula anterior: ${\displaystyle h(s_{n})=n}$

   ${\displaystyle (1\times 10^{(3-1)}+2\times 10^{(3-2)}+3\times 10^{(3-3)})=(1\times 10^{2}+2\times 10^{1}+3\times 10^{0})=(100+20+3)}$^[ii]

   ...llegamos a nuestra numeración, una característica muy interesante. ${\displaystyle 123}$

2. (o, en forma biyectiva base 10: ) ${\displaystyle 9A+1A+3}$

Referencias

• Gödel, Kurt (1931), "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" (PDF) , Monatshefte für Mathematik und Physik , 38 : 173–198, doi :10.1007/BF01700692, S2CID  197663120, archivado desde el original ( PDF) el 11 de abril de 2018 , consultado el 7 de diciembre de 2013.
• La demostración de Gödel, de Ernest Nagel y James R. Newman (1959). Este libro ofrece una buena introducción y resumen de la demostración, con una gran sección dedicada a la numeración de Gödel.

1. Véase Gödel 1931, pág. 179; la notación de Gödel (véase pág. 176) ha sido adaptada a la notación moderna.

Lectura adicional

• Gödel, Escher, Bach: una eterna trenza dorada , de Douglas Hofstadter . Este libro define y utiliza una numeración alternativa de Gödel.
• Soy un bucle extraño de Douglas Hofstadter . Este es un libro más reciente de Hofstadter que incluye la historia de la numeración de Gödel.
• Visualización del Tarpit de Turing, por Jason Hemann y Eric Holk. Utiliza la numeración de Gödel para codificar programas.