Numeração Gödel

Autor: Leandro Alegsa

03-04-2021

Na teoria formal dos números, uma numeração Gödel é uma função que atribui a cada símbolo e fórmula de alguma linguagem formal um número natural único chamado de número Gödel (GN). O conceito foi usado pela primeira vez por Kurt Gödel para a prova de seu teorema de incompletude.

Uma numeração Gödel pode ser interpretada como uma codificação onde um número é atribuído a cada símbolo de uma notação matemática, e um fluxo de números naturais pode então representar alguma forma ou função. Uma numeração do conjunto de funções computáveis pode então ser representada por um fluxo de números Gödel (também chamados de números efetivos). O teorema de equivalência de Rogers estabelece os critérios para os quais essas numerações do conjunto de funções computáveis são numerações de Gödel.

Definição

Dado um conjunto S contável, uma numeração Gödel é uma função injectiva

f : S → N {\i1}displaystyle f:S para mathbb {N} } $f:S\to \mathbb {N}$

com f e f - 1 f^{-1}} $f^{-1}$ (o inverso de f) sendo funções computáveis.

Exemplos

Notação de base e cordas

Um dos mais simples esquemas de numeração Gödel é usado todos os dias: A correspondência entre números inteiros e suas representações como cadeias de símbolos. Por exemplo, a seqüência 2 3 é entendida, por um conjunto particular de regras, para corresponder ao número vinte e três. Da mesma forma, cadeias de símbolos de algum alfabeto de símbolos N podem ser codificadas identificando cada símbolo com um número de 0 a N e lendo a cadeia como a representação básica N+1 de um número inteiro.

Perguntas e Respostas

P: O que é uma numeração de Gödel?

R: A numeração de Gödel é uma função que atribui um número natural exclusivo a cada símbolo e fórmula de uma linguagem formal, chamada de número de Gödel (GN).

P: Quem usou o conceito de numeração de Gödel pela primeira vez?

R: Kurt Gödel foi o primeiro a usar o conceito de numeração de Gödel para a prova de seu teorema da incompletude.

P: Como podemos interpretar a numeração de Gödel?

R: Podemos interpretar a numeração de Gödel como uma codificação em que cada símbolo de uma notação matemática recebe um número, e um fluxo de números naturais pode representar alguma forma ou função.

P: Como chamamos os números naturais atribuídos por uma numeração de Gödel?

R: Os números naturais atribuídos por uma numeração de Gödel são chamados de números de Gödel ou números efetivos.

P: O que o teorema de equivalência de Rogers afirma?

R: O teorema de equivalência de Rogers estabelece critérios para os quais as numerações do conjunto de funções computáveis são numerações de Gödel.

P: O que é representado por um fluxo de números de Gödel?

R: Uma numeração do conjunto de funções computáveis pode ser representada por um fluxo de números de Gödel.

P: Por que a numeração de Gödel é importante na teoria formal dos números?

R: A numeração de Gödel é importante na teoria formal dos números, pois fornece uma maneira de representar fórmulas matemáticas e funções como números naturais, o que permite a prova de teoremas importantes, como o teorema da incompletude.