Numeración de Gödel
En la teoría de los números formales, una numeración de Gödel es una función que asigna a cada símbolo y fórmula de un lenguaje formal un único número natural llamado número de Gödel (GN). El concepto fue utilizado por primera vez por Kurt Gödel para la demostración de su teorema de incompletitud.
Una 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, y un flujo de números naturales puede entonces representar alguna forma o función. Una numeración del conjunto de funciones computables puede entonces ser representada por un flujo de números de Gödel (también llamados números efectivos). El teorema de equivalencia de Rogers establece los criterios por los que esas numeraciones del conjunto de funciones computables son numeraciones de Gödel.
Definición
Dado un conjunto contable S, una numeración de Gödel es una función inyectiva
f : S → N {\displaystyle f:S\to \mathbb {N} } } 
siendo tanto f como f - 1 {\displaystyle f^{-1}} 
(la inversa de f) son funciones computables.
Ejemplos
Notación base y cadenas
Uno de los esquemas de numeración de Gödel más sencillos se utiliza a diario: La correspondencia entre los números enteros y sus representaciones como cadenas de símbolos. Por ejemplo, la secuencia 2 3 se entiende, por un conjunto particular de reglas, como el número veintitrés. Del mismo modo, las cadenas de símbolos de un alfabeto de N símbolos pueden codificarse identificando cada símbolo con un número de 0 a N y leyendo la cadena como la representación de base N+1 de un número entero.
Preguntas y respuestas
P: ¿Qué es una numeración de Gödel?
R: Una numeración de Gödel es una función que asigna un número natural único a cada símbolo y fórmula de un lenguaje formal, llamado número de Gödel (GN).
P: ¿Quién utilizó por primera vez el concepto de numeración de Gödel?
R: Kurt Gödel utilizó por primera vez el concepto de numeración de Gödel para la demostración de su teorema de incompletitud.
P: ¿Cómo podemos interpretar la numeración de Gödel?
R: Podemos interpretar la numeración de Gödel como una codificación en la que a cada símbolo de una notación matemática se le asigna un número, y un flujo de números naturales puede representar alguna forma o función.
P: ¿Cómo llamamos a los números naturales asignados por una numeración de Gödel?
R: Los números naturales asignados por una numeración de Gödel se llaman números de Gödel o números efectivos.
P: ¿Qué afirma el teorema de equivalencia de Rogers?
R: El teorema de equivalencia de Rogers establece los criterios por los que aquellas numeraciones del conjunto de funciones computables son numeraciones de Gödel.
P: ¿Qué representa una serie de numeraciones de Gödel?
R: Una numeración del conjunto de funciones computables se puede representar por una corriente de números de Gödel.
P: ¿Por qué es importante la numeración de Gödel en la teoría formal de números?
R: La numeración de Gödel es importante en la teoría formal de números ya que proporciona una forma de representar fórmulas y funciones matemáticas como números naturales, lo que permite demostrar teoremas importantes como el teorema de incompletitud.
