Numeração de Gödel - Gödel numbering

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

Uma numeração de Gödel pode ser interpretada como uma codificação na qual um número é atribuído a cada símbolo de uma notação matemática , após a qual uma seqüência de números naturais pode então representar uma seqüência de símbolos. Essas sequências de números naturais podem novamente ser representadas por números naturais únicos, facilitando sua manipulação nas teorias formais da aritmética.

Desde a publicação do artigo de Gödel em 1931, o termo "numeração de Gödel" ou "código de Gödel" tem sido usado para se referir a atribuições mais gerais de números naturais a objetos matemáticos.

Visão geral simplificada

Gödel observou que as declarações dentro de um sistema podem ser representadas por números naturais. O significado disso era que as propriedades das declarações - como sua verdade e falsidade - seriam equivalentes a determinar se seus números de Gödel tinham certas propriedades. Os números envolvidos podem ser muito longos (em termos de número de dígitos), mas isso não é uma barreira; tudo o que importa é que podemos mostrar que esses números podem ser construídos.

Em termos simples, planejamos um método pelo qual cada fórmula ou afirmação que pode ser formulada em nosso sistema obtém um número único, de modo que possamos converter mecanicamente entre fórmulas e números de Gödel. Claramente, existem muitas maneiras de fazer isso. Dada qualquer afirmação, o número para o qual ela é convertida é conhecido como seu número de Gödel. Um exemplo simples é a maneira como o inglês é armazenado como uma sequência de números em computadores que usam ASCII ou Unicode :

• A palavra OLÁ é representada por (72,69,76,76,79) usando ASCII decimal .
• A fórmula lógica x=y => y=x é representada por (120,61,121,32,61,62,32,121,61,120) usando ASCII decimal.

Codificação de Gödel

Gödel usou um sistema baseado na fatoração primária . Ele primeiro atribuiu um número natural único a cada símbolo básico na linguagem formal da aritmética com a qual estava lidando.

Para codificar uma fórmula inteira, que é uma sequência de símbolos, Gödel usou o seguinte sistema. Dada uma sequência de números inteiros positivos, a codificação de Gödel da sequência é o produto dos primeiros n primos elevados aos seus valores correspondentes na sequência: ${\ displaystyle (x_ {1}, x_ {2}, x_ {3}, ..., x_ {n})}$

${\ displaystyle \ 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 (e, em particular, um número obtido desta forma) pode ser fatorado exclusivamente em fatores primos , portanto, é possível recuperar a sequência original de seu número de Gödel (para qualquer número n de símbolos a serem codificados).

Gödel usou especificamente esse esquema em dois níveis: primeiro, para codificar sequências de símbolos que representam fórmulas e, segundo, para codificar sequências de fórmulas que representam provas. Isso permitiu que ele mostrasse uma correspondência entre afirmações sobre números naturais e afirmações sobre a comprovação de teoremas sobre números naturais, a observação-chave da prova. ( Gödel 1931 )

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

Exemplo

Na numeração de Gödel específica usada 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, em seu sistema, o número de Gödel da fórmula "0 = 0 "é 2 ⁶ × 3 ⁵ × 5 ⁶ = 243.000.000.

Falta de singularidade

São possíveis infinitas numerações de Gödel diferentes. Por exemplo, supondo que existem K símbolos básicos, uma numeração alternativa Gödels poderia ser construída por invertibly mapear esse conjunto de símbolos (por meio, por exemplo, uma função invertível h ) para o conjunto de dígitos de um bijective base- K numeral sistema . Uma fórmula que consiste em uma string de n símbolos seria então mapeada para o número ${\ displaystyle s_ {1} s_ {2} s_ {3} \ dots s_ {n}}$

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

Em outras palavras, ao colocar o conjunto de K símbolos básicos em alguma ordem fixa, de modo que o -ésimo símbolo corresponda exclusivamente ao -ésimo dígito de uma base bijetiva- sistema numeral K , cada fórmula pode servir apenas como o próprio numeral de seu próprio número de Gödel.${\ displaystyle i}$${\ displaystyle i}$

Por exemplo, a numeração descrita aqui tem K = 1000.

Aplicação à aritmética formal

Recursão

Pode-se usar a numeração de Gödel para mostrar como as funções definidas pela recursão de curso de valores são de fato funções recursivas primitivas .

Expressando declarações e provas por números

Uma vez 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 nos números naturais. Se f é o mapeamento de Gödel er é uma regra de inferência, então deve haver alguma função aritmética g _r de números naturais de modo que se a fórmula C é derivada das fórmulas A e B por meio de uma regra de inferência r , ou seja,

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

então

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

Isso é verdadeiro para a numeração usada por Gödel e para qualquer outra numeração em que a fórmula codificada possa ser recuperada aritmeticamente de seu número de Gödel.

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

Generalizações

Na teoria da computabilidade , o termo "numeração de Gödel" é usado em configurações mais gerais do que as descritas acima. Pode referir-se a:

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

Além disso, o termo numeração de Gödel às vezes é usado quando os "números" atribuídos são, na verdade, strings, o que é necessário ao considerar modelos de computação como máquinas de Turing que manipulam strings em vez de números.

Conjuntos Gödel

Os conjuntos de Gödel às vezes são usados ​​na teoria dos conjuntos para codificar fórmulas e são semelhantes aos números de Gödel, exceto que se usa conjuntos em vez de números para fazer a codificação. Em casos simples, quando alguém usa um conjunto finito hereditariamente para codificar fórmulas, isso é essencialmente equivalente ao uso dos números de Gödel, mas um pouco mais fácil de definir porque a estrutura em árvore das fórmulas pode ser modelada pela estrutura em árvore dos conjuntos. Os conjuntos de Gödel também podem ser usados ​​para codificar fórmulas em idiomas infinitários .

Veja também

• Codificação de igreja
• Número da descrição
• Numeração de Gödel para sequências
• Teoremas da incompletude de Gödel
• Teorema da incompletude de Chaitin

Referências

• Gödel, Kurt (1931), "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" (PDF) , Monatshefte für Mathematik und Physik , 38 : 173–198, arquivado do original (PDF) em 11/04/2018 , recuperado em 07/12/2013 .
• Prova de Gödel por Ernest Nagel e James R. Newman (1959). Este livro fornece uma boa introdução e resumo da prova, com uma grande seção dedicada à numeração de Gödel.

Leitura adicional

• Gödel, Escher, Bach: an Eternal Golden Braid , de Douglas Hofstadter . Este livro define e usa uma numeração de Gödel alternativa.
• I Am a Strange Loop de Douglas Hofstadter . Este é um livro mais recente de Hofstadter que inclui a história da numeração de Gödel.
• Visualizando o Turing Tarpit de Jason Hemann e Eric Holk. Usa a numeração de Gödel para codificar programas.