Codage de Gödel

En logique mathématique, un codage de Gödel (ou numérotation de Gödel) est une fonction qui attribue à chaque symbole et formule bien-formée de certains langages formels un entier naturel unique, appelé son code de Gödel, ou numéro de Gödel. Le concept a été utilisé par Kurt Gödel pour la preuve de ses théorèmes d'incomplétude[1].

Un codage de Gödel peut être interprété comme un codage dans lequel un numéro est attribué à chaque symbole d'une notation mathématique, après quoi une séquence d'entiers naturels peut alors représenter une séquence de symboles. Ces séquences d'entiers peuvent encore être représentées par des entiers naturels isolés, facilitant leur manipulation dans les théories formelles de l'arithmétique.

Depuis la publication de l'article de Gödel en 1931, le terme « numérotation de Gödel » ou « code de Gödel » a été utilisé pour désigner des assignations plus générales d'entiers naturels à des objets mathématiques.

Aperçu simplifié

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.

Codage de Gödel

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  d'entiers strictement positifs, est codée par le produit des n premiers nombres premiers élevés à leurs valeurs correspondantes dans la suite :

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.

Exemple

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 26 × 35 × 56 = 243 000 000.

Manque d'unicité

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 erait alors associée au numéro

En d'autres termes, en plaçant l'ensemble de K symboles de base dans un ordre fixe, de sorte que le ith symbole correspond uniquement au ith 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.

Application à l'arithmétique formelle

Expression de preuves par des nombres

Une fois qu'un codage de Gödel pour une théorie formelle est établi, chaque règle d'inférence de la théorie peut s'exprimer comme une fonction sur les entiers naturels. Si f est le mappage de Gödel et si la formule C peut être dérivée des formules A et B par une règle d'inférence r; c'est-à-dire.

Alors il devrait y avoir une fonction arithmétique gr  d'entiers naturels tels que

Cela est vrai pour le codage de Gödel utilisé et pour tout autre codage où la formule codée peut être récupérée arithmétiquement à partir de son code.

Ainsi, dans une théorie formelle telle que l'arithmétique de Peano dans laquelle on peut faire des affirmations sur les nombres et leurs relations arithmétiques, on peut utiliser un codage de Gödel pour faire indirectement des déclarations sur la théorie elle-même. Cette technique a permis à Gödel de prouver les résultats sur les propriétés de cohérence et d'exhaustivité des systèmes formels.

Généralisations

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é[réf. nécessaire] 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.

Ensembles de Gödel

Les ensembles de Gödel[réf. nécessaire] 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.

Notes et références

  1. (de) Kurt Gödel, « Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I », Monatshefte für Mathematik und Physik, vol. 38, , p. 173–198 (DOI 10.1007/BF01700692, S2CID 197663120, lire en ligne [archive du ], consulté le )

Voir aussi

Articles connexes

Lectures complémentaires

  • Portail de la logique
  • Portail de l'informatique théorique
  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.