Codage de Gödel

Gödel a noté que les déclarations dans un système peuvent être représentées par des entiers naturels. La signification de cela était que les propriétés des déclarations—telles que leur vérité et leur fausseté—équivaudraient à déterminer si leurs code de Gödel avaient certaines propriétés. Les nombres impliqués pourraient être très long (en termes de nombre de chiffres), mais ce n'est pas une barrière ; tout ce qui compte, c'est que nous pouvons montrer que ces chiffres peuvent être construits.

En termes simples, nous concevons une méthode par laquelle chaque formule ou déclaration qui peut être formulée dans notre système obtient un nombre unique, de telle sorte que nous pouvons nous convertir mécaniquement entre les formules et les nombres de Gödel. De toute évidence, il existe de nombreuses façons de le faire. Compte tenu de toute déclaration, le numéro auquel il est converti est connu sous le nom de son numéro de Gödel. Un exemple simple est la façon dont les langues sont stockées comme une suite de nombres dans des ordinateurs utilisant ASCII ou Unicode :

• Le mot HELLO est représenté par 72-69-76-76-79 en utilisant ASCII.
• L'énoncé logique x=y => y=x est représenté par 120-61-121-32-61-62-32-121-61-120 en utilisant ASCII.

Gödel a utilisé un système basé sur la factorisation en nombre premier. Il a d'abord attribué un entier naturel unique à chaque symbole de base dans le langage formel de l'arithmétique.

Pour coder une formule entière, qui est une séquence de symboles, Gödel a utilisé le système suivant. Une suite finie ${\displaystyle (x_{1},x_{2},x_{3},...,x_{n})}$ d'entiers strictement positifs, est codée par le produit des n premiers nombres premiers élevés à leurs valeurs correspondantes dans la suite :

${\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}}.\,}$

Le théorème fondamental de l'arithmétique assure que deux suites finies distinctes ont deux codes distincts, et il est donc possible de retrouver la suite à partir de son code.

Gödel a utilisé ce schéma à deux niveaux : d'abord pour coder des suites de symboles représentant des formules, puis pour coder des suites de formules représentant des preuves. Cela lui a permis d'exprimer par un énoncé arithmétique, modulo codage, la prouvabilité d'un énoncé arithmétique, un élément nécessaire de la preuve.

Dans la numérotation spécifique de Gödel utilisée par Nagel et Newman, le code de Gödel pour le symbole « 0 » est 6 et le code Gödel pour le symbole « = » est 5. Ainsi, dans leur système, le nombre de Gödel de la formule « 0 = 0 » est 2⁶ × 3⁵ × 5⁶ = 243 000 000.

Une numérotation de Gödel n'est pas unique, car pour toute preuve utilisant les codes de Gödel, il existe une infinité de façons dont ces nombres pourraient être définis.

Par exemple, en supposant qu'il y ait des symboles de base K, un codage de Gödel alternative pourrait être construite en associant de manière invariable cet ensemble de symboles (par exemple, une fonction inversible h) à l'ensemble des chiffres d'un système de numération bijectif K. Une formule composée d'une chaîne de n symboles ${\displaystyle s_{1}s_{2}s_{3}\dots s_{n}}$erait alors associée au numéro

${\displaystyle 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}.}$

En d'autres termes, en plaçant l'ensemble de K symboles de base dans un ordre fixe, de sorte que le i^th symbole correspond uniquement au i^th nombre d'un système de numération bijectif K, chaque formule peut servir, tout comme le nombre même, de son propre code de Gödel.

Par exemple, la numérotation décrite ici a K = 10000.

En théorie de la calculabilité, le terme « codage de Gödel » est utilisé dans des cas plus généraux que celui décrit ci-dessus. Il peut se référer à:

1. Toute affectation des éléments d'un langage formel à des entiers naturels de telle sorte que les nombres peuvent être manipulés par un algorithme pour simuler la manipulation d'éléments du langage formel.
   
2. Plus généralement, une affectation d'éléments à partir d'un objet mathématique dénombrable, tel qu'un groupe dénombrable, à des entiers naturels permettant une manipulation algorithmique de l'objet mathématique.
   

En outre, le terme de codage de Gödel est parfois utilisé lorsque ce sont des chaînes de caractères qui servent de codes, ce qui est nécessaire lorsque l'on considère des modèles de calcul tels que des machines de Turing qui manipulent des chaînes, plutôt que des nombres.

Les ensembles de Gödel sont parfois utilisés en théorie des ensembles pour coder les formules, et sont similaires aux codes de Gödel, sauf que l'on utilise des ensembles plutôt que des nombres pour effectuer l'encodage. Dans les cas simples, lorsqu'on utilise un ensemble héréditairement fini pour coder des formules, cela est essentiellement équivalent à l'utilisation des codes de Gödel, mais un peu plus facile à définir, car la structure arborescente des formules peut être modélisée par l'arborescence des ensembles. Les ensembles de Gödel peuvent également être utilisés pour coder des formules dans des logiques infinies.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Gödel numbering » (voir la liste des auteurs).