ChapitreCalculabilité

Arithmétisation de la syntaxe

Les mots du langage de l'arithmétique sont codés par des entiers, et chacune des notions syntaxiques de la logique, terme, formule, occurrence libre, substitution, instance de tautologie, axiome logique, démonstration formelle, devient une relation primitive récursive sur les codes.

L'outil est la récurrence de valeurs : un mot se reconnaît à partir de ses facteurs propres, dont les codes sont plus petits. C'est l'arithmétisation que Gödel a menée en 1931, et sur laquelle repose le chapitre « Calculabilité et incomplétude ».