Numeración de Gödel

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)

Una numeración de Gödel se puede interpretar como una codificación en la que se asigna un número a cada símbolo de una notación matemática, después de lo cual una secuencia de números naturales puede representar una secuencia de símbolos. Estas secuencias de números naturales pueden representarse nuevamente por 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 Gödel" se ha utilizado para referirse a asignaciones más generales de números naturales a objetos matemáticos.

Resumen simplificado

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 declaración, 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 realmente muy grandes, 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 declaración 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 usan ASCII. Dado que 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 es representado por 102111120121.
• La fórmula lógica x=y => y=x es representado por 120061121032061062032121061120.

Codificación de Gödel

Gödel usó un sistema basado en 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 toda una fórmula, que es una secuencia de símbolos, Gödel utilizó el siguiente sistema. Dada una secuencia ()x1,x2,x3,...,xn){displaystyle (x_{1},x_{2},x_{3},x_{n}}} de enteros positivos, la codificación de Gödel de la secuencia es el producto de la primera n primos elevados a sus valores correspondientes en la secuencia:

enc()x1,x2,x3,...... ,xn)=2x1⋅ ⋅ 3x2⋅ ⋅ 5x3⋯ ⋯ pnxn.{displaystyle mathrm {enc} (x_{1},x_{2},x_{3},dotsx_{n}=2^{x_{1}cdot 3^{x_{2}cdot 5^{x_{3}}cdots.

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 manera ú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 usó 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.

Ejemplo

En la numeración específica de Gödel 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

Infinitamente muchos diferentes Las numeraciones de Gödel son posibles. Por ejemplo, suponiendo que hay K símbolos básicos, una numeración Gödel alternativa se podría construir mediante la cartografía invertible de este conjunto de símbolos (por ejemplo, una función invertible h) al conjunto de dígitos de un sistema bijetivo base-K numeral. Una fórmula que consiste en una cadena de n símbolos s1s2s3...... sn{displaystyle S_{1}s_{3}dots s_{n} entonces se asignará al número

h()s1)× × K()n− − 1)+h()s2)× × K()n− − 2)+⋯ ⋯ +h()sn− − 1)× × K1+h()sn)× × K0.{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, colocando el conjunto de K símbolos básicos en algún orden fijo, tal que i{displaystyle i}-el símbolo corresponde únicamente al i{displaystyle i}- el dígito de una base bijeactiva...K sistema numeral, cada fórmula puede servir como el mismo numeral de su propio número de Gödel.

Por ejemplo, la numeración descrita aquí tiene k = 1000.

Aplicación a la aritmética formal

recurre

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

Expresando declaraciones y pruebas por 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 puede expresarse como una función en los números naturales. Si f es el mapeo Gödel y r es una regla de inferencia, entonces debería haber alguna función aritmética g _r de números naturales de tal manera que si la fórmula c se deriva de las fórmulas a y b a través de una regla de inferencia r , es decir

A,B⊢ ⊢ rC,{displaystyle A,Bvdash _{r}C,}

entonces

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

Esto es cierto para la numeración de Gödel utilizado, y para cualquier otra numeración donde la fórmula codificada se puede recuperar aritméticamente de su número Gödel.

Por lo tanto, en una teoría formal como la aritmética de maní en la que se pueden hacer declaraciones sobre los números y sus relaciones aritméticas entre sí, se puede usar una numeración de Gödel para hacer declaraciones indirectamente sobre la teoría misma. Esta técnica permitió a Gödel probar los resultados sobre la consistencia e integridad de las propiedades de los sistemas formales.

Generalizaciones

En la teoría de la computabilidad, el término " Gödel numeración " se usa en configuraciones más generales que la descrita 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.
2. Más generalmente, 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.

Además, el término numeración de gödel a veces se usa cuando los números asignados "#34; en realidad son cadenas, lo cual es necesario cuando se considera modelos de cálculo, como máquinas Turing que manipulan las cadenas en lugar de los números.

Gödel conjuntos

Los conjuntos de gödel a veces se usan en la teoría de conjuntos para codificar fórmulas, y son similares a los números de Gödel, excepto que uno usa conjuntos en lugar de números para hacer la codificación. En casos simples, cuando uno usa un conjunto hereditario 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 los árboles de las fórmulas puede ser modelada por la estructura de los árboles de los conjuntos. Los conjuntos de Gödel también se pueden usar para codificar fórmulas en idiomas infinitarios.