Numeración de Gödel

En lógica matemática , la numeración de Gödel es una función que asigna a cada símbolo y fórmula bien formada de un lenguaje formal un número natural único , denominado número de Gödel . Kurt Gödel desarrolló este concepto para la demostración de sus teoremas de incompletitud . ^{[ 1 ]}^{: 173–198}

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, a su vez, representarse 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.

Resumen simplificado

Gödel observó que cada enunciado dentro de un sistema puede representarse mediante un número natural (su número de Gödel ). Esto significaba que las propiedades de un enunciado —como su veracidad o falsedad— equivaldrían a determinar si su número de Gödel poseía ciertas propiedades. Los números involucrados podrían ser muy grandes, pero esto no representa un obstáculo; lo importante es que dichos números puedan construirse.

En términos sencillos, Gödel 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 en ambos sentidos. Existen muchas maneras de hacer esto. Un ejemplo sencillo es la forma en que el inglés se almacena como una secuencia de números en las computadoras que utilizan ASCII . Dado que los códigos ASCII están en el rango de 0 a 127, basta con rellenarlos con tres 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 empleó 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 trabajaba.

Para codificar una fórmula completa, que es una secuencia de símbolos, Gödel utilizó el siguiente sistema. Dada una secuencia $(x_{1},x_{2},x_{3},...,x_{n})$ De los 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:

\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 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 n de símbolos a codificar).

Gödel empleó este esquema específicamente en dos niveles: primero, para codificar secuencias de símbolos que representaban fórmulas, y segundo, para codificar secuencias de fórmulas que representaban demostraciones. Esto le permitió demostrar 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 ).

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

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

Si K se elige como una potencia de 10, este esquema hace que sea bastante fácil para un humano convertir entre una cadena de símbolos y su número de Gödel, ya que el número de Gödel representado en base 10 es simplemente la concatenación de los $n$ números decimales $h(s_{i})$ .

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

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 de curso de valores son, de hecho, funciones recursivas primitivas .

Expresar afirmaciones y pruebas mediante números.

Una vez establecida 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 de los números naturales. Si f es la función de Gödel y r es una regla de inferencia, entonces debe existir 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 a través de una regla de inferencia r , es decir

A,B\vdash _{r}C,

entonces

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

Esto es cierto 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 formular afirmaciones sobre los números y sus relaciones aritméticas entre sí, se puede utilizar la numeración de Gödel para formular indirectamente afirmaciones sobre la propia teoría. Esta técnica permitió a Gödel demostrar resultados sobre las propiedades de consistencia y completitud de los sistemas formales .

Generalizaciones

En la 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:

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.
En términos más generales, se trata de 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 de dicho objeto matemático.

Además, el término numeración de Gödel se utiliza a veces cuando los "números" asignados son en realidad cadenas de caracteres, lo cual es necesario al considerar modelos de computación como las máquinas de Turing que manipulan cadenas de caracteres en lugar de números.

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, con la diferencia de que se utilizan conjuntos en lugar de números para la codificación. En casos sencillos, cuando se utiliza 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 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

Notas

↑ La notación de Gödel^{[ 1 ]}^{: 176} se ha adaptado a la notación moderna.
↑ 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 mantiene en 11 en lugar de 10: el decimal 19 seguirá siendo 19, y lo mismo ocurre con el 21; pero el decimal 20 será 1A ). $h(s_{n})=n$ y la fórmula anterior:
$(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)$ ^{[ iii ]}
...llegamos a $123$ como nuestra numeración, una característica ingeniosa.
(o, en forma biyectiva de base 10: $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 (en alemán). 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 .

Nagel, Ernest ; Newman, James R. (1959). La prueba de Gödel .

Lecturas adicionales

Hofstadter, Douglas (1979). Gödel, Escher, Bach: una eterna trenza dorada . Basic Books. ISBN 978-0-465-02656-2.Define y utiliza una numeración de Gödel alternativa.
Hofstadter, Douglas (2007). Soy un bucle extraño . Basic Books. ISBN 978-0-465-03078-1.Incluye la historia de la numeración de Gödel.
Hemann, Jason; Holk, Eric (15 de junio de 2013). «Visualizando el pozo de alquitrán de Turing» (PDF) . Actas del primer taller ACM SIGPLAN sobre arte funcional, música, modelado y diseño . págs. 71-76 . doi : 10.1145/2505341.2505348 . ISBN 978-1-4503-2386-4Archivado del original (PDF) el 27 de septiembre de 2016.Utiliza la numeración de Gödel para codificar los programas.

[2] La notación de Gödel^{[ 1 ]}^{: 176} se ha adaptado a la notación moderna.

[fn1-3] 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 mantiene en 11 en lugar de 10: el decimal 19 seguirá siendo 19, y lo mismo ocurre con el 21; pero el decimal 20 será 1A ). $h(s_{n})=n$ y la fórmula anterior:
$(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)$ ^{[ iii ]}
...llegamos a $123$ como nuestra numeración, una característica ingeniosa.

[fn2-4] (o, en forma biyectiva de base 10: $9A+1A+3$ )

[formal-1] Gödel , Kurt (1931) . "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" (PDF) . Monatshefte für Mathematik und Physik (en alemán). 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 .

[ 1 ]

[ ii ]

[ iii ]