Números de Gödel
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
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
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.