Avertissement préliminaire : Roughly speaking (vulgairement parlant), le premier théorème d'incomplétude de Gödel est une trivialité. Fondamentalement, il repose sur le paradoxe du menteur.
En effet, soit T une théorie contenant au moins l'arithmétique classique, et soit F la formule du langage qui dit d'elle-même : je ne suis pas démontrable à partir de T. Si F est fausse, c'est qu'elle est démontrable à partir de T, donc T⊢F.
Mais alors, T démontre une formule fausse, ce qui signifie que T est contradictoire.
Par contraposée, on en déduit que si T est consistante, alors elle ne démontre pas F... et du coup F a raison quand elle dit qu'elle n'est pas démontrable à partir de T , c'est-à-dire que F est vraie.
Moralité : On a réussi à fabriquer une formule qui est vraie mais non démontrable... et c'est exactement ce que dit le premier théorème d'incomplétude.
Bien entendu, le raisonnement ci-dessus est extrêmement simplifié, et toute la difficulté de ce chapitre va consister à prouver qu'il existe effectivement une formule qui dit d'elle-même qu'elle n'est pas démontrable. Cette preuve va passer par des constructions alambiquées et des lemmes extrêmement techniques. C'est la raison pour laquelle certaines démonstrations seront seulement esquissées, d'autres purement et simplement omises, renvoyant à des références spécialisées pour les détails.
Ce chapitre constitue une exception dans la structure générale de ce livre. En effet, nous n'allons pas y faire du tout de théorie des ensembles (ou presque pas), et très peu de logique. Par contre nous y ferons beaucoup de récursivité / calculabilité. L'idée est d'introduire une notion convenable de fonction calculable, qui puisse nous servir à arithmétiser la syntaxe et à introduire progressivement les outils qui nous permettront ensuite de démontrer les paradoxes qui mènent aux théorèmes d'indécidabilité et d'incomplétude.
A la section 1 on introduit la première notion de fonction calculable qui puisse venir à l'esprit, à savoir celle de fonction récursive primitive (en abrégé 𝓡𝓟). On donne plusieurs approches de cette notion, ainsi que les premiers exemples de fonctions 𝓡𝓟. On montre ensuite comment les fonctions 𝓡𝓟 vont nous permettre d'aborder avec succès des notions un peu plus subtiles : quantifications bornées, opérateur de minimalisation, codage des suites finies d'entiers, énumération des suites. La section se termine par un résultat négatif. On montre de deux façons différentes que la notion de fonction récursive primitive est inadéquate par rapport à la calculabilité : d'abord par un argument théorique, appelé diagonalisation, puis par l'exhibition d'une fonction calculable qui n'est pas 𝓡𝓟 : la fonction d'Ackermann.
La section 2 étudie une classe plus générale de fonctions, à savoir celle des fonctions récursives. Dans un premier temps, une réflexion simple nous permet de constater que le passage à des fonctions partielles rend caduc l'argument diagonal évoqué ci-dessus. On donne alors la définition des fonctions récursives (partielles) et les premières propriétés qui en découlent. On expose ensuite la thèse de Church, qui dit en substance que les fonctions récursives sont exactement les fonctions calculables en un certain sens.
A la section 3 on rentre dans un domaine plus technique avec la complexité des formules. On se place dans la structure 𝓝=⟨ℕ 0, S, +, ∗, ≤⟩ , où on définit les formules Δ0_0 , Σ0_1 et Π0_1 . On généralise ensuite cette définition aux formules Σ et Π , dont on montre l'identité avec les formules Σ0_1 et Π0_1 dans le cadre de la 𝓝-équivalence. On termine par la définition des fonctions Δ0_0-rudimentaires, qui joueront un rôle important dans les sections 4 et 5.
La section 4 est consacrée à l'énumération Δ0_0-rudimentaire des suites finies. Après quelques préliminaires algébriques on définit la fonction β-tilda de Gödel, puis on montre que les fonctions récursives partielles sont exactement les fonctions à graphe Σ0_1 . On termine par la forme normale de Kleene, dont on donne quelques conséquences pratiques.
A la section 5 nous étudions un exemple concret de fonctions calculables. Il en existe divers modèles, et nous avons choisi celui des machines à registres. Nous commençons par une description de ces machines, puis donnons quelques exemples de fonctions calculables et de programmes exécutables par machines à registres. Le résultat essentiel de cette section est que la classe des fonctions récursives coïncide exactement avec celle des fonctions calculables par machines à registres. On explique alors rapidement en quoi ce résultat abonde fortement dans le sens de la thèse de Church.
La section 6 est consacrée à l'étude des ensembles récursivement énumérables, ou semi-récursifs, qui est une classe plus large que celle des ensembles récursifs. Après quelques préliminaires sur les fonctions et relations universelles, on donne trois définitions des ensembles récursivement énumérables (dont on montre qu'elles sont équivalentes), et on les compare avec les ensembles récursifs. On s'intéresse ensuite au problème de la halte, où on montre que la question de savoir si un algorithme converge (c'est-à-dire s'arrête en un temps fini) est indécidable. On termine par quelques compléments sur les relations Σ0_1 et Π0_1 .
A la section 7 on rentre enfin dans le vif du sujet : la représentabilité d'une fonction de ℕ puissance p dans ℕ puissance q. On décrit la théorie PA faible , dite aussi arithmétique Q de Robinson, qui n'est autre que PA1 "amputée" du schéma d'induction, et on étudie de façon très superficielle la structure des modèles de cette théorie. On en vient ensuite aux fonctions représentables, qui sont les fonctions dont les résultats peuvent être "représentés en un certain sens" par une formule du langage de PA faible . L'étude de la représentabilité passe en particulier par la fonction β de Gödel, qui permet de coder les suites d'entiers. On termine par l'exposé du théorème de représentation, qui dit que toute fonction récursive totale est représentable.
A la section 8 on arithmétise la syntaxe : on commence par coder les formules, puis les démonstrations, et on termine par la notion de théorie récursive.
Enfin, à la section 9 on présente les différents théorèmes d'indécidabilité et d'incomplétude, dits aussi théorèmes de limitation. On commence par le théorème d'indécidabilité de Church, qui énonce l'indécidabilité de l'arithmétique et du calcul des prédicats. Viennent ensuite le lemme diagonal, qui contient en substance l'essentiel de ce qui suit, puis enfin les célèbres théorèmes d'incomplétude de Gödel. En conclusion, on explique en quoi le second théorème d'incomplétude va nous servir en théorie des ensembles.