Número de Gödel

Em lógica matemática, uma numeração de Gödel é uma função matemática que atribui a cada símbolo e fórmula bem formada de alguma linguagem formal um único número natural, chamado seu número de Gödel. O conceito foi usado pela primeira vez por Kurt Gödel para a prova de seu teorema da incompletude.

A numeração de Gödel pode ser interpretada como uma codificação em que um número é atribuído a cada símbolo da notação matemática, após o qual uma sequência de números naturais pode representar uma seqüência de caracteres. Estas sequências de números naturais podem voltar a ser representadas por um único número natural, facilitando a sua manipulação nas teorias formais da aritmética.

Desde que o artigo de Gödel foi publicado em 1931, o termo "numeração de Gödel" tem sido usado para se referir a atribuições mais genéricas dos números naturais em objetos matemáticos.

Codificação de Gödel

Gödel utilizou um sistema de numeração de Gödel baseada na fatoração de primos. Primeiro, ele atribuiu um número natural único para cada símbolo básico na linguagem formal da aritmética com a qual ele estava lidando.

Para codificar uma fórmula completa, que é uma seqüência de símbolos, Gödel utilizou o seguinte sistema. Dada uma seqüência $x_{1}x_{2}x_{3}...x_{n}$ de números inteiros positivos, a codificação de seqüência de Gödel é o produto dos n primeiros números primos elevados a seus valores correspondentes na seqüência:

$\mathrm {enc} (x_{1}x_{2}x_{3}\dots x_{n})=2^{x_{1}}\cdot 3^{x_{2}}\cdot 5^{x_{3}}\cdots p_{n}^{x_{n}}.\,$

De acordo com o teorema fundamental da aritmética, qualquer número obtido desta forma pode ser unicamente fatorado em fatores primos, por isso, é possível recuperar a seqüência original de seu número de Gödel (para qualquer número n dado de símbolos a serem codificados).

Gödel usou este esquema especificamente a dois níveis: primeiro, para codificar seqüências de símbolos que representam fórmulas e, segundo, para codificar seqüências de fórmulas que representam as provas. Isso lhe permitiu mostrar uma correspondência entre as afirmações sobre números naturais e afirmações sobre a demonstrabilidade de teoremas sobre números naturais, a observação-chave da prova.

Existem formas mais sofisticadas (e mais concisas) de construir uma numeração de Gödel para seqüências.

Exemplo

Na numeração específica de Gödel utilizada por Nagel e Newman, o número de Gödel para o símbolo "0" é 6 e o número de Gödel para o símbolo "=" é 5. Assim, no seu sistema, o número de Gödel da fórmula "0 = 0" é de 2⁶ × 3⁵ × 5⁶ = 243,000,000.

A falta de singularidade

A numeração de Gödel não é única, de modo que, para qualquer prova usando números de Gödel, existem infinitamente muitas maneiras nas quais estes números poderiam ser definidos.

Por exemplo, supondo que há K símbolos básicos, uma numeração de Gödel alternativa poderia ser construída pelo mapeamento inverso deste conjunto de símbolos (através, por exemplo, uma função inversa h) para o conjunto de dígitos de um sistema numeral bijetivo de base-K. A fórmula consistindo de uma seqüência de n símbolos $s_{1}s_{2}s_{3}\dots s_{n}$, seria então mapeada para o número

$h(s_{1})\times K^{(n-1)}+h(s_{2})\times K^{(n-2)}+\cdots +h(s_{n-1})\times K^{1}+h(s_{n})\times K^{0}.$

Em outras palavras, colocando o conjunto de K símbolos básicos em alguma ordem fixa, de tal forma que o i^ésimo símbolo corresponde unicamente ao i^ésimo dígito de um sistema numeral bijetivo de base K, cada fórmula pode servir apenas como o próprio número do seu próprio número de Gödel.

Aplicação à aritmética formal

Depois que uma numeração de Gödel para uma teoria formal é estabelecida, cada regra de inferência da teoria pode ser expressa como uma função dos números naturais. Se f é o mapeamento de Gödel e, se a fórmula C pode ser obtida a partir de fórmulas A e B através de uma regra de inferência r, ou seja,

$A,B\vdash _{r}C,\$

então deve haver alguma função aritmética g_r dos números naturais tal que

$g_{r}(f(A),f(B))=f(C).\$

Isto é verdade para a numeração de Gödel utilizada, e para qualquer outra numeração onde a fórmula codificada pode ser aritmeticamente recuperada a partir de seu número de Gödel.

Assim, em uma teoria formal, tal como aritmética de Peano em que se pode fazer afirmações sobre os números e as relações aritméticas entre si, pode-se usar uma numeração de Gödel para indiretamente fazer declarações sobre a própria teoria. Esta técnica permitiu Gödel provar os resultados sobre a consistência e integridade das propriedades de sistemas formais.

Generalizações

Em Teoria da computabilidade, o termo "numeração de Gödel" é usado em contextos mais gerais do que o descrito acima. Pode se referir a:

1. Qualquer atribuição dos elementos de uma linguagem formal para números naturais de modo a que os números podem ser manipulados por um algoritmo para simular a manipulação dos elementos da linguagem formal.
2. Mais geralmente, uma atribuição dos elementos de um objeto matemático contável, tal como um grupos contável, para números naturais para permitir a manipulação do algoritmo do objeto matemático.

Além disso, a numeração de Gödel termo é por vezes usada quando os "números" designados são, na verdade cadeias de caracteres, o que é necessário quando se consideram os modelos de computação, tais como máquinas de Turing que manipulam strings ao invés de números.

Conjuntos de Gödel

Conjuntos de Gödel são por vezes utilizados na teoria dos conjuntos para codificar as fórmulas, e são semelhantes aos números de Gödel, exceto que o primeiro usa conjuntos de números em vez de números para fazer a codificação. Nos casos mais simples quando se usa hereditariamente conjuntos finitos para codificar fórmulas este é essencialmente equivalente à utilização de números de Gödel, mas um pouco mais fácil de definir porque a estrutura da árvore das fórmulas podem ser modeladas pela estrutura da árvores dos conjuntos.

Ver também

• Teorema da Incompletude de Gödel
• Complexidade de Kolmogorov

Referências

• 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.
• Gödel's Proof por Ernest Nagel e James R. Newman (1959). Este livro fornece uma boa introdução e um resumo da prova, com uma grande seção dedicada a numeração de Gödel.

Leituras Posteriores

• Gödel, Escher, Bach: an Eternal Golden Braid, by Douglas Hofstadter. Este livro define e usa uma numeração de Gödel alternativa.
• I Am a Strange Loop por Douglas Hofstadter. Esta é uma versão mais recente livro de Hofstadter, que inclui a história da numeração de Gödel.