Numeración de Gödel

Este artículo incluye una lista de referencias generales , pero carece de suficientes citas en línea correspondientes . Ayúdenos a mejorar este artículo introduciendo citas más precisas. ( Abril de 2021 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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.

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; lo único 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 .

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 números 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},\puntos ,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 .

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.

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}\puntos 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 de su propio número de Gödel.${\estilo de visualización i}$${\estilo de visualización i}$

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

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 .

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 .

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 ]}

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 .

• 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

• 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.

• 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.