Théorème d'incomplétude de Gödel - Définition

Théorèmes d'incomplétude et calculabilité

La notion de calculabilité intervient à divers titres à propos des théorèmes d'incomplétude. On l'a utilisée pour en définir les hypothèses. Elle intervient dans la preuve du premier théorème d'incomplétude (Gödel utilise les fonctions récursives primitives). Enfin incomplétude et indécidabilité de l'arithmétique sont liées.

Indécidabilité algorithmique

Il y a un lien étroit entre décidabilité algorithmique d'une théorie, l'existence d'une méthode mécanique pour tester si un énoncé est ou non un théorème, et complétude de cette théorie. Une théorie récursivement axiomatisable et complète est décidable. On peut donc prouver le premier théorème d'incomplétude en montrant qu'une théorie qui satisfait les hypothèses utiles est indécidable. Ce résultat, l'indécidabilité algorithmique des théories qui satisfont les hypothèses du premier théorème d'incomplétude, a été démontré indépendamment par Turing et Church en 1936 (voir problème de la décision), en utilisant les méthodes développées par Gödel pour son premier théorème d'incomplétude. Pour un résultat d'indécidabilité, qui est un résultat négatif, il faut avoir formalisé la calculabilité, et être convaincu que cette formalisation est correcte, conviction qui ne peut reposer seulement sur des bases mathématiques. En 1931, Gödel connaît un modèle de calcul que l'on dirait maintenant Turing-complet, les fonctions récursives générales, décrit dans une lettre que Jacques Herbrand lui a adressée, et qu'il a lui-même précisé et exposé en 1934. Cependant il n'est pas convaincu à l'époque d'avoir décrit ainsi toutes les fonctions calculables. À la suite de travaux de Kleene, Church, et Turing, ces deux derniers ont énoncé indépendamment en 1936 la thèse de Church : les fonctions calculables sont les fonctions récursives générales.

On peut être plus précis en donnant une classe restreinte d'énoncés pour laquelle la prouvabilité est indécidable. Si on reprend les arguments développés dans le paragraphe Vérité et démontrabilité ci-dessus, on voit par exemple que la classe des énoncés sans quantificateurs (et sans variables) est, elle, décidable.

En utilisant les arguments développés par Gödel, on montre que la prouvabilité des énoncés Σ₁ est indécidable. Sans entrer dans le détail de la définition des formules Σ₁ (faite ci-dessous), cela ne semble pas si loin d'une solution négative au dixième problème de Hilbert : l'existence d'un algorithme de décision pour la résolution des équations diophantiennes. Mais il fallut plusieurs dizaines d'années et les efforts successifs de plusieurs mathématiciens dont Martin Davis, Hilary Putnam, Julia Robinson et finalement Youri Matiiassevitch pour y arriver en 1970 (voir théorème de Matiiassevitch).

On peut tout à fait déduire le premier théorème de Gödel du théorème de Matiiassevitch. Cela peut paraître artificiel, puisqu'un résultat d'indécidabilité beaucoup plus facile à démontrer suffit. Mais on peut en déduire des énoncés indécidables d'une forme particulièrement simple. En effet, le théorème de Matiiassevitch équivaut à dire que la vérité des énoncés (formules closes) qui s'écrivent comme des égalités polynomiales quantifiées existentiellement, n'est pas décidable. Or :

• on peut reconnaître mécaniquement de tels énoncés, et donc leurs négations ;

• l'ensemble des tels énoncés vrais est récursivement énumérable, et donc, d'après le théorème de Matiiassevitch, l'ensemble des tels énoncés faux n'est pas récursivement énumérable ;

• l'ensemble des théorèmes d'une théorie récursivement axiomatisable est récursivement énumérable (voir Théorie récursivement axiomatisable), et donc l'ensemble des théorèmes qui s'écrivent comme la négation d'une égalité polynomiale quantifiée existentiellement également ;

• l'hypothèse de cohérence que fait Gödel pour son premier théorème d'incomplétude a pour conséquence directe que des égalités quantifiées existentiellement et fausses ne peuvent être démontrables.

On en déduit qu'il existe des énoncés vrais non démontrables, qui s'écrivent comme la négation d'une égalité polynomiale quantifiée existentiellement, ou plus simplement comme une inégalité polynomiale quantifiée universellement.