ChapitreCalculabilité

Arithmétique dans l'arithmétique de Peano

L'arithmétique de Robinson démontre tous les calculs sur des chiffres, mais pas les lois générales qui demandent une récurrence : ni la commutativité de l'addition, ni même que tout entier est inférieur ou égal à lui-même. Le schéma de récurrence de l'arithmétique de Peano les donne toutes, à condition de le manier dans le système formel, sous des hypothèses où la variable de récurrence n'est pas libre. On en tire les lois de l'addition et de la multiplication, l'ordre et ses quantifications bornées, le principe du plus petit élément, la division euclidienne, le théorème de Bézout et le lemme chinois pour deux modules, chacun démontré dans l'arithmétique de Peano.

Le chapitre s'achève sur l'équivalence, démontrable dans l'arithmétique de Peano, de toute formule de la plus petite classe qui contient les formules Δ₀ et qui est stable par conjonction, disjonction, quantification existentielle et quantification universelle bornée, avec une formule à un seul quantificateur existentiel devant une formule Δ₀. C'est la première étape de la démonstration, dans l'arithmétique de Peano, des conditions de dérivabilité qui manquent encore au second théorème d'incomplétude.