Codage de Gödel

Auteur: Leandro Alegsa Date de création: 9 mai 2021

Dans la théorie des nombres formels, une numérotation de Gödel est une fonction qui attribue à chaque symbole et formule d'un langage formel un nombre naturel unique appelé nombre de Gödel (GN). Ce concept a été utilisé pour la première fois par Kurt Gödel pour la preuve de son théorème d'incomplétude.

Une numérotation de Gödel peut être interprétée comme un codage dans lequel un nombre est attribué à chaque symbole d'une notation mathématique, et un flux de nombres naturels peut alors représenter une forme ou une fonction. Une numérotation de l'ensemble des fonctions calculables peut alors être représentée par un flux de nombres de Gödel (également appelés nombres effectifs). Le théorème d'équivalence de Rogers énonce des critères pour lesquels ces numérotations de l'ensemble des fonctions calculables sont des numéros de Gödel.

Définition

Étant donné un ensemble dénombrable S, une numérotation de Gödel est une fonction injective

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

avec les deux f et f - 1 {\displaystyle f^{-1}} $f^{-1}$ (l'inverse de f) étant des fonctions calculables.

Exemples

Notation de base et chaînes de caractères

L'un des systèmes de numérotation de Gödel les plus simples est utilisé tous les jours : La correspondance entre les nombres entiers et leurs représentations sous forme de chaînes de symboles. Par exemple, la séquence 2 3 est comprise, par un ensemble particulier de règles, comme correspondant au nombre vingt-trois. De même, les chaînes de symboles d'un alphabet de N symboles peuvent être codées en identifiant chaque symbole par un nombre de 0 à N et en lisant la chaîne comme la représentation de base N+1 d'un entier.

Questions et réponses

Q : Qu'est-ce qu'une numérotation de Gödel ?

R : Une numérotation de Gödel est une fonction qui attribue un nombre naturel unique à chaque symbole et formule d'un langage formel, appelé nombre de Gödel (GN).

Q : Qui a utilisé pour la première fois le concept de numérotation de Gödel ?

R : Kurt Gödel a utilisé pour la première fois le concept de numérotation de Gödel pour la preuve de son théorème d'incomplétude.

Q : Comment peut-on interpréter la numérotation de Gödel ?

R : Nous pouvons interpréter la numérotation de Gödel comme un encodage où chaque symbole d'une notation mathématique se voit attribuer un nombre, et un flux de nombres naturels peut représenter une forme ou une fonction.

Q : Comment appelons-nous les nombres naturels attribués par une numérotation de Gödel ?

R : Les nombres naturels attribués par une numérotation de Gödel sont appelés nombres de Gödel ou nombres effectifs.

Q : Que dit le théorème d'équivalence de Rogers ?

R : Le théorème d'équivalence de Rogers énonce les critères pour lesquels les numérotations de l'ensemble des fonctions calculables sont des numérotations de Gödel.

Q : Que représente un flux de nombres de Gödel ?

R : Une numérotation de l'ensemble des fonctions calculables peut être représentée par un flot de nombres de Gödel.

Q : Pourquoi la numérotation de Gödel est-elle importante dans la théorie formelle des nombres ?

R : La numérotation de Gödel est importante pour la théorie formelle des nombres car elle permet de représenter les formules et les fonctions mathématiques sous forme d'entiers naturels, ce qui permet de prouver des théorèmes importants comme le théorème d'incomplétude.