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

Números de Gödel

1931
  • Kurt Gödel
Técnica de numeração de Gödel na lógica matemática com números naturais exclusivos.

(Imagem gerada apenas para fins ilustrativos)

A Numeração de Gödel é uma técnica fundamental que atribui um número natural único (um número de Gödel) a cada símbolo, fórmula e demonstração em uma linguagem formal. Essa aritmetização da sintaxe permite que afirmações metamatemáticas sobre um sistema formal (por exemplo, "esta fórmula é demonstrável") sejam codificadas como afirmações aritméticas sobre números, que podem então ser analisados ​​dentro do próprio sistema.

A numeração de Gödel é o engenhoso mecanismo que preenche a lacuna entre a sintaxe (a estrutura simbólica de uma linguagem formal) e a teoria dos números (as propriedades dos inteiros). O processo permite que afirmações sobre lógica sejam traduzidas em afirmações sobre números. O método funciona atribuindo-se primeiro um inteiro único a cada símbolo básico da linguagem formal (por exemplo, ∨ → 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, uma demonstração, que é uma sequência de fórmulas, pode ser codificada da mesma maneira, tomando os números de Gödel de suas fórmulas constituintes e aplicando novamente a codificação de potências de primos. Essa aritmetização completa significa que propriedades metamatemáticas complexas, como "a sequência F é uma demonstração válida da fórmula P", tornam-se predicados puramente aritméticos envolvendo os números de Gödel de F e P. Isso permitiu a Gödel construir uma fórmula que se refere à sua própria demonstrabilidade, o passo fundamental em sua demonstração da incompletude.

UNESCO Nomenclature: 1201
Matemática pura

Tipo

Sistema abstrato

Interrupção

Substancial

Uso

Conceitual/Teórico

Precursores

  • geometria analítica (a aplicação da geometria à álgebra segundo Descartes)
  • O conceito de Leibniz de uma "characteristica universalis"
  • o teorema fundamental da aritmética (fatoração única em números primos)
  • formalização de linguagens na lógica por Frege e Russell
  • O trabalho de Cantor sobre mapeamentos entre conjuntos

Aplicações

  • Teoria da computabilidade (representando máquinas de Turing e programas como números)
  • ciência da computação (o princípio de que código são dados)
  • teoria da informação
  • criptografia
  • teoria da linguagem formal
  • provas de indecidibilidade, como o problema da parada

Patentes:

NA

Ideias de Inovação Potencial

Devido ao tráfego de bots de coleta de dados, atualmente superior a 40 mil por dia, este conteúdo é reservado aos membros da comunidade.
> Login < ou > Registrar < (100% gratuito) para acessar isso, assim como todo o restante do conteúdo e das ferramentas restritas.

Relacionado a: número de Gödel, aritmetização, sintaxe, metamatemática, codificação, linguagem formal, teoria da demonstração, computabilidade, autorreferência, fatoração em números primos.

Contexto histórico

Números de Gödel

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

(Caso a data seja desconhecida ou irrelevante, por exemplo, "mecânica dos fluidos", é fornecida uma estimativa aproximada de seu surgimento notável)

Princípios relacionados à invenção, inovação e tecnologia

Imagens em tamanho real e downloads estão disponíveis apenas, 100% gratuitos, para membros registrados.