Théorèmes d'incomplétude de Gödel

Les théorèmes d'incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, publiés par Kurt Gödel en 1931 dans son article (« Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés »). Ils ont marqué un tournant dans l'histoire de la logique en apportant une réponse négative à la question de la démonstration de la cohérence des mathématiques posée plus de 20 ans auparavant par le programme de Hilbert. Le premier théorème d'incomplétude établit qu'une théorie cohérente suffisante pour y démontrer les théorèmes de base de l'arithmétique est nécessairement incomplète, au sens où il existe des énoncés qui n'y sont ni démontrables, ni réfutables (un énoncé est démontrable si on peut le déduire des axiomes de la théorie, il est réfutable si on peut déduire sa négation). On parle alors d'énoncés indécidables dans la théorie. Le second théorème d'incomplétude est à la fois un corollaire et une formalisation d'une partie de la preuve du premier. Il traite le problème des preuves de cohérence d'une théorie : une théorie est cohérente s'il existe des énoncés qui n'y sont pas démontrables (ou, ce qui revient au même, si on ne peut y démontrer A et non A) ; par exemple on exprime souvent la cohérence de l'arithmétique par le fait que l'énoncé 0 = 1 n'y est pas démontrable (sachant que bien entendu 0 ≠ 1 l'est). Sous des hypothèses à peine plus fortes que celles du premier théorème, on peut construire un énoncé exprimant la cohérence d'une théorie dans le langage de celle-ci. Le second théorème affirme alors que si la théorie est cohérente cet énoncé ne peut pas en être conséquence, ce que l'on peut résumer par : « une théorie cohérente ne démontre pas sa propre cohérence ». Le premier théorème d'incomplétude peut être énoncé de la façon encore un peu approximative suivante (les termes techniques sont expliqués dans le paragraphe suivant). De tels énoncés sont dits indécidables dans cette théorie. On dit également indépendants de la théorie.