THEOREMES D'INCOMPLETUDE DE GODEL

Source: http://www.peiresc.org/DINER/Lexique.pdf

 

Preuve publiée par Gödel en 1931 concernant l'existence de propositions indécidables dans tout système axiomatique fondé sur une classe d'axiomes assez riches pour permettre la construction de l'arithmétique. Le premier théorème, que l'on appelle souvent le théorème de Gödel, établit que dans tout système de l'arithmétique il existe une proposition qui ne peut être prouvée pas plus que sa négation à l'intérieur du système. Le second théorème établit que la consistance d'un système formel de l'arithmétique ne peut être démontrée par des moyens formalisables à l'intérieur du système. En fait ces théorèmes s'appliquent à toute théorie récursivement axiomatisable capable de formaliser l'arithmétique, soit une théorie qui soit formalisée de façon à reconnaître purement mécaniquement les axiomes parmi les énoncés. Grossièrement, le premier théorème énonce qu'une théorie suffisante pour faire de l'arithmétique est nécessairement incomplète, au sens où il existe dans cette théorie des énoncés qui ne sont pas démontrables et dont la négation n'est pas non plus démontrable : c'est-à-dire qu'il existe des énoncés sur lesquels on sait qu'on ne pourra jamais rien dire dans le cadre de la théorie. Sous le même genre d'hypothèses sur les théories considérées, le second théorème affirme qu'il existe un énoncé exprimant la cohérence de la théorie - le fait qu'elle ne permette pas de démontrer tout et donc n'importe quoi - et que cet énoncé ne peut pas être démontré dans la théorie elle-même. Gödel ne démontre pas qu'il existe en arithmétique des propositions vraies mais absolument indémontrables. Il montre plutôt que toutes les propositions vraies de l'arithmétique ne peuvent pas être démontrées dans un seul et unique système formel donné. À cause des hypothèses des théorèmes, toute théorie qui prétend formaliser l'ensemble des mathématiques, comme la théorie des ensembles, est concernée. Faut-il pour autant renoncer à ce qu'un discours mathématique ait une valeur de vérité universelle ? Sur quoi se fonder pour savoir s'il est cohérent, puisqu'il semble que l'on ne puisse y arriver par des moyens purement internes aux mathématiques ? Les théorèmes de Gödel ne donnent pas de réponse mais permettent d'écarter celles qui sont trop simples. Un tel résultat eu pour effet de compromettre la finalisation du programme de Hilbert sur le fondement des mathématiques. Ce résultat réfutait d'avance toutes les tentatives d'unité de la langue de la science telles qu'elles seront formulées par Carnap en 1932. Popper remarquait avec ironie que cette réfutation provenait d'un collègue de Carnap au Cercle de Vienne. Les théorèmes de Gödel sont d'une grande portée philosophique en contestant la possibilité de formalisation complète de la connaissance scientifique et s'inscrivent techniquement dans les développements de la logique, en particulier la théorie des algorithmes, de la calculabilité et de la récursivité, participant ainsi au développement de l'informatique. Gödel a forcé les mathématiciens à s'interroger sur la différence entre la vérité et la preuve, ce qui a provoqué une révolution en mathématiques aussi dramatique que la découverte des géométries non euclidiennes. En d'autres termes, les penseurs rationalistes après Platon et Descartes voyaient les mathématiques comme l'exemple suprême du raisonnement et essayaient de s'en inspirer pour des questions relevant d'autres domaines. Pour les tenants de cette vision rationaliste, le théorème de Gödel fut perçu comme un choc car il coupait l'herbe sous le pied aux défenseurs de la raison pure. Si les fondations des mathématiques pures devenaient elles-mêmes incertaines, alors qu'en serait-il d'autres domaines de la réalité, moins ordonnés et plus compliqués mais plus significatifs encore pour nous ? Le but était d'amener la certitude mathématique dans d'autres champs de la pensée humaine, mais si les mathématiques venaient à produire des doutes, de quoi serions-nous sûrs désormais ? Ce sont en partie les raisons du choc. Dans la seconde moitié du XX° siècle Chaitin a transposé le résultat de Gödel à la théorie de la complexité. Si l'on adopte la définition de la complexité de Kolmogorov d'un objet comme taille minimale d'un programme calculant cet objet, les nombres aléatoires sont ceux pour lesquels il n'existe pas de programme plus court que la liste de leurs chiffres. Chaitin a démontré que bien que la plupart des nombres soient des nombres aléatoires, un système formel donné, aussi puissant soit il ne peut démontrer le caractère aléatoire que d'un nombre finis de nombres.