Une technique de codage (arithmétisation) qui assigne des codes entiers naturels à des objets syntaxiques (symboles, formules, suites, preuves) de sorte que les relations syntaxiques deviennent exprimables et manipulables arithmétiquement.

Principe

Définir un codage bijectif effectif des symboles et des suites finies vers les entiers naturels (par exemple via un encodage par puissances de nombres premiers) afin que concaténation, substitution et relations de preuve correspondent à des relations arithmétiques sur les codes.

Démonstration

Gödel a encodé symboles et suites finies en nombres entiers pour que le prédicat « x encode une preuve de la formule y » soit représentable en arithmétique ; cette arithmétisation est au cœur des théorèmes d'incomplétude.

Mauvaise application

Employer la numérotation de Gödel sans distinguer l'existence d'un code et la décidabilité effective du décodage, ou utiliser des encodages impraticablement grands pour des tâches algorithmiques ; supposer que l'arithmétisation fournit des procédures efficaces.

Conséquence

Permet d'exprimer des affirmations syntaxiques et métamathématiques à l'intérieur de l'arithmétique, autorisant l'autoréférence, la formalisation de prédicats de preuve et des résultats fondamentaux d'indécidabilité et d'incomplétude.

Inversion

La réversion consiste à considérer la syntaxe comme non numérique ou à utiliser des encodages symboliques de haut niveau sans codes entiers explicites ; refuser l'arithmétisation empêche d'intérioriser la syntaxe dans l'arithmétique.

Limite

Nécessite un langage formel à syntaxe effective et un schéma d'encodage convenu ; les choix de codage ne sont pas uniques et n'accordent pas en eux-mêmes décidabilité ou efficience computationnelle.

Tension sémantique

Tension entre la vue syntaxique abstraite et l'encodage arithmétique : l'encodage rend la syntaxe accessible aux outils arithmétiques mais introduit des choix et une complexité absents du niveau abstrait.

Synthèse

La numérotation de Gödel encode systématiquement les objets syntaxiques en nombres naturels afin que l'arithmétique puisse représenter et raisonner sur preuves et formules, fournissant l'outil technique de l'autoréférence et des résultats d'indécidabilité formelle.