Product Design, Manufacturing & Innovation Resources
Hogar » Números de Gödel

Números de Gödel

1931
  • Kurt Gödel
Técnica de numeración de Gödel en lógica matemática con números naturales únicos.

(Imagen generada únicamente con fines ilustrativos)

La numeración de Gödel es una técnica fundamental que asigna un número natural único (un número de Gödel) a cada símbolo, fórmula y demostración en un lenguaje formal. Esta aritmetización de la sintaxis permite codificar enunciados metamatemáticos sobre un sistema formal (por ejemplo, «esta fórmula es demostrable») como enunciados aritméticos sobre números, que luego pueden ser analizados dentro del propio sistema.

La numeración de Gödel es el ingenioso mecanismo que une la sintaxis (la estructura simbólica de un lenguaje formal) con la teoría de números (las propiedades de los enteros). Este proceso permite traducir enunciados lógicos en enunciados numéricos. El método consiste en asignar un entero único a cada símbolo básico del lenguaje formal (por ejemplo, ¬ → 1, ∨ → 2, ∀ → 3, x → 4, etc.).

A formula, which is a sequence of these symbols, can then be assigned its own unique number. Gödel’s original method used prime factorization. For a sequence of symbols with numbers [latex]s_1, s_2, …, s_k[/latex], the formula’s Gödel number would be [latex]2^{s_1} \cdot 3^{s_2} \cdot 5^{s_3} \cdot \dots \cdot p_k^{s_k}[/latex], where [latex]p_k[/latex] is the k-th prime number. Due to the fundamental theorem of arithmetic (unique prime factorization), this mapping is injective; every formula gets a unique number, and from any such number, the original formula can be uniquely recovered.

Finalmente, una demostración, que es una secuencia de fórmulas, puede codificarse de la misma manera, tomando los números de Gödel de sus fórmulas constituyentes y aplicando nuevamente la codificación de potencias de primos. Esta aritmetización completa implica que las propiedades metamatemáticas complejas, como «la secuencia F es una demostración válida de la fórmula P», se convierten en predicados puramente aritméticos que involucran los números de Gödel de F y P. Esto permitió a Gödel construir una fórmula que se refiere a su propia demostrabilidad, el paso clave en su demostración de incompletitud.

UNESCO Nomenclature: 1201
– Matemáticas puras

Tipo

Sistema abstracto

Ruptura

Sustancial

Uso

Conceptual/Teórico

Precursores

  • geometría analítica (el mapeo de Descartes de la geometría al álgebra)
  • El concepto de Leibniz de una "característica universal"
  • the fundamental theorem of arithmetic (unique prime factorization)
  • formalization of languages in logic by Frege and Russell
  • El trabajo de Cantor sobre las correspondencias entre conjuntos

Aplicaciones

  • computability theory (representing turing machines and programs as numbers)
  • computer science (the principle that code is data)
  • information theory
  • criptografía
  • formal language theory
  • proofs of undecidability, such as the halting problem

Patentes:

NA

Ideas para posibles innovaciones

Debido al bloqueo del tráfico generado por bots, que actualmente supera los 40.000 al día, este contenido está reservado para los miembros de la comunidad.
> Iniciar sesión < o > Registrarse < (100% gratis) para acceder a esto, al igual que a todo el demás contenido y herramientas restringidos.

Relacionado con: número de Gödel, aritmetización, sintaxis, metamatemáticas, codificación, lenguaje formal, teoría de la demostración, computabilidad, autorreferencia, factorización prima.

Contexto histórico

Números de Gödel

1924
1925
1930
1931
1939
1940
1950
1922
1925
1928
1930
1936
1940
1943
1950

(Si la fecha es desconocida o no es relevante, por ejemplo "mecánica de fluidos", se proporciona una estimación redondeada de su aparición notable)

Invención, innovación y principios técnicos relacionados.

Las imágenes a tamaño completo y las descargas sólo están disponibles, 100% gratis, para los miembros registrados.

> Acceso <