ChapitreCalculabilité

Calculabilité et incomplétude

Tout ensemble récursivement énumérable se définit par une formule de l'arithmétique, grâce à la fonction $\beta$ de Gödel, qui code les suites finies avec l'addition et la multiplication seules. L'ensemble $K$ de l'arrêt se définit donc ainsi, et l'ensemble des énoncés vrais dans $\mathbb N$ ne peut pas être récursivement énumérable.

Comme les théorèmes d'une théorie dont les axiomes forment un ensemble récursivement énumérable en forment un aussi, une telle théorie, si ses axiomes sont vrais dans $\mathbb N$, ne démontre pas tous les énoncés vrais : c'est une forme du premier théorème d'incomplétude. Ce dernier pas s'appuie sur l'arithmétisation de la syntaxe, qui rend primitifs récursifs les ensembles de formules, d'axiomes et de démonstrations ; tout y est démontré, jusqu'à l'incomplétude de l'arithmétique de Peano. Le théorème de Craig y montre enfin qu'une théorie dont les axiomes forment un ensemble récursivement énumérable démontre les mêmes formules qu'une théorie dont les axiomes forment un ensemble primitif récursif.