Numeración de Gödel

Numeración de Gödel

En teoría de los números un número de Gödel es una función que asigna a cada símbolo y fórmula de un lenguaje formal un número único, denominado Número de Gödel (GN). El concepto fue utilizado por primera vez por Kurt Gödel para la demostración del teorema de Incompletitud de Gödel.

La enumeración de un conjunto de funciones computables se denomina también enumeración de Gödel o enumeración efectiva. Una enumeración de Gödel se puede interpretar como un lenguaje de programación donde los números de Gödel están asignados a cada función computable igual que los programas que calculos los valores para la función en este lenguaje de programación.

Contenido

Definición

Dado un conjunto enumerable S, una enumeración de Gödel es una función

f:S \to \mathbb{N}

donde f y la inversa de f son funciones computables.

Ejemplo

Paso 1

Los números de Gödel se construyen con referencia a símbolos de cálculo proposicional y la aritmética formal. Cada símbolo se asigna primero a un número natural, por tanto:

.

Símbolos lógicos Números 1:12
¬ 1 ("no")
\forall 2 ("para todos")
\rightarrow 3 ("si, entonces")
\vee 4 ("o")
\wedge 5 ("y")
( 6
) 7
S 8 ("es el sucesor de")
0 9
= 10
. 11
+ 12
Símbolos proposicionales Números más grandes que 10 y divisibles por 3
P 12
Q 15
R 18
S 21
Variables individuales Nombres más grandes que 10 con resto 1 cuando se dividen por 3
v 13
x 16
y 19
Símbolos de predicado Nombres más grandes que 10 con resto 2 cuando se dividen por 3
E 14
F 17
G 20

Y así para todos los símbolos posibles. La sintaxis del cálculo proposicional asegura que no hay ambigüedad entre el símbolo "P" y el símbolo "+" aunque ambos estén asignados al número 12.

Paso 2

A cada enunciado aritmético se le asigna un número de Gödel único utilizando series de números primos. Se basa básicamente en el siguiente código: 1er primo carácter × 2º primo carácter × 3er primo carácter etc.
Por ejemplo el enunciado \forallx, P (x) se convierte en
22 × 316 × 512 × 76 × 1116 × 137, porque {2, 3, 5, 7, 11, ...} es la serie de primos, y 2, 16, 12, 6, 16, 7 son los códigos de los caracteres. Este es un número bastante grande, pero perfectamente determinado: 14259844433335185664666562849653536301757812500.

Es importante ver que, por el teorema fundamental de la aritmética, este número tan grande se puede descomponer en sus factores primos, y por tanto se puede convertir un número de Gódel en la secuencia de caracteres original.

Paso 3

Finalmente, a las secuencias de enunciados se les asigna un número de Gödel, de manera que la secuencia
Enunciado 1 (GN1)
Enunciado 2 (GN2)
Enunciado 3 (GN3)
(donde GN significa número de Gödel)

tiene el número de Gödel 2GN1×3GN2×5GN3, que denominaremos GN4.

La demostración del teorema de incompletitud de Gödel se basa en la demostración de que, en aritmética formal, algunos conjuntos de enunciados prueban otros enunciados de forma lógica. Por ejemplo, se puede probar que la unión de GN1, GN2 y GN3 (es decir GN4) prueban GN5. Como esta es una relación demostrable entre dos números, se le asigna su propio símbolo, por ejemplo R. Entonces se puede escribir R (v, x) para expresar que x demuestra v. En el caso anterior donde x y v son los números de Gödel GN4 y GN5, se podría escribir R(GN5, GN4).

Una demostración informal

El argumento central de la demostración hecha por Gödel se basa en que puede escribirse

\forallx, ¬R (v, x)

que quiere decir

ninguna sentencia de tipo v se puede probar.

El número de Gödel para esta sentencia sería

22 × 316 × 51 × 718 × 116 × 1313 × 1716 × 197

que se puede denominar GN6. Ahora, si se considera la sentencia

\forallx, ¬R(GN6,x),

que de hecho está diciendo

ninguna sentencia que afirme 'ninguna sentencia de tipo v se puede probar' puede probarse.

Que equivale a

esta sentencia no se puede probar.

Si esta última sentencia se puede probar, entonces su sistema formal es inconsistente porque demuestra una sentencia que ella misma afirma que no se puede demostrar (contradicción). Si la sentencia no se puede probar dentro del sistema formal, entonces lo que afirma la sentencia es cierto, y por tanto la sentencia es consistente, pero como el sistema contiene una afirmación que es semánticamente cierta pero que no se puede probar (sintácticamente), entonces el sistema es incompleto.

Véase también

  • Codificación de Church

Referencias

  • Gödel, Kurt, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", Monatsheft für Math. und Physik 38, 1931, S.173-198.

Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Teoremas de incompletitud de Gödel — Kurt Gödel a los 19 años de edad, cinco años antes de la demostración de los teoremas. Los teoremas de incompletitud de Gödel son dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1930. Ambos están relacionados con la… …   Wikipedia Español

  • Kurt Gödel — Para el lenguaje de programación, véase Gödel (lenguaje de programación). Kurt Gödel Kurt Gödel Nacimiento 28 de abril …   Wikipedia Español

  • Alfred Tarski — Nacimiento 14 de enero …   Wikipedia Español

  • Metalógica — La metalógica es el estudio de las propiedades y los componentes de los sistemas lógicos.[1] Contenido 1 Propiedades metalógicas 1.1 Consistencia 1.2 Decidibilidad …   Wikipedia Español

  • Cálculo lambda — Artículo parcialmente traducido: Contiene texto en inglés. Ayuda a terminarlo. El cálculo lambda es un sistema formal diseñado para investigar la definición de función, la noción de aplicación de funciones y la recursión. Fue introducido por… …   Wikipedia Español

  • Número computable — En matemáticas, especialmente en ciencia computacional teórica y lógica matemática, los números computables o recursivos son los números reales que pueden ser computados con la precisión que se desee por un algoritmo finito. Se puede llegar al… …   Wikipedia Español

  • Aritmética — Este artículo trata sobre la aritmética elemental. Para otros usos de este término, véase teoría de números. Alegoría de la Aritmética. Pintura de Laurent de La Hyre. La aritmética (del lat. arithmetĭcus, y este del gr. ἀριθμητικός …   Wikipedia Español

  • Cálculo — Saltar a navegación, búsqueda Para otros usos de este término, véase Cálculo (desambiguación). Para cálculo infinitesimal (diferencial o integral) véase Cálculo infinitesimal Para el estudio de los números reales, los complejos, los vectores y… …   Wikipedia Español

  • Historia de la matemática — Página del Compendio de cálculo por el método de completado y balanceado de Muhammad ibn Mūsā al Khwārizmī (820 d.C.) La historia de las matemáticas es el área de estudio que abarca las investigaciones sobre los orígenes de los descubrimi …   Wikipedia Español

  • Historia de la notación matemática — Este artículo o sección necesita una revisión de ortografía y gramática. Puedes colaborar editándolo (lee aquí sugerencias para mejorar tu ortografía). Cuando se haya corregido, borra este aviso por favor. La notación matemática comprende los… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”